:: Spoiler

Die Münzen müssen maximal einen Wert von 4,99 abdecken. Es lohnt sich, sich zunächst die 'Einer' anzugucken:
1
2
3 = 1 + 2
4 = 2 + 2
5
6 = 5 + 1
7 = 5 + 2
8 = 5 + 2 + 1
9 = 5 + 2 + 2
Man kann also mit 1×5ct, 2×2ct und 1×1ct jeden Betrag von 1 bis 9 Cent bezahlen.

Bei den Zehnern geht das analog: 1×50ct, 2×20ct und 1×10ct.

Die ganzen Euros von 1 bis 4 lassen sich dann mit 2×2€ und 1×1€ bezahlen.

In Summe komme ich so auf 4+4+3=11 Münzen mit einem Gesamtwert von 6,10 €

Irgendwie fehlt mir hier die Loss Funktion für das Optimierungsproblem, also irgendeine Gewichtung für die Anzahl Münzen oder den Wert der Münzen (oder meinetwegen Pareto). 499 1-Cent-Münzen sind doch zum Beispiel auch eine Lösung.