[:de]

Ein interessantes Problem über das ich heute gestolpert bin: Für einen beliebigen Geldbetrag n – was ist die minimale Anzahl an Münzen, mit der man diesen Geldbetrag erreichen kann? Also zum Beispiel kann man ja 10 Cent als zehn einzelne Cent-Stücke, oder aber als zwei Fünf-Cent Stücke, oder als ein Fünf-Cent Stück und fünf einzelne Cent-Stücke darstellen, und so weiter. Für zehn Cent ist natürlich die minimale Anzahl an Münzen genau eine Zehn-Cent Münze. Aber wie löst man das Problem allgemein?

[:]
[:en]
This article is only available in German, unfortunately.
[:]

[:de]Die Anzahl an Kombinationen steigt ziemlich schnell, wie folgendes Bild für sieben Cent veranschaulicht:

Hier entspricht jeder Pfeil einer Reduktion um einen bestimmten Betrag (1, 2, oder 5 Cent). Gesucht ist anschaulich die minimale Anzahl an Pfeilen, denen man folgen muss, bis man eine 0 erreicht. Im Bild wird schnell klar, dass das der rechteste Pfad ist – der Pfad, der einem 5-Cent Stück und einem 2-Cent Stück entspricht (wer genau hinsieht, erkennt, dass ein äquivalenter Pfad im Bild noch ein zweites Mal vorhanden ist).

Für das Euro-Münzsystem, in dem jede größere Münze ein vielfaches aller kleineren Münzen darstellt, lässt sich das Problem recht einfach lösen – nämlich genau so wie das typischerweise eine Kassiererin machen würde (zumindest solange ihr das Kleingeld nicht ausgeht). Man nimmt einfach möglichst große Münzen – also ein Greedy Algorithmus. Der würde dann in Python etwa so aussehen:

# Example uses European currency - Euros and Cents (coins only)
coins = [1, 2, 5, 10, 20, 50, 100, 200]

def coinage1(value):
    """
        Greedy search - try to minimize value as fast as possible. This is what
        ordinary people would usually do. May miss more optimal solutions in
        specific cases.
    """
    if value == 0:
        return 0
    fits = filter( (lambda n: n <= value), coins)
    return 1 + coinage1(value - max(fits))

Das funktioniert, wie gesagt, bei unserem Münzsystem ganz gut – kann aber in anderen Situationen schiefgehen. Ein einfaches Beispiel wäre ein Münzsystem in dem als Münzwerte nur 1 Cent, 4 Cent, 199 Cent und 200 Cent vorkommen. Hier würde der Algorithmus für 203 Cent vier Münzen verlangen (eine 200 Cent / 2 Euro Münze und drei 1 Cent Münzen) obwohl offensichtlich bereits zwei Münzen reichen (eine 199 Cent Münze und eine 4 Cent Münze). Die Frage ist also – gibt es einen Algorithmus der auch mit derart seltsamen Münzsystemen zurechtkommt? Wenn ich mir das Münzsystem anschaue, welches in Großbritannien bis 1971 üblich war, könnte das Problem durchaus ein realistisches sein :)

Also geht es zuverlässiger? Naja, man kann den Baum einfach mal rekursiv komplett durchgehen und mitzählen, wieviele Pfeile man jeweils gelaufen ist. In Code gegossen würde das etwa so aussehen (die Definition der Münzen bleibt wie oben):

def coinage2(value):
    """
        Naive, recursive search through the entire solution space
    """
    if value == 0:
        return 0
    nvalues = filter( (lambda n: n >= 0), map( (lambda n: value - n), coins ) )
    return 1 + min( map( coinage1, nvalues) )

 Wie oben ist die Abbruchbedingung, dass die 0 erreicht wurde. Falls wir noch nicht am Ende sind, berechnen wir für jede Münze einen neuen Wert aus dem aktuellen Wert minus dem Wert der Münze. Das erzeugt quasi für einen Knoten im Baum die jeweiligen Kindknoten. Negative Ergebnisse werden weggeworfen – dann war die Münze zu groß für den Restbetrag. Anschließend suchen wir rekursiv weiter und geben am Ende das Minimum aus.

Das Problem bei diesem Ansatz ist, dass er zwar elegant hingeschrieben, aber unglaublich ineffizient ist. Tatsächlich führt der Ansatz schon bei kleinen Beträgen zu exorbitant langen Wartezeiten. Auf meinem Rechner habe ich die Berechnung des Betrages 202 (also zwei Euro und zwei Cent) nach fünf Minuten abgebrochen. Tatsächlich kann man sich schnell klar machen, dass dieser Algorithmus sehr viele Varianten völlig unnötigerweise untersucht. Eine erste Möglichkeit dieses Verhalten zu verbessern, ist es, die Suche abzubrechen, falls man noch nicht am Ende angelangt ist, aber bei einer vorherigen Variante mit derselben Anzahl an Schritten bereits am Ende angelangt wäre. Im Bild von oben: Wenn man zunächst den rechten Pfad gewählt hat (also die 5 Cent und dann die 2 Cent), dann weiß man bereits, dass es eine Lösung mit zwei Schritten gibt. Es ergibt dann für alle weiteren potentiellen Lösungen keinen Sinn mehr, weiter als zwei Schritte zu suchen. Der folgende Algorithmus verwendet diesen Ansatz um schneller ans Ziel zu kommen. Um das noch etwas zu beschleunigen, adaptiert dieser Algorithmus noch den Greedy-Ansatz, um so schnell wie möglich eine erste (hoffentlich kurze) Lösung zu finden. Das sieht dann wie folgt aus:

def coinage3(value, limit=None):
    """
        Recursive search that will prune those parts of the solution space where
        a better solution has been found already.
    """
    if limit is None:
        limit = value

    if value == 0:
        return 0

    scoins = sorted(coins, reverse=True)
    solution = limit
    for coin in scoins:
        newval = value - coin
        if newval >= 0 and solution >= 0:
            newlim = 1 + coinage3(newval, solution - 1)
            if newlim < solution:
                solution = newlim
    return solution

 Das funktioniert schon deutlich besser. Werte im niedrigen Eurobereich werden hier halbwegs schnell gefunden. Trotzdem ist auch diese Variante noch zu langsam. Der Grund dafür ist, dass immer noch viel zu viel berechnet wird. Statt sich Zwischenergebnisse zu merken und für andere Pfade weiterzuverwenden, verwirft der Algorithmus alle Ergebnisse und berechnet alles wieder neu. Dabei könnten einige Ergebnisse sehr hilfreich sein. Im Bild ganz oben sieht man zum Beispiel, dass die Kombination 0 0 (also die Möglichkeiten zwei Cent aufzuteilen) sehr oft vorkommt. Statt dies immer wieder neu zu berechnen, wäre es viel sinnvoller, sich die Ergebnisse zu merken und in anderen Zweigen dann einfach einzusetzen.

Hier kommt Dynamic Programming ins Spiel. Man benötigt eine Datenstruktur, die durch die Rekursion mitgezogen wird und dazu dient, Zwischenergebnisse zu speichern. Das dahinterliegende Konzept ist hier gut erklärt. Wenn wir das versuchen, sieht der Algorithmus etwa wie folgt aus:

def coinage4(value, solutions=None):
    """
        Recursive search with Dynamic Programming. This will avoid working on
        the same subproblem again and again.
    """
    if solutions is None:
        solutions = {0: 0}

    if value not in solutions:
        nvalues = filter((lambda n: n >= 0), map((lambda n: value - n), coins))
        cfunc = lambda n: coinage4(n, solutions=solutions)
        solutions[value] = 1 + min(map( cfunc, nvalues ))
    return solutions[value]

Hier merkt sich der Algorithmus die bereits erarbeiteten Lösungen in einem Dictionary. Nur wenn das aktuelle Teilproblem noch nicht gelöst wurde, wird es tatsächlich berechnet. Ansonsten schlägt man einfach im Dictionary nach. Diese Lösung bringt tatsächlich einen erheblichen Geschwindigkeitsschub mit sich. Für eine finale Verbesserung können wir noch die letzten beiden Varianten kombinieren, und zusätzlich zur Weiterverwendung bisheriger Rechenergebnisse auch die Suche abbrechen, falls wir schon einen kürzeren Pfad kennen. Das sieht dann wie folgt aus:

def coinage5(value, limit=None, solutions=None):
    """
        A combination of coinage4 and coinage3 - avoid searching unnecessary
        parts of the solution space.
    """
    if limit is None:
        limit = value

    if solutions is None:
        solutions = {0: 0}

    if value == 0:
        return 0

    scoins = sorted(coins, reverse=True)

    if value not in solutions:
        solution = limit
        for coin in scoins:
            newval = value - coin
            if newval >= 0 and solution >= 0:
                newlim = 1 + coinage5(newval, solution - 1, solutions)
                if newlim < solution:
                    solution = newlim
        solutions[value] = solution
    return solutions[value]

 Diese Variante arbeitet richtig schnell. Hier treten Probleme dann vorrangig nicht mehr mit der Laufzeit, sondern mit der Rekursionstiefe auf. Jenseits der 1000 Euro wird die vorgegebene Rekursionstiefe überschritten und der Interpreter bricht die Berechnung mit einem Fehler ab. Man kann zwar die erlaubte Rekursionstiefe erhöhen, aber letztendlich würde dann doch nur ein iterativer Algorithms dieses Problem lösen.

Interessante Tatsache am Rande: Das Problem ist eine Variante des bekannten Rucksack-Problems und damit im allgemeinen Fall NP-vollständig. Jedenfalls eine nette Abwechslung das mal zu lösen. Den Code so zu erweitern, dass er rausfindet, welche Münzkombination denn jetzt die minimale war, bleibt dann zum selber lösen :)

[:]