5
Das Problem macht n Cents Änderung mit Vierteln, Groschen, Nickel und Pennies, und mit der geringsten Gesamtanzahl von Münzen. In dem speziellen Fall, in dem die vier Nennwerte Viertel, Groschen, Nickel und Pennies sind, haben wir c1 = 25, c2 = 10, c3 = 5 und c4 = 1.Münzwechsel: Gieriger Ansatz
nur Viertel, Groschen, und ein paar Cent (und keine Nickels) zu verwenden, der greedy-Algorithmus würde Änderung machen für 30 Cent mit sechs Münzen -a Quartal und fünf Cent-während wir drei Münzen verwendet haben könnten, nämlich drei Groschen.
Angesichts einer Reihe von Nennungen, wie können wir sagen, ob Greedy-Ansatz eine optimale Lösung schafft?
Fragen Sie, wie Sie das lösen können? Es gibt eine einfache dynamische Programmierlösung dafür. –
@AmiTavory Ich las Diskrete Mathematik und es ist Anwendungen von Rosen und er hatte dieses Beispiel in seinem Buch zitiert. Auch ich dachte, das Problem sei dem Knapsack-Problem ähnlich und wurde von einer gierigen Lösung überrascht. – bhavya
Sorry, aber (zumindest) verstehe ich einfach nicht, was genau du fragst. Vielleicht könnten Sie Ihre Frage etwas bearbeiten. –