Wechselgeldproblem
Lektion 8 von 15 im Kurs Dynamische Programmierung 101 von Coddy.
Das Münzwechselproblem (Coin Change Problem) ist ein klassisches Problem der dynamischen Programmierung. Gegeben ist ein Satz von Münzen mit verschiedenen Nennwerten und ein Gesamtbetrag. Die Aufgabe besteht darin, die minimale Anzahl an Münzen zu finden, die benötigt wird, um den gegebenen Betrag zu erreichen.
Angenommen, wir haben zum Beispiel Münzen mit den Nennwerten [1, 5, 10] und wollen den Betrag 15 erreichen. Die minimale Anzahl der benötigten Münzen wäre 2 (eine 10er-Münze und eine 5er-Münze).
Um dieses Problem mithilfe der dynamischen Programmierung zu lösen, können wir eine Tabelle erstellen, in der die Zeilen die Nennwerte der Münzen und die Spalten die Beträge von 0 bis zum angegebenen Gesamtbetrag darstellen. Wir füllen die Tabelle dann nach dem Bottom-up-Prinzip aus, indem wir die minimale Anzahl an Münzen berechnen, die erforderlich ist, um jeden Betrag unter Verwendung der Münzen jeder Stückelung zu erreichen.
Aufgabe
MittelSchreiben Sie ein Programm, das zwei Eingaben entgegennimmt: eine Liste von Münznennwerten und einen Zielbetrag, und die minimale Anzahl an Münzen zurückgibt, die benötigt werden, um den Zielbetrag zu erreichen.
Zum Beispiel sollte für die Nennwerte [1, 5, 10] und den Zielbetrag 15 die Ausgabe 2 sein.
Probier es selbst
def min_coins(coins, target):
# Code hier schreibenAlle Lektionen in Dynamische Programmierung 101
3Algorithmen der dynamischen Programmierung
Längste gemeinsame TeilsequenzRucksackproblemWechselgeldproblemEdit-Distanz