Utopia

In Utopia will der Finanzminister die Ausgaben für das Prägen der Münzen reduzieren. Sein Ansatz:

• Bei Bezahlvorgängen sollen möglichst wenig Münzen gebraucht werden.
• Ein Bezahlvorgang besteht aus dem 'Reingeld' und dem 'Rückgeld'; der zu bezahlende Betrag ist Reingeld - Rückgeld.
• Die Münzwerte sollen nun so gestaltet werden, dass die minimal benötigte Zahl von Münzen für Rein- und Rückgeld zusammen möglichst klein ist, und zwar gemittelt über alle Kleinbeträge von 1 bis 100 Cent.

Für die ersten 6 Münzen der Eurowährung (1 Cent bis 50 Cent) ist dieser Mittelwert 2.96, und man braucht bis zu 5 Münzen für einen Bezahlvorgang. Zum Beispiel bezahlt man 87 Cent als Reingeld 50+20+10+5+2, Rückgeld 0 oder auch Reingeld 50+50, Rückgeld 10+2+1.
In Utopia ist der Mittwelwert 2.52, und man braucht maximal 3 Münzen. Jetzt zahlt man 87 Cent als Reingeld 43+43+1, Rückgeld 0. Und 20 Cent zahlt man als Reingeld 43+9, Rückgeld 32 (!!).
(Aus dem ACM International Collegiate Programming Contest 2002)