\n[:en]
\nThis article is only available in German<\/a>, unfortunately.
\n[:]
\n<\/p>\n
[:de]Die Anzahl an Kombinationen steigt ziemlich schnell, wie folgendes Bild f\u00fcr sieben Cent veranschaulicht:<\/p>\n
F\u00fcr das Euro-M\u00fcnzsystem, in dem jede gr\u00f6\u00dfere M\u00fcnze ein vielfaches aller kleineren M\u00fcnzen darstellt, l\u00e4sst sich das Problem recht einfach l\u00f6sen – n\u00e4mlich genau so wie das typischerweise eine Kassiererin machen w\u00fcrde (zumindest solange ihr das Kleingeld nicht ausgeht). Man nimmt einfach m\u00f6glichst gro\u00dfe M\u00fcnzen – also ein Greedy Algorithmus. Der w\u00fcrde dann in Python etwa so aussehen:<\/p>\n Das funktioniert, wie gesagt, bei unserem M\u00fcnzsystem ganz gut – kann aber in anderen Situationen schiefgehen. Ein einfaches Beispiel w\u00e4re ein M\u00fcnzsystem in dem als M\u00fcnzwerte nur 1 Cent, 4 Cent, 199 Cent und 200 Cent vorkommen. Hier w\u00fcrde der Algorithmus f\u00fcr 203 Cent vier M\u00fcnzen verlangen (eine 200 Cent \/ 2 Euro M\u00fcnze und drei 1 Cent M\u00fcnzen) obwohl offensichtlich bereits zwei M\u00fcnzen reichen (eine 199 Cent M\u00fcnze und eine 4 Cent M\u00fcnze). Die Frage ist also – gibt es einen Algorithmus der auch mit derart seltsamen M\u00fcnzsystemen zurechtkommt? Wenn ich mir das M\u00fcnzsystem anschaue, welches in Gro\u00dfbritannien bis 1971 \u00fcblich war<\/a>, k\u00f6nnte das Problem durchaus ein realistisches sein :)<\/p>\n Also geht es zuverl\u00e4ssiger? Naja, man kann den Baum einfach mal rekursiv komplett durchgehen und mitz\u00e4hlen, wieviele Pfeile man jeweils gelaufen ist. In Code gegossen w\u00fcrde das etwa so aussehen (die Definition der M\u00fcnzen bleibt wie oben):<\/p>\n \u00a0Wie oben ist die Abbruchbedingung, dass die 0 erreicht wurde. Falls wir noch nicht am Ende sind, berechnen wir f\u00fcr jede M\u00fcnze einen neuen Wert aus dem aktuellen Wert minus dem Wert der M\u00fcnze. Das erzeugt quasi f\u00fcr einen Knoten im Baum die jeweiligen Kindknoten. Negative Ergebnisse werden weggeworfen – dann war die M\u00fcnze zu gro\u00df f\u00fcr den Restbetrag. Anschlie\u00dfend suchen wir rekursiv weiter und geben am Ende das Minimum aus.<\/p>\n Das Problem bei diesem Ansatz ist, dass er zwar elegant hingeschrieben, aber unglaublich ineffizient ist. Tats\u00e4chlich f\u00fchrt der Ansatz schon bei kleinen Betr\u00e4gen zu exorbitant langen Wartezeiten. Auf meinem Rechner habe ich die Berechnung des Betrages 202 (also zwei Euro und zwei Cent) nach f\u00fcnf Minuten abgebrochen. Tats\u00e4chlich kann man sich schnell klar machen, dass dieser Algorithmus sehr viele Varianten v\u00f6llig unn\u00f6tigerweise untersucht. Eine erste M\u00f6glichkeit 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\u00e4re. Im Bild von oben: Wenn man zun\u00e4chst den rechten Pfad gew\u00e4hlt hat (also die 5 Cent und dann die 2 Cent), dann wei\u00df man bereits, dass es eine L\u00f6sung mit zwei Schritten gibt. Es ergibt dann f\u00fcr alle weiteren potentiellen L\u00f6sungen 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\u00f6glich eine erste (hoffentlich kurze) L\u00f6sung zu finden. Das sieht dann wie folgt aus:<\/p>\n \u00a0Das funktioniert schon deutlich besser. Werte im niedrigen Eurobereich werden hier halbwegs schnell gefunden. Trotzdem ist auch diese Variante noch zu langsam. Der Grund daf\u00fcr ist, dass immer noch viel zu viel berechnet wird. Statt sich Zwischenergebnisse zu merken und f\u00fcr andere Pfade weiterzuverwenden, verwirft der Algorithmus alle Ergebnisse und berechnet alles wieder neu. Dabei k\u00f6nnten einige Ergebnisse sehr hilfreich sein. Im Bild ganz oben sieht man zum Beispiel, dass die Kombination 0 0<\/span> (also die M\u00f6glichkeiten zwei Cent aufzuteilen) sehr oft vorkommt. Statt dies immer wieder neu zu berechnen, w\u00e4re es viel sinnvoller, sich die Ergebnisse zu merken und in anderen Zweigen dann einfach einzusetzen.<\/p>\n![\"sieben\"](\"https:\/\/balanceofcowards.net\/wp-uploads\/balanceofcowards.net\/2014\/01\/sieben-300x125.png\")
<\/a>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\u00fcck und einem 2-Cent St\u00fcck entspricht (wer genau hinsieht, erkennt, dass ein \u00e4quivalenter Pfad im Bild noch ein zweites Mal vorhanden ist).<\/p>\n# Example uses European currency - Euros and Cents (coins only)\r\ncoins = [1, 2, 5, 10, 20, 50, 100, 200]\r\n\r\ndef coinage1(value):\r\n \"\"\"\r\n Greedy search - try to minimize value as fast as possible. This is what\r\n ordinary people would usually do. May miss more optimal solutions in\r\n specific cases.\r\n \"\"\"\r\n if value == 0:\r\n return 0\r\n fits = filter( (lambda n: n <= value), coins)\r\n return 1 + coinage1(value - max(fits))<\/pre>\n
def coinage2(value):\r\n \"\"\"\r\n Naive, recursive search through the entire solution space\r\n \"\"\"\r\n if value == 0:\r\n return 0\r\n nvalues = filter( (lambda n: n >= 0), map( (lambda n: value - n), coins ) )\r\n return 1 + min( map( coinage1, nvalues) )<\/pre>\n
def coinage3(value, limit=None):\r\n \"\"\"\r\n Recursive search that will prune those parts of the solution space where\r\n a better solution has been found already.\r\n \"\"\"\r\n if limit is None:\r\n limit = value\r\n\r\n if value == 0:\r\n return 0\r\n\r\n scoins = sorted(coins, reverse=True)\r\n solution = limit\r\n for coin in scoins:\r\n newval = value - coin\r\n if newval >= 0 and solution >= 0:\r\n newlim = 1 + coinage3(newval, solution - 1)\r\n if newlim < solution:\r\n solution = newlim\r\n return solution<\/pre>\n