Ich verstehe, wie der gierige Algorithmus für das Problem des Münzenwechsels (einen bestimmten Betrag mit der minimal möglichen Anzahl von Münzen bezahlen) funktioniert - er wählt immer die Münze mit dem größten Nennwert aus, der die verbleibende Summe nicht überschreitet - und dass er immer die richtige Lösung für findet bestimmte Münzsätze.

Bei einigen Münzsätzen gibt es jedoch Beträge, bei denen der Greedy-Algorithmus fehlschlägt. Zum Beispiel für das Set{1, 15, 25} und die Summe 30 wählt der gierige Algorithmus zuerst 25, wobei ein Rest von 5 und dann fünf Einsen für insgesamt sechs Münzen übrig bleiben. Die Lösung mit der minimalen Anzahl von Münzen ist jedoch, zweimal 15 zu wählen.

Welche Bedingungen muss ein Münzsatz erfüllen, damit der gierige Algorithmus für alle Summen die minimale Lösung findet?