Algorithme glouton et problème du rendu de monnaie

Bonjour à tous,
J'ai une petit problème ...

Je dispose de N pièces en nombre illimité, des pièces de valeur (a1 , a2 , . . . , an )

Je veux construire un algorithme qui détermine si l'Algorithme de Glouton est optimal pour un ensemble de pièce donné.

Merci de votre aide

Amusant.

Sans réfléchir à fond je dirai que l'algorithme glouton (c'est pas un nom propre : il n'a pas été inventé par un monsieur appelé Glouton :D ) doit être optimal si la différence de valeur entre deux pièces de rang N et N+1 est toujours inférieur à la différence entre celles de rang N+1 et N+2 (considérant les pièces rangées en ordre croissant de valeur).

Mais je répond par intuition, ne m'étant pas penché sur la question.

En tout cas, il me semble qu'il n'est pas optimal si cette condition n'est pas rempli.

Et bien entendu, on suppose que tu considères que l'optimal est celui qui minimise le nombre de pièces pour une valeur globale donnée.

Merci beaucoup ! Ça ma permis d’avancer mais ce n'est malheureusement pas l'unique condition

Ne connaissant pas du tout la question, comme je l'ai écrit au dessus, j'ai fait une rapide recherche, et la solution sur l'"optimalité" de l'algorithme glouton dans le cadre du problème dit du "rendu de monnaie" est .... sur wikipédia.

http://fr.wikipedia.org/wiki/Algorithme_glouton
http://fr.wikipedia.org/wiki/Probl%C...ndu_de_monnaie

Dans le deuxième lien, tu as tout ce qu'il te faut.

Salut tout le monde !!
Bon j'ai un mini projet a realiser , sur le probleme de rendu de monnaie partie dynamique , j'ai fait l'lagorithme dynamique mais quand j'ai fait la traduction en C il ne marche pas , je vous prie de m'aider .
L'algorithme consiste a rendre un couple composé d'une part par le minimum de pieces d'une façon optimale et d'une autre un tableau indiquant les pieces a rendre ! voilà l'algorithme et le C

Algorithme dynamique :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

Fonction P(S,n) Début Si n=0 alors retourner +8 ; Sinon Si n=1 et V[1]=1 retourner S ; Sinon Si S=0 alors retourner 0 ; Sinon Pour i= 1 à n faire Si S<V[i] alors P(S,i)= P(S,i-1) ; Nmin= P(S,i) ; Sinon P(S,i)= min(p(S,i-1) ;P(S-V[i]),i)+1) ; Nmin= P(S,i) ; Fin Si Fin Pour Fin Si Fin Si Fin Si Retourner Nmin ; Fin   Fonction R(V,P,S) K= 1 ; Si V[X]*P(S-V[i],X)> S alors X= X-1 ; Fin Si Tant que (V[X]*P(S-V[i], X)<= S ) et ( k <= Nmin ) faire j ? P(S-V[i],X) ; Répéter T[k] = V[X] ; k = k+1 ; j = j-1 ; Jusqu’a : j=1 X = X-1 ; Fin Tant que Fin

---

Ne cherche pas à faire l'algorithme optimal, c'est trop compliqué à faire.
Tous les automates utilisent l'algorithme glouton, en commençant par rendre la pièce ou le billet maximal.

Citation:

---

Envoyé par Jimmy_

Tous les automates utilisent l'algorithme glouton, en commençant par rendre la pièce ou le billet maximal.

---

L'algorithme glouton est l'algorithme optimal sur les systèmes monétaires canoniques.
Or, depuis 72 ( ou 71 ou 73 ? bref, l'année de la réforme monétaire britannique), tous les systèmes monétaires occidentaux sont canoniques (pour les autres, je ne sais pas).