Denkaufgabe: Geldscheinstückelung
Wieder mal die eingerosteten altersschwachen Hirnzellen in Betrieb setzen:
Ein Jungstudent hat mir begeistert von seiner Programmieraufgabe aus einer Einführungsvorlesung in die Informatik erzählt. Die Aufgabe war: Als Eingabe dient eine ganze Zahl, die einen Geldbetrag in Euro (ohne Cent) darstellt. Das Programm soll ausgeben, wie man diesen Betrag in Euro-Scheinen zusammensetzt, und zwar mit möglichst wenig Scheinen. Hört sich einfach an, es geht ja auch zunächst mal um das Erlernen des Programmierens, und nicht um Rechenaufgaben. Sowas zum Üben eben.
Der Student hat die Aufgabe auch gelöst und mir erzählt, daß es ja eigentlich ganz einfach sei, er habe das mit Modulo-Rechnung gemacht. Den Betrag der Reihe nach durch die Geldscheinwerte ganzzahlig dividiert um die Zahl der benötigten Scheine dieser Größe zu erhalten und dann mit dem Modulo-Rest und dem nächstkleineren Schein weitergemacht. Klappt prima und liefert die richtigen Ergebnisse.
Wirklich?
Für die 50-20-10-Stückelung wie sie bei Währungen meist üblich ist, mag das zutreffen.
Hätten wir aber beispielsweise eine Stückelung aus 50-40-10-Taler Scheinen und geben 80 ein, dann liefert das Programm 1×50 + 3×10, also vier Scheine. Dabei wäre es auch mit zwei Scheinen gegangen (2×40). Also ist der Algorithmus nur für bestimmte Stückelungen zu gebrauchen, gar nicht schön. Aber für welche?
Fragen wir mal nicht nach dem universellen Algorithmus, sondern umgekehrt danach, welche Bedingungen die Stückelung erfüllen muß, um mit dem Trival-Algorithmus, nämlich dem Herunterrechnen vom größten zum kleinsten Schein, zum richtigen Ergebnis zu kommen. Der Trivial-Algorithmus entspricht nämlich der natürlichen Handlungsweise der meisten Menschen und hat dadurch schon seine Daseinsberechtigung.
In erster Vermutung könnte man auf die Idee kommen, daß jeder Schein mindestens den doppelten Wert des nächstniedrigeren haben muß. Hilft aber nicht. Wollen wir 90 Gulden mit einer 70-30-5-Stückelung zahlen, dann liefert der Algorithmus 1×70 + 4×5, also fünf Scheine, obwohl es mit dreien (3×30) ginge.
Es erinnert mich etwas an das Knapsack-Problem, das ist es aber nicht. Beim Knapsack geht es darum, möglichst nahe an eine Obergrenze heranzukommen und dabei den Wert unterhalb der Schranke zu maximieren. Hier geht es darum, die Grenze genau zu treffen. Der Wert der Scheine ist letztlich wurscht, denn die Summe ist festgelegt, es geht aber darum, die Zahl der Scheine zu minimieren.
Und was wäre ein Algorithmus für allgemeine Stückelungen, der besser als die vollständige Suche ist?
Ich muß mal drüber nachdenken. Erster Gedanke, der mir beim Autofahren gekommen ist: Es ist verwandt mit der Aufgabe, eine bestimmte Flüssigkeitsmenge mit zwei Kanistern abzufüllen, meistens ein 5- und ein 3-Gallonenkanister (Siehe Die Hard III). Die Kanister-Aufgabe ist nur ein erweiterter euklidischer Algorithmus mit gewissen Beschränkungen und neutralen Nachkorrekturen beim Ergebnis (man kann nicht mehr in einen Kanister packen als reingeht, und man kann nichts ausleeren, bevor man es eingefüllt hat).
Nur bei der Geldscheinaufgabe ist das so nicht ganz möglich, denn das “Wechselgeld” ist nicht vorgesehen. 90 Euro durch einen Hunderter hinzulegen und sich einen Zehner wegzunehmen, wie bei den Kanistern, entspricht zwar den Kaufgewohnheiten, aber nicht der Aufgabenstellung.
Also:
- Was wäre der Algorithmus für den allgemeinen Fall?
- Welche Komplexität hätte der? Kommen wir auf O(log n) wenn wir die Arithmetik (Division usw.) mit Aufwand 1 annehmen?
- Welches Kriterium muß eine Stückelung erfüllen, damit der Trivial-Algorithmus stets das beste Ergebnis liefern kann? (OK, das ist ja an sich schon das Kriterium, aber explizit ausformuliert…)
Mir geht da folgender Algorithmus durch den Kopf: Man nimmt eine leere Menge und fügt – beginnend mit dem kleinsten – eine Scheingröße nach der anderen der Menge hinzu und bildet den kgV aus den Größen. Dann schreibt man die Vielfachen aller Scheine bis zum kgV in eine Tabelle. Ist der kgV ein Teiler des nächstgrößeren Scheins, kann man die Scheine rausnehmen und die Menge dadurch verkleinern (also in größeren Schritten weiterrechnen). Dann könnte man bei der Eingabe des Betrages direkt in der Tabelle nachschlagen, aus welchen Beträgen man das zusammenbaut.
Bei der 50-20-10-Stückelung würde man also auch bei Hinzufügen des 50ers den 20er und den 10er noch nicht entfernen weil kgv(10,20)=20 kein Teiler von 50 ist. Allerdings kann man 80 ja als 1×50+3×10 oder 4×20 darstellen. Geht’s mit weniger Aufwand?
3 Kommentare (RSS-Feed)
Unter http://home.arcor.de/hirnstrom/tmp/Stueckelung.java habe ich eine nicht sonderlich inspirierte Lösung abgelegt.
Es ist eine nicht ganz dumme Brute-Force-Variante mit einer Abkürzung, die mitzählt, was die beste Lösung war, und wenn eine Lösung mit – sagen wir – 3 Scheinen vorliegt, alle Versuche mit mehr als 3 Scheinen bei Schein 4 abbricht (also eine 2. Lösung findet).
Wenn der User mitspielt, und die Stückelungsliste absteigend sortiert eingibt (50,20,10), so ist der Algorithmus i.d.R. schneller, als wenn die Sortierung aufsteigend (10,20,50) ist.
Er vermeidet auch die Wechselmöglichkeiten (1,2) und (2,1) für 3 zu finden – er findet nur (2,1).
Hier eine Liste der Werte bis 1 Euro, für unsere Währung unter der Berücksichtigung von Münzen (ob der Blog das mitmacht?):
for i in {1..101} ; do echo -n $i” “; java Stueckelung $i 100,50,20,10,5,2,1 ; done
1 len: 1 : 1
2 len: 1 : 2
3 len: 2 : 2, 1
4 len: 2 : 2, 2
5 len: 1 : 5
6 len: 2 : 5, 1
7 len: 2 : 5, 2
8 len: 3 : 5, 2, 1
9 len: 3 : 5, 2, 2
10 len: 1 : 10
11 len: 2 : 10, 1
12 len: 2 : 10, 2
13 len: 3 : 10, 2, 1
14 len: 3 : 10, 2, 2
15 len: 2 : 10, 5
16 len: 3 : 10, 5, 1
17 len: 3 : 10, 5, 2
18 len: 4 : 10, 5, 2, 1
19 len: 4 : 10, 5, 2, 2
20 len: 1 : 20
21 len: 2 : 20, 1
22 len: 2 : 20, 2
23 len: 3 : 20, 2, 1
24 len: 3 : 20, 2, 2
25 len: 2 : 20, 5
26 len: 3 : 20, 5, 1
27 len: 3 : 20, 5, 2
28 len: 4 : 20, 5, 2, 1
29 len: 4 : 20, 5, 2, 2
30 len: 2 : 20, 10
31 len: 3 : 20, 10, 1
32 len: 3 : 20, 10, 2
33 len: 4 : 20, 10, 2, 1
34 len: 4 : 20, 10, 2, 2
35 len: 3 : 20, 10, 5
36 len: 4 : 20, 10, 5, 1
37 len: 4 : 20, 10, 5, 2
38 len: 5 : 20, 10, 5, 2, 1
39 len: 5 : 20, 10, 5, 2, 2
40 len: 2 : 20, 20
41 len: 3 : 20, 20, 1
42 len: 3 : 20, 20, 2
43 len: 4 : 20, 20, 2, 1
44 len: 4 : 20, 20, 2, 2
45 len: 3 : 20, 20, 5
46 len: 4 : 20, 20, 5, 1
47 len: 4 : 20, 20, 5, 2
48 len: 5 : 20, 20, 5, 2, 1
49 len: 5 : 20, 20, 5, 2, 2
50 len: 1 : 50
51 len: 2 : 50, 1
52 len: 2 : 50, 2
53 len: 3 : 50, 2, 1
54 len: 3 : 50, 2, 2
55 len: 2 : 50, 5
56 len: 3 : 50, 5, 1
57 len: 3 : 50, 5, 2
58 len: 4 : 50, 5, 2, 1
59 len: 4 : 50, 5, 2, 2
60 len: 2 : 50, 10
61 len: 3 : 50, 10, 1
62 len: 3 : 50, 10, 2
63 len: 4 : 50, 10, 2, 1
64 len: 4 : 50, 10, 2, 2
65 len: 3 : 50, 10, 5
66 len: 4 : 50, 10, 5, 1
67 len: 4 : 50, 10, 5, 2
68 len: 5 : 50, 10, 5, 2, 1
69 len: 5 : 50, 10, 5, 2, 2
70 len: 2 : 50, 20
71 len: 3 : 50, 20, 1
72 len: 3 : 50, 20, 2
73 len: 4 : 50, 20, 2, 1
74 len: 4 : 50, 20, 2, 2
75 len: 3 : 50, 20, 5
76 len: 4 : 50, 20, 5, 1
77 len: 4 : 50, 20, 5, 2
78 len: 5 : 50, 20, 5, 2, 1
79 len: 5 : 50, 20, 5, 2, 2
80 len: 3 : 50, 20, 10
81 len: 4 : 50, 20, 10, 1
82 len: 4 : 50, 20, 10, 2
83 len: 5 : 50, 20, 10, 2, 1
84 len: 5 : 50, 20, 10, 2, 2
85 len: 4 : 50, 20, 10, 5
86 len: 5 : 50, 20, 10, 5, 1
87 len: 5 : 50, 20, 10, 5, 2
88 len: 6 : 50, 20, 10, 5, 2, 1
89 len: 6 : 50, 20, 10, 5, 2, 2
90 len: 3 : 50, 20, 20
91 len: 4 : 50, 20, 20, 1
92 len: 4 : 50, 20, 20, 2
93 len: 5 : 50, 20, 20, 2, 1
94 len: 5 : 50, 20, 20, 2, 2
95 len: 4 : 50, 20, 20, 5
96 len: 5 : 50, 20, 20, 5, 1
97 len: 5 : 50, 20, 20, 5, 2
98 len: 6 : 50, 20, 20, 5, 2, 1
99 len: 6 : 50, 20, 20, 5, 2, 2
100 len: 1 : 100
Neben der ästhetisch bemerkenswerten Selbstähnlichkeit fällt mir auf, daß es keinen Fall gibt, in dem der Algorithmus 2 gleichgute Lösungen findet (das kann er durchaus – siehe die Aufteilung der 10 auf (2,3,4): =>(3,3,4);(4,4,2).
Und er tappt auch nirgends in die 90 (70,30,5)-Falle, bei der er erst das zweitbeste Ergebnis findet.
Nennen wir ein Element der Stückelliste ‘Stück’ oder ‘S’, so gilt für jeden Betrag > S ist S ein Element der besten Stückelliste, wenn die Stückelliste 1,2,5,10… lautet. Nicht so bei (5,30,70). Was ist dafür bestimmend?
Das deutet m.E. darauf hin, daß die 1,2,5,10,20…-Stückelung ein Optimum sein könnte.
Jetzt ruft aber die Bettdecke. Ich bin erkältet. Der Kaffee ist alle.
Im Projekt Euler – eine Sammlung Matheaufgaben für Programmierer hauptsächlich – gibt es eine verwandte Frage: Frage 31: http://projecteuler.net/index.php?section=problems
Es geht nicht um die beste, sondern um alle Lösungen einer Stückelung, aber die, die man lösen soll, enthält keine 70/30-Falle. 🙂
Nicht uninteressant.
Kleine Korrektur vorab: Vorletzter Absatz: ‘bildet das kgV’, nicht ‘den’.
Spontan fällt mir ein kürzlich aufgeschnappter Rat ein: “In doubt, use brute force”. 🙂
Interessant wäre es zu untersuchen, ob es Währungen mit schlechter Stückelung gibt, das wäre eine Währung, die bei allen Gesamtwerten unter dem Doppelten des größten Wertes zusammmen deutlich mehr Scheine benötigt, als andere.
Also ein einfaches Beispiel: 1, 2, 5, 10.
Maximum < 2*10 = 19.
Erzeugen einer Liste aller Werte {1, 2, 3, … 19};
Erzeugen einer Funktion größteStückelung (Wert).
Anwenden der Funktion auf die Liste und Bildung der Summe.
Ich könnte mir vorstellen, daß die 1,2,5,10… – Stückelung schon das Optimum ist.
Beim Vergleich mit 1, 2, 6, 8 müßte man für die zweite Liste selbstverständlich auch bis 19 gehen. Oder sollte vielleicht zwei Vergleiche anstellen – einmal bis 19, einmal bis 15=(2*8)-1.
Die Idee mit 2*M-1 ist übrigens nur so aus dem Bauch heraus gefällt.
Hey – eigentlich wollte ich mich heute abend mit was anderem beschäftigen. 🙂