Münzwechsel (Coin change)

💡

Das Münzwechselproblem ist eines der bekanntesten Probleme in der Dynamischen Programmierung. Es zeigt sehr deutlich den Unterschied zwischen einem Greedy- und einem Dynamic-Programming-Ansatz und verdeutlicht, wie man fälschlicherweise glauben könnte, dass der Greedy-Ansatz genügt, obwohl er in Wahrheit nur ein suboptimales Ergebnis liefert und nicht das globale Problem löst.

Angenommen, das Münzsystem besteht aus n verschiedenen Münzen mit den positiven Werten . Ziel ist es, einen Gesamtbetrag x mit möglichst wenigen Münzen zu bilden.

Wenn zum Beispiel die Münzwerte sind und wir müssen 11 erreichen, so wäre die optimale Zusammenstellung 1 + 5 + 5 ⇒ 3 Münzen.

Eingabe

Die erste Zeile der Eingabe enthält zwei ganze Zahlen n (1 ≤ n ≤ 100) und x (1 ≤ x ≤ ).

Die nächste Zeile enthält n durch Leerzeichen getrennte Werte (1 ≤ ≤ ).

Ausgabe

Das Programm soll die minimale Anzahl an Münzen ausgeben, die nötig ist, um x zu bilden. Falls es nicht möglich ist, die gewünschte Summe x zu erzeugen, soll das Programm -1 ausgeben.

Beispiele

Eingabe	Ausgabe
3 11 1 5 7	3
3 12 1 5 7	2

Erklärung

11 → 1 + 5 + 5

12 → 5 + 7

Anleitung

Beachten Sie, dass der Greedy-Ansatz, bei dem immer die größte verfügbare Münze genommen wird, hier nicht funktioniert. Das erste Beispiel veranschaulicht das sehr gut. Um 11 zu bilden, würde man bei einem Greedy-Ansatz zunächst 7 nehmen ⇒ es bleiben 11-7 = 4 übrig. Deshalb benötigen wir 4 weitere Münzen (jeweils 1), was insgesamt 5 Münzen ergibt. In Wahrheit sind es aber nur 3 (5 + 5 + 1).

Wir definieren einen Zustand d[i], der die minimale Anzahl an Münzen repräsentiert, die benötigt wird, um die Summe i zu bilden. Wenn wir d sinnvoll initialisieren und alle Werte bis zur Zielsumme x aktualisieren, ist das Endergebnis einfach d[x].

Zu Beginn können wir alle Werte in d auf Infinity (bedeutet „nicht möglich“) setzen, mit Ausnahme von 0, das mit 0 Münzen erreichbar ist:

c = [...]
x = ...
d = [0] + [float('inf')] * x      # d[0] is 0 and d[1...x] inclusive is infinity

Dann versuchen wir für jede Zahl 1...x, die minimal benötigte Münzanzahl zu ermitteln. Angenommen, wir betrachten gerade die Zahl num, so überprüfen wir alle möglichen Münzen, um zu sehen, ob wir num unter Verwendung des Werts der aktuellen Münze und eines bereits erreichten früheren Zustands (num - $$c_i$$) erhalten können. Wenn sich dadurch ein besseres Ergebnis ergibt, aktualisieren wir d[num]. Konkret:

for num in range(1, x + 1):       # Über alle Zahlen von 1 bis x (einschließlich) iterieren
    for ci in c:                  # Versuch, d[num] mit allen verfügbaren Münzen zu verbessern
        if num - ci >= 0:         # Wenn es möglich ist, num mit der i-ten Münze zu bilden
            d[num] = min(d[num], d[num - ci] + 1)
print(d[x])

d[num] = min(d[num], d[num - ci] + 1) ist dabei der zentrale Schritt der Lösung. Wir versuchen in jeder Iteration, den Zustand von d[num] weiter zu verbessern, indem wir den früheren Zustand d[num - $$c_i$$] nutzen und 1 Münze (mit Wert ) hinzufügen.

Wenn alle Zahlen mit allen Münzen durchgegangen sind, entspricht der Wert d[x] der minimalen Anzahl an benötigten Münzen.

Sehen wir uns das Beispiel an:

c = [1, 5, 7] und x = 11

d = [0, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞]

num = 1

num = 2

num = 3

num = 4

num = 5

num = 6

num = 7

num = 8

num = 9

num = 10

num = 11

print(d[11]) ⇒ gibt 3 aus

Eingabe

Ausgabe

Beispiele

Erklärung

Anleitung

Constraints

To check your solution you need to sign in

Sign in to continue