Bonjour à tous,
Je cherche désespérément un algorithme pour rendre des pièces de monnaie. Mais pas l'algorithme glouton... Je m'explique : j'ai à disposition un stock limité de pièces de valeur 1 à 9 et je souhaite rendre au mieux une certaine somme de monnaie.
Un exemple qui ne marche justement pas avec l'algorithme glouton : Je dois rendre 10.- et j'ai a disposition une pièce de 9, une pièce de 8 et une pièce de 2.
Glouton va sélectionner la pièce de 9, et n'ayant pas de pièce de 1 ne va pas pouvoir continuer, alors qu'il existe la solution 8 + 2...
Merci d'avance pour votre aide !
-----