Algorithmen und Datenstrukturen · Middle · Frage 43 von 75
Warum kann ein Greedy-Algorithmus beim Wechselgeld mit Münzen [1, 3, 4] und Betrag 6 scheitern?
- 1Greedy nimmt 4 + 1 + 1 (drei Münzen), 3 + 3 braucht nur zwei
- 2Greedy kann keine Beträge über der größten Münze behandeln
- 3Greedy scheitert immer, wenn Münzen keine Zweierpotenzen sind
Antwort zeigen
Richtige Antwort: Greedy nimmt 4 + 1 + 1 (drei Münzen), 3 + 3 braucht nur zwei
Erklärung
Die größte Münze zuerst zu nehmen ist für Standardwährungen optimal, aber nicht für beliebige Münzsätze. Dynamische Programmierung über Beträge (dp[a] = 1 + min dp[a - coin]) findet immer das Minimum.