Meno monete possibili

[kobeilprofeta]

Penso che sia noto come problema. Debbo raggiungere una determinata cifra usando meno monete (banconote) possibili.

Voglio capire quando valga la legge "uso sempre la più grande possibile". (*)

Ovviamente questa cosa non vale sempre, un facile controesempio è:
costruire 6€ avendo a disposizione: 5, 3, 0.01

Con le nostre taglie di euro questa cosa ad occhio sembra valere (non so dimostrarlo). Qualcuno è in grado di dire quando vale la (*) e quando no?

[Rigel]

La (*) è, in buona sostanza, l'algoritmo greedy per il problema dello zaino (semplificato in questo caso).
Come è noto, quest'algoritmo non è ottimale (e infatti non fornisce la soluzione ottimale nel tuo esempio).
Non so se nel caso da te esposto sia noto un algoritmo ottimale.