8 Yen sollen mit Münzen zu 1 Yen, 4 Yen und 6 Yen bezahlt werden. Welche Aussage über die Zahl der Münzen, die ein Greedy-Algorithmus wählt (der zuerst so viele der größten Münze wie möglich verwendet), im Verhältnis zur kleinstmöglichen Münzzahl ist richtig?

Antwort: B. Der Greedy-Algorithmus verwendet 3 Münzen und verfehlt das Minimum von 2

Der Greedy-Algorithmus nimmt zuerst eine 6-Yen-Münze und zahlt die restlichen 2 Yen mit zwei 1-Yen-Münzen, insgesamt also 3 Münzen. Mit zwei 4-Yen-Münzen geht es aber mit nur 2. Weil ein Greedy-Algorithmus nur die jeweils im Moment beste Wahl aneinanderreiht, ist er bei manchen Münzsystemen nicht optimal. Die dynamische Programmierung, die eine Tabelle der kleinsten Münzzahl für jeden Betrag von 0 bis 8 Yen in aufsteigender Reihenfolge füllt, findet immer das Minimum. Bei Münzsystemen wie dem japanischen mit 1, 5, 10, 50, 100 und 500 Yen liefert der Greedy-Algorithmus stets das Minimum.