Du hast das Kamel gefunden und bist nun in der Wüste unterwegs. Allerdings ist dir das Tier etwas unsympathisch, weswegen du beschließt es zu verkaufen. Glücklicherweise findest du tatsächlich einen Käufer, der bereit ist, den von dir geforderten Preis in Talern zu bezahlen.
Natürlich hat er den Betrag nicht passend dabei – du musst also Wechselgeld herausgeben. In der Wüste gibt es Münzen zu 1, 3, 4, 6, 10 und 50 Cent, und du hast von jeder Sorte mehr als genug.
Da du möglichst wenig Münzen herausgeben willst, wendest du die folgende Strategie an: Du gibst zunächst so viele wie möglich von der größten passenden Münze, dann von der nächstkleineren, und so weiter.
Führt diese Strategie für jeden möglichen Betrag an Wechselgeld immer zur geringstmöglichen Anzahl an Münzen?
