Das Münzwechselproblem

Wer an der Kasse Wechselgeld herausgibt, greift zur größten passenden Münze, dann zur nächsten, und bei Euro oder Dollar ergibt das immer die wenigsten Münzen. Ändert man die Münzen aber auf 1, 3 und 4, zahlt dieselbe Gewohnheit 6 mit drei Münzen, obwohl zwei reichen würden. Dynamische Programmierung findet für beliebige Münzen das echte Minimum.

Eine Reihe von Beträgen, jeder mit den wenigsten Münzen, die ihn bilden, über Münzen in drei verschiedenen Größen
Eine Reihe von Beträgen, jeder mit den wenigsten Münzen, die ihn bilden, über Münzen in drei verschiedenen Größen

Zwei Fragen

Das Münzwechselproblem gibt es in zwei Varianten. Die erste fragt nach den wenigsten Münzen für einen genauen Betrag; sie heißt auch Wechselgeldproblem. Die zweite fragt, wie viele verschiedene Münzkombinationen ihn ergeben. In beiden darf jede Münzsorte beliebig oft verwendet werden, und beide werden gelöst, indem man die Antwort für jeden Betrag aus den Antworten für kleinere Beträge aufbaut.

Wenigste Münzen, Schritt für Schritt

Legen Sie eine Reihe von Zellen für die Beträge von 0 bis zum Ziel an. Betrag 0 braucht 0 Münzen; jeder andere Betrag beginnt bei unendlich. Gehen Sie die Beträge der Reihe nach durch und probieren Sie für jeden jede passende Münze c: Die Zelle für den Betrag minus c, plus eine Münze, ist ein Kandidat. Behalten Sie den kleinsten. Jede Zelle hängt nur von Zellen links von ihr ab, die schon feststehen, also füllt ein einziger Durchgang die Reihe.

Ein Beispiel

Mit den Münzen 1, 3 und 4: Betrag 1 braucht 1 Münze, 2 braucht 2, 3 braucht 1 (eine einzelne 3) und 4 braucht 1. Für 5 probiert man 1 (4 braucht 1, also 2 Münzen), 3 (2 braucht 2, also 3 Münzen) und 4 (1 braucht 1, also 2 Münzen): Am besten sind 2. Für 6 probiert man 1 (5 braucht 2, also 3), 3 (3 braucht 1, also 2) und 4 (2 braucht 2, also 3): Am besten sind 2, mit 3 + 3. Greedy hätte 4 + 1 + 1 gezahlt.

Die Möglichkeiten zählen

Um Kombinationen zu zählen, nimmt man die Münzen einzeln hinzu. Mit nur der ersten Münze lässt sich jeder Betrag auf genau eine Weise bilden oder gar nicht. Kommt eine neue Münze c hinzu, sind die Möglichkeiten für einen Betrag a die alten Möglichkeiten ohne c plus die Möglichkeiten für a − c, bei denen c wieder erlaubt ist, denn jede davon wird durch eine weitere Münze c zu einer Möglichkeit für a. Mit den Münzen 1, 2 und 5 gibt es 4 Möglichkeiten für 5: 5, 2 + 2 + 1, 2 + 1 + 1 + 1 und 1 + 1 + 1 + 1 + 1.

Wann Greedy genügt

Ein Münzsystem, bei dem Greedy immer die wenigsten Münzen liefert, heißt kanonisch. Die meisten modernen Währungen sind so angelegt, und 1994 beschrieb David Pearson einen Test, der ein Münzsystem in einer Zahl von Schritten prüft, die nur polynomiell mit der Anzahl der Münzen wächst. Die alten britischen Münzen waren nicht kanonisch: Greedy zahlt 48 Pence als eine Half Crown, einen Shilling und einen Sixpence, wo zwei Florin reichen würden.

Selbst ausprobieren

Öffnen Sie die App, wechseln Sie zur Ansicht Tabelle und drücken Sie Schritt. Im Modus Wenigste Münzen ist die orange Zelle der Betrag, der gerade berechnet wird, und die blaue Zelle der kleinere Betrag, den die Münze übrig lässt; die Zeile darunter hält die letzte Münze fest, und am Ende werden die Münzen an ihr entlang zurückgelesen. Wechseln Sie zu Anzahl der Möglichkeiten und sehen Sie zu, wie die Zahlen Zeile für Zeile wachsen, während eine Münze nach der anderen hinzukommt.

Häufig gestellte Fragen

Ist das Münzwechselproblem ein Rucksackproblem?

Ein enger Verwandter. Die Variante mit den wenigsten Münzen ist ein unbeschränktes Rucksackproblem, bei dem jede Münze ein Gegenstand ist, dessen Gewicht ihr Nennwert ist, der Rucksack genau gefüllt werden muss und das Ziel möglichst wenige Gegenstände sind.

Wie hoch ist die Zeitkomplexität?

O(k·A) für k Münzsorten und einen Betrag A, in beiden Varianten. Die Tabelle für die wenigsten Münzen hat A + 1 Zellen, die Tabelle für die Möglichkeiten (k + 1)·(A + 1), wobei eine einzige Zeile genügt, wenn die Zellen an Ort und Stelle aktualisiert werden.

Warum werden die Münzen in fester Reihenfolge gezählt?

Würde jeder Betrag jede Münze probieren, würden 1 + 2 und 2 + 1 als zwei Möglichkeiten gezählt. Werden die Münzen Zeile für Zeile hinzugenommen, wird eine Kombination immer zuerst aus den früheren Münzen aufgebaut, sodass jede genau einmal gezählt wird.

Lassen sich die Münzen auch für die Anzahl der Möglichkeiten zurücklesen?

Nicht als eine einzige Antwort, denn es gibt viele. Die Variante mit den wenigsten Münzen speichert die letzte Münze jedes Betrags, und das reicht, um eine beste Kombination zu rekonstruieren.

Bereit, es auszuprobieren?

Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.

Münzwechsel ausprobieren