Algo rendu de monnaie

Bonjour,

Je cherche un algo qui me permettrais de résoudre un rendu de monnaie.
j'ai pensé a l'algo glouton, mais je ne sais pas si il peut s'utiliser dans mon cas.
je m'explique :

imaginons que j'ai une somme de 21€ à rendre.
par contre je ne dispose que de pièce/billet de 5, 8, 10, 12 et 15€ (oui, c'est une monnaie particulière ! )
je voudrais alors trouver la solution qui rendrais la somme au mieux.
c'est a dire que je ne peux pas rendre moins, mais je ne veux pas rendre trop.
dans mon cas, je vais rendre 22€ soit 10+12.

Merci de m'apporter votre aide.

8+8+5 = 21 :)
Sinon as-tu une contrainte supplémentaire du genre minimiser le nombre de pièces utilisées ?

Ça ressemble beaucoup au problème du sac a dos : Lien Wikipedia

Argf!!! 21 est un movais exemple.
19 est un bon exemple.
car on ne peut que rembourser 20.
sinon, je n'ai pour le moment aucune contrainte si ce n'est que de connaitre la somme a rembourser et le calcul pour y arriver.

Je t'invite à consulter le lien que Hyperm4n a mis dans son message précédent et qui me semble pertinent.

J'y ai pensé et j'ai été voir cet algo.
je ne pense pas qu'il puisse s'appliquer a mon ca.

En effet dans ce algo, nous avons un nombre de boite defini.
hors dans mon cas, je peux mettre autant de BA que je veux.
dans l'algo sac a dos il est aussi nommé glouton si j'ai bien compris.
et lorsqu'on utilise une boite, elle est retirée de la liste.
jusqu'a epuisement de la liste.
ce qui n'est pas mon cas.

De plus mon cas n'est pas deterministe.
Je peux ne pas trouver la solution exacte et serais obliger parfois de me contenter de la solution la plus rapprochée.
exemple pour 19 ou je ne peux que rendre 20 et pas 19 tout rond.

Citation:

---

Envoyé par Matt_NewDev

De plus mon cas n'est pas deterministe.
Je peux ne pas trouver la solution exacte et serais obliger parfois de me contenter de la solution la plus rapprochée.
exemple pour 19 ou je ne peux que rendre 20 et pas 19 tout rond.

---

La littérature nous indique que pour toute valeur S supérieure à 19, on aura une solution exacte à ton problème (cf Frobenius Number).

Pour les valeurs S<19 sans solution exacte, on peut simplement recommencer avec S+1, S+2, ... jusqu'a trouver une solution. Au pire il faudra en tester 5 puisque c'est la précision de ton système monétaire.

Etant donné que tu n'as pas d'autre contrainte que trouver une solution exacte, une approche "glouton" avec backtrack semble être le plus naturel. Un simple odomètre décroissant fait l'affaire.