Greedy: Münzwechsel kanonisch

Kanonischer Münzwechsel mit Stückelungen 1, 5, 10, 25: immer die grösstmögliche Münze wählen. Für dieses System ist Greedy optimal.

Beliebige Stückelung (nicht gierig lösen): Coin Change [1].

Wo gebraucht

Alltagsbeispiel und Gegenbeispiel-Maschine: bei nicht-kanonischen Münzsystemen versagt Greedy. Trainiert Misstrauen gegenüber Lokalwahl ohne Beweis.

Vertiefung

Beim Greedy-Münzwechsel wird jeweils die grösste noch passende Münze gewählt. Für manche Münzsysteme liefert dies stets eine minimale Münzanzahl; solche Systeme heissen kanonisch. Die verbreiteten Euro-Nennwerte sind so gestaltet, dass die Regel für die üblichen ganzzahligen Beträge funktioniert.

Für beliebige Nennwerte ist die Regel nicht verlässlich. Ein Gegenbeispiel genügt, um die Allgemeingültigkeit zu widerlegen. Eine dynamische Programmierung kann dagegen für alle Beträge bis zum Ziel die kleinste Münzanzahl berechnen und dient auch zum systematischen Prüfen eines Münzsystems in einem endlichen Bereich.

Schwierigkeitsstufen

1. Die Greedy-Auswahl für ein gegebenes Münzsystem ausführen.
2. Ein Münzsystem mit einem Gegenbeispiel widerlegen.
3. Greedy-Ergebnis und DP-Optimum über viele Zielbeträge vergleichen.

Fallstricke

Dass die Regel bei mehreren getesteten Beträgen funktioniert, ist noch kein allgemeiner Beweis. Ausserdem müssen Erreichbarkeit und eine Münze mit Wert eins getrennt von der Optimalitätsfrage betrachtet werden.