Discussion :

[Matt_NewDev]

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.

[Franck Dernoncourt]

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

[Hyperm4n]

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

[Matt_NewDev]

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.

[Franck Dernoncourt]

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

[Matt_NewDev]

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.