Bonjour à tous,

voilà. Je bloque sur un algo qui semblait facile à première vue, mais qui s'avère plus ardu que ce que je pensais. Je vais essayer d'énoncer le problème le plus clairement possible:

- j'utiliserai le mot monnaie dans le sens "une pièce ou un billet"
- j'utiliserai le mot change dans le sens "différence entre l'argent inséré par l'utilisateur et le prix du produit"
- l'unité de base est le centime d'euro, on évite ainsi les flottants.
- j'ai une table de monnaies disponibles (appelons-là TDispo): pour chaque valeur (1, 2, 5, ...,20.000, 50.000 (50.000 cts = 500€) ) on a un nombre de monnaie disponible, c'est à dire que l'on peut utiliser pour rendre le change.
- C1: on doit calculer la façon optimale de rendre le change, c'est à dire avec le moins de monnaies possibles.
- C2: s'il est possible de rendre le change, on ne doit pas dire que ce n'est pas possible (contrainte plus importante qu'il n'y parait)

Pour l'instant j'ai un algoritthme "glouton" qui fonctionne à peu près, mais s'il respecte C1, parfois il ne respecte pas C2:

reste := change
Tant que reste>0
| prendre la plus grande monnaie possible (pgmp) dans TDispo telle que pgmp<reste
| si pgmp<0 (n'existe pas)
| | break
| sinon
| | res[pgmp]++
| | reste -= pgmp

Si reste == 0 c'est ok, sinon c'est pas ok
avec:
change = somme à retourner
res = table dans laquelle on stocke le résultat du calcul (sa structure est la même que TDispo )

Cet algo ne fonctionne pas, par exemple, dans le cas où on dois rendre 80cts et qu'on a disponible (TDisp): 1 piece de 50cts et 4 pieces de 20cts

J'ai bien cherché partout, mais j'ai rien trouvé d'exploitable. Si quelqu'un est plus habile que moi en recherche... ça doit bien se trouver non?

Sinon toute proposition est la bienvenue