Algorithme glouton et problème du rendu de monnaie

[quentinzone]

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

[Bluedeep]

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 ) 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.

[quentinzone]

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

[Bluedeep]

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.

[Mexdy]

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

[Jimmy_]

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.

[Bluedeep]

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).