Das Wechselgeldproblem
Kurz gesagt: Das Wechselgeldproblem sucht die wenigsten Münzen für einen Betrag; eine Tabelle der dynamischen Programmierung löst es in O(Betrag × Münzen), nennt die Münzen und zählt die Möglichkeiten.
Problem
Das Wechselgeld des Automaten
Der Parkautomat gibt Wechselgeld zurück. Er hat für jede der acht Euro-Münzen eine Röhre: 1, 2, 5, 10, 20 und 50 Cent, 1 € und 2 €. Je weniger Münzen er herausgibt, desto seltener muss jemand die Röhren nachfüllen. Das Wechselgeld soll also aus den wenigsten Münzen bestehen.
Der Entwickler will nicht raten und schreibt eine Rekursion, die alles ausprobiert: für jede Münze, die ins Wechselgeld passt, „diese Münze plus das Beste für den Rest“, und nimmt das Kleinste. Die Beträge sind in Cent, und der Zähler zählt die ausprobierten Münzen:
static long tries = 0;
static int Fewest(int[] coins, int amount){ if (amount == 0) { return 0; } int best = amount + 1; foreach (int coin in coins) { if (coin > amount) { break; } tries++; int count = Fewest(coins, amount - coin) + 1; best = Math.Min(best, count); } return best;}
int[] coins = { 1, 2, 5, 10, 20, 50, 100, 200 };foreach (int amount in new[] { 10, 20, 30 }){ tries = 0; int count = Fewest(coins, amount); Console.WriteLine($"{amount} Cent: {count} Münzen, {tries} Versuche");}10 Cent: 1 Münzen, 309 Versuche20 Cent: 1 Münzen, 66281 Versuche30 Cent: 2 Münzen, 14158888 VersucheDie Antworten stimmen. Aber für 30 Cent probiert die Rekursion 14.158.888 Münzen aus, und für 40 Cent 3.024.560.419. Wechselgeld von 63 Cent braucht 689.951.222.249.236 Versuche: Bei einer Milliarde pro Sekunde sind das acht Tage, während der Fahrer an der Schranke wartet.
Die Idee
Die Tabelle
Die Rekursion fragt immer wieder dasselbe: das Beste für 13 Cent, für 8 Cent, für 3 Cent. Das sind die überlappenden Teilprobleme aus der vorigen Lektion. Nur gehen hier von jedem Betrag bis zu acht Zweige ab, einer für jede Münze, und der Baum wächst noch schneller.
Also bauen wir eine Tabelle von unten nach oben. Eine Tabelle der dynamischen Programmierung wird durch vier Dinge beschrieben:
- Was die Zelle bedeutet. best[a] sind die wenigsten Münzen für genau a Cent.
- Woher sie kommt. Die letzte Münze ist eine der passenden. Also ist best[a] gleich 1 + best[a − Münze] für die beste Münze.
- In welcher Reihenfolge sie gefüllt wird. a − Münze ist kleiner als a. Von links nach rechts ist alles, was die Zelle liest, schon fertig.
- Wo die Antwort steht. In der letzten Zelle, best[Wechselgeld]. Der Start ist best[0] = 0: Null Cent brauchen keine Münzen.
Das ist eine DP-Tabelle: eine Zelle für jedes Teilproblem, gefüllt in einer Reihenfolge, in der jede Zelle die Zellen, von denen sie abhängt, fertig vorfindet. Wie in der vorigen Lektion liegt die Wahl nur in der Zelle, zwischen mehreren Möglichkeiten.
Sieh es dir an
Zelle für Zelle
Die Tabelle für 9 Cent. Achte auf die Pfeile: Jeder kommt aus der Zelle a − Münze, und Zelle a behält das Kleinste, das sie gesehen hat:
static List<int> Change(int[] coins, int amount){ int[] best = new int[amount + 1]; int[] last = new int[amount + 1]; for (int a = 1; a <= amount; a++) { best[a] = amount + 1; foreach (int coin in coins) { if (coin > a) { break; } int count = best[a - coin] + 1; if (count < best[a]) { best[a] = count; last[a] = coin; } } } List<int> used = new List<int>(); for (int a = amount; a > 0; a -= last[a]) { used.Add(last[a]); } return used;}Schritt für Schritt, in Worten
- Change(coins, 9): best[a] sind die wenigsten Münzen für a Cent, last[a] die Münze, mit der man dorthin kommt. best[0] = 0: Null Cent brauchen keine Münzen.
- Probiere für jedes a von links nach rechts jede Münze bis a aus: eine Münze plus das Beste für den Rest, best[a − Münze] + 1. Der Pfeil kommt aus dieser Zelle.
- a = 5: Die Münze 1 ergibt best[4] + 1 = 3, die Münze 2 ergibt best[3] + 1 = 3, die Münze 5 ergibt best[0] + 1 = 1. Die Zelle behält das Kleinste, und last merkt sich die Münze.
- Die Münzen sind von klein nach groß geordnet, und 10 ist schon mehr als 9: Die Schleife hält dort an. Jede Zelle liest nur Zellen links von ihr, und die sind schon endgültig.
- Zurück entlang last: 9 → 7 → 5 → 0. Die Münzen sind 2 + 2 + 5. 22 Versuche für 9 Cent, jede Zelle einmal gelöst.
int[] coins = { 1, 2, 5, 10, 20, 50, 100, 200 };Console.WriteLine(string.Join(" + ", Change(coins, 9)));2 + 2 + 5amount + 1 bedeutet „noch nichts“: Du brauchst nie mehr Münzen als Cent, denn schon Ein-Cent-Münzen ergeben genau amount. Der erste Versuch ist also immer besser. Die Zahl ist klein, und + 1 kann nicht überlaufen, wie es bei Integer.MAX_VALUE der Fall wäre.Die Idee
Welche Münzen
Die Anzahl reicht nicht: Der Automat muss auch wissen, welche Münzen er ausgeben soll. Neben best[a] führt die Tabelle deshalb auch last[a], die Münze, die zum Besten für a führt. Am Ende beginnst du beim Wechselgeld: last[a] ausgeben, abziehen und wiederholen, bis du 0 erreichst.
static long tries = 0;
static List<int> Change(int[] coins, int amount){ int[] best = new int[amount + 1]; int[] last = new int[amount + 1]; for (int a = 1; a <= amount; a++) { best[a] = amount + 1; foreach (int coin in coins) { if (coin > a) { break; } tries++; int count = best[a - coin] + 1; if (count < best[a]) { best[a] = count; last[a] = coin; } } } List<int> used = new List<int>(); for (int a = amount; a > 0; a -= last[a]) { used.Add(last[a]); } return used;}
int[] coins = { 1, 2, 5, 10, 20, 50, 100, 200 };foreach (int amount in new[] { 63, 480 }){ tries = 0; List<int> used = Change(coins, amount); string list = string.Join(" + ", used); Console.WriteLine($"{amount} Cent: {list}, {tries} Versuche");}63 Cent: 1 + 2 + 10 + 50, 296 Versuche480 Cent: 10 + 20 + 50 + 200 + 200, 3460 Versuche296 Versuche für 63 Cent statt 689.951.222.249.236. Die Tabelle hat eine Zelle pro Cent, und jede Zelle probiert höchstens die acht Münzen aus. Die Arbeit ist O(n · k): n Cent mal k Münzarten. Mit k = 8 ist das linear im Wechselgeld.
Probier es aus
Ergänze
Eine Münze plus das Beste für den Rest. Welche Zelle liest der Versuch?
static List<int> Change(int[] coins, int amount)
{
int[] best = new int[amount + 1];
int[] last = new int[amount + 1];
for (int a = 1; a <= amount; a++)
{
best[a] = amount + 1;
foreach (int coin in coins)
{
if (coin > a)
{
break;
}
int count = best[] + 1;
if (count < best[a])
{
best[a] = count;
last[a] = coin;
}
}
}
List<int> used = new List<int>();
for (int a = amount; a > 0; a -= last[a])
{
used.Add(last[a]);
}
return used;
}Der Rest nach der Münze sind a - coin Cent, und das Beste dafür steht schon in der Tabelle, weil es links liegt. Eine Münze mehr ist + 1.
Die Idee
Warum nicht zuerst die größte Münze?
Ein Kassierer macht etwas anderes: Er gibt die größte Münze, die passt, und wiederholt das. Für 63 Cent sind das 50, 10, 2, 1: wieder vier Münzen. Mit Euro-Münzen liefert diese Regel immer die wenigsten Münzen. Die Münzen sind so gewählt.
Aber die Regel hängt vom Münzsystem ab. Bei anderen Münzen oder wenn eine Röhre im Automaten leer wird, kann „die größte zuerst“ mehr Münzen als nötig liefern. Wann sie funktioniert und wann sie scheitert, ist die Lektion „Wann ein gieriger Algorithmus scheitert“. Die Tabelle verlässt sich nicht darauf: Sie probiert für jeden Betrag jede Münze aus und findet die wenigsten für beliebige Münzen.
Die Idee
Auf wie viele Arten
Ein anderes Problem mit derselben Tabelle. Der Geldautomat zahlt Beträge in Scheinen zu 5, 10, 20 und 50 € aus. Die Tester wollen jede mögliche Kombination für 100 € prüfen und fragen: Wie viele gibt es?
Jetzt ist die Zelle count[a]: auf wie viele Arten sich genau a Euro bilden lassen. count[0] = 1, die leere Kombination. Die äußere Schleife geht über die Scheine, die innere über die Beträge:
static long Ways(int[] notes, int amount){ long[] count = new long[amount + 1]; count[0] = 1; foreach (int note in notes) { for (int a = note; a <= amount; a++) { count[a] += count[a - note]; } } return count[amount];}int[] notes = { 5, 10, 20, 50 };Console.WriteLine(Ways(notes, 100) + " Möglichkeiten");49 MöglichkeitenDie Reihenfolge der Schleifen ist wichtig. Wenn die Fünfer ganz vor den Zehnern kommen, wird jede Kombination in einer Reihenfolge gebaut: erst die Fünfer, dann die Zehner. 5 + 10 und 10 + 5 sind also dieselbe Kombination und werden einmal gezählt. Und hier sucht niemand ein Minimum: Die Zelle addiert die Anzahl der Möglichkeiten aus den Zellen links von ihr.
Probier es aus
Sag die Ausgabe voraus
Wie viele Kombinationen gibt es für 20 € mit Scheinen zu 5, 10 und 20?
static long Ways(int[] notes, int amount){ long[] count = new long[amount + 1]; count[0] = 1; foreach (int note in notes) { for (int a = note; a <= amount; a++) { count[a] += count[a - note]; } } return count[amount];}
int[] notes = { 5, 10, 20 };Console.WriteLine(Ways(notes, 20) + " Möglichkeiten");Ein Zwanziger; zwei Zehner; ein Zehner und zwei Fünfer; vier Fünfer. Vier Kombinationen. 6 ist die Zahl der Reihenfolgen: 10 + 5 + 5, 5 + 10 + 5 und 5 + 5 + 10 sind drei davon, aber die Kombination ist eine.
Probier es aus
Finde den Fehler
Ein Kollege hat dieselbe Zählung geschrieben, aber für 100 € kommt eine viel größere Zahl heraus:
int[] notes = { 5, 10, 20, 50 };Console.WriteLine(Ways(notes, 100) + " Möglichkeiten");48007 MöglichkeitenIn welcher Zeile steckt der Fehler?
Wähle die Zeile mit dem Fehler.
Die äußere Schleife geht über die Beträge, die innere über die Scheine. Für jeden Betrag wird also jeder Schein als der letzte probiert, unabhängig von den vorigen, und jede Anordnung einer Kombination wird einzeln gezählt: 5 + 10 und 10 + 5 sind zwei Möglichkeiten. Das ist die Zahl der Reihenfolgen, 48.007, während die Kombinationen 49 sind. Wenn die Scheine die äußere Schleife sind, wird jede Kombination in einer Reihenfolge gebaut und einmal gezählt.
Sieh es dir an
Miss es: Rekursion gegen Tabelle
Wir zählen die ausprobierten Münzen: in jedem rekursiven Aufruf und in jeder Zelle. Die Rekursion wird über 30 Cent nicht ausgeführt: Bei 40 Cent sind es über 3 Milliarden Versuche.
- Rekursion ohne Gedächtnis
O(2ⁿ) - Tabelle
O(n)
| Algorithmus | n = 10 | n = 20 | n = 30 |
|---|---|---|---|
| Rekursion ohne Gedächtnis | 309 | 66.281 | 14.158.888 |
| Tabelle | 26 | 67 | 117 |
static List<int> Change(int[] coins, int amount){ int[] best = new int[amount + 1]; int[] last = new int[amount + 1]; for (int a = 1; a <= amount; a++) { best[a] = amount + 1; foreach (int coin in coins) { if (coin > a) { break; } int count = best[a - coin] + 1; if (count < best[a]) { best[a] = count; last[a] = coin; } } } List<int> used = new List<int>(); for (int a = amount; a > 0; a -= last[a]) { used.Add(last[a]); } return used;}Alle 10 Cent vervielfacht sich die Rekursion um etwa das 200-Fache, während die Tabelle um 40 bis 50 Versuche wächst. Die Kurve der Rekursion ist mit O(2ⁿ) beschriftet: Sie ist exponentiell, mit einer Basis von etwa 1,7.
Genauer, für Neugierige
Dieselben Zahlen in deiner Sprache:
static long tries = 0;
static int Fewest(int[] coins, int amount){ if (amount == 0) { return 0; } int best = amount + 1; foreach (int coin in coins) { if (coin > amount) { break; } tries++; int count = Fewest(coins, amount - coin) + 1; best = Math.Min(best, count); } return best;}
static List<int> Change(int[] coins, int amount){ int[] best = new int[amount + 1]; int[] last = new int[amount + 1]; for (int a = 1; a <= amount; a++) { best[a] = amount + 1; foreach (int coin in coins) { if (coin > a) { break; } tries++; int count = best[a - coin] + 1; if (count < best[a]) { best[a] = count; last[a] = coin; } } } List<int> used = new List<int>(); for (int a = amount; a > 0; a -= last[a]) { used.Add(last[a]); } return used;}
int[] coins = { 1, 2, 5, 10, 20, 50, 100, 200 };foreach (int amount in new[] { 10, 20, 30 }){ tries = 0; Fewest(coins, amount); long plain = tries; tries = 0; Change(coins, amount); Console.WriteLine($"{amount} Cent: ohne Speicher {plain}, Tabelle {tries}");}10 Cent: ohne Speicher 309, Tabelle 2620 Cent: ohne Speicher 66281, Tabelle 6730 Cent: ohne Speicher 14158888, Tabelle 117Übung
Das Wechselgeld aus der Eingabe
Löse die Aufgabe in deinem Editor.
Wechselgeld. Lies das Wechselgeld in Cent ein und gib aus, wie viele Münzen der Automat herausgibt und welche. Nutze Change aus der Lektion.
4805 Münzen: 10 + 20 + 50 + 200 + 200Weitere Aufgaben
- Eine leere Röhre. Die Röhren für 1 und 2 Cent sind leer. Welche Beträge unter 1 € kann der Automat gar nicht zurückgeben? Woran erkennst du es in der Tabelle? (Tipp: Die Zelle bleibt
amount + 1.) - Die größte zuerst. Gib die Münzen von der größten zur kleinsten aus.
- Wie viele Arten mit Münzen. Auf wie viele Arten kannst du 1 € mit den Münzen von 1 bis 50 Cent zahlen? Und wenn die 1-€-Münze auch erlaubt ist?
Genauer
Unmögliches Wechselgeld und sehr große Zahlen
Zwei Dinge, die die Lektion übersprungen hat.
Genauer, für Neugierige
Wenn das Wechselgeld nicht zurückgegeben werden kann. Wenn die Röhren für 1 und 2 Cent leer sind, lassen sich 3 Cent mit nichts zurückgeben. Dann bleibt die Zelle amount + 1, weil kein Versuch besser ist. Und wenn last[a] 0 ist, würde der Weg zurück ewig auf der Stelle drehen. Vor dem Zurückgehen prüfst du also, ob best[amount] > amount gilt, und der Automat sagt „Kein Wechselgeld, bitte zahlen Sie passend“.
Die Zahl der Möglichkeiten wächst sehr schnell. Auf wie viele Arten kannst du 100 € nur mit Münzen zahlen (10.000 Cent, die acht Euro-Münzen)?
static long Ways(int[] notes, int amount){ long[] count = new long[amount + 1]; count[0] = 1; foreach (int note in notes) { for (int a = note; a <= amount; a++) { count[a] += count[a - note]; } } return count[amount];}
int[] coins = { 1, 2, 5, 10, 20, 50, 100, 200 };Console.WriteLine(Ways(coins, 10000));1133873304647601int reicht bis etwa 2,1 Milliarden und wäre längst übergelaufen, ohne Fehler. Deshalb ist die Tabelle long. Für noch größere Beträge reicht auch long nicht mehr (etwa 9,2 · 10¹⁸), und du brauchst `BigInteger` (System.Numerics).Die Tabelle in zwei Dimensionen. Das Zählen der Möglichkeiten ist eigentlich eine Tabelle „die ersten i Scheine × der Betrag“: Zelle (i, a) sagt, auf wie viele Arten sich a nur mit den ersten i Scheinen bilden lässt. Zeile i entsteht aus der Zeile darüber (ohne Schein i) und aus der Zelle links in derselben Zeile (mit einem weiteren Schein i). Das Programm behält nur eine Zeile und überschreibt sie von links nach rechts. Deshalb geht die äußere Schleife über die Scheine: Sie läuft durch die Zeilen. Dieselbe Idee, eine Zeile statt der ganzen Tabelle, kehrt im Rucksackproblem wieder.
Test