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 un Algorithme  Glouton est optimal pour un ensemble de pièce donné.
 
Merci de votre aide

Un Algorithme Glouton, prend la pièce de la plus grande valeur autant de fois qu'il est possible de la prendre pour ne pas dépasser la somme souhaité, puis  prend la seconde valeur autant de fois qu'il est possible de la prendre pour ne pas dépasser le reste la somme souhaité etc ... etc ...
 
L'idée c'est d'utiliser le moins de pièce possible. Je cherche à construire un algorithme qui détermine si oui on utilise le moins de pièce possible avec un Algorithme Glouton
En entré : les valeurs des pièces
En sortie : si c'est optimal ou non
 
2) pour le moment, j'ai pas de code , je recherche plutôt a quelle condition un Algorithme Glouton est optimal. Merci

Je connais une technique, qui permet de distribuer une somme selon un nombre de valeur pour obtenir la somme.
 
Il faut faire un tableau des valeur et commencer par enlever à la somme le plus grand nombre de valeur la plus grande, puis passer à celles plus petites dans l'ordre décroissant, jusqu'à obtenir 0 ou un reste.

 
 
Il y a une condition suffisante (mais je ne sais pas si elle est nécessaire) qui dit que l'algorithme glouton donne la solution optimale (c'est-à-dire avec le moins de pièces possibles) si chaque pièce de la suite est au moins 2 fois plus grande que la précédente.
 
Exemple, si on dispose de pièces de 1 centime, 2 centimes, 5 centimes, 10 centimes, 20 centimes, 50 centimes, 1 euro, 2 euros et 5 euros, alors on aura toujours la solution optimale.  
 
Par contre si on dispose de pièces de 5 centimes, 20 centimes, 25 centimes et 40 centimes et qu'on doit former la somme de 50 centimes, l'algorithme glouton retournera normalement (40 + 5 + 5) alors que la solution optimale aurait été (25 + 25).
 
Il est assez facile de prouver que cette condition est suffisante (exercice laissé au lecteur   ) mais pour l'instant je ne vois pas comment prouver qu'elle est nécessaire, mais bon c'est certain que ça a déjà été étudié, faudrait juste pas avoir la flemme.
 
Atchao bonsoir.

C'est faux: je prends comme suite de pièces des pièces de valeur 1, 5 et 11.
Chaque pièce de la suite est au moins 2 fois plus grande que la précédente.
Et si je fais l'algo glouton pour la valeur 15, je dois faire 11+1+1+1+1 soit 5 pièces, ce qui est clairement pas optimal puisque 3 pièces suffisaient, en faisant 5+5+5.
A+,

Bon déjà, l'énoncé est mal posé:
L'algo glouton doit il être optimal pour toute somme possible, ou bien pour un ensemble de valeurs somme cibles déterminé?
Dans le premier cas, 1 doit obligatoirement faire partie des valeurs des pièces, et dans le second, je n'ai aucune idée de l'existence d'un critère général .  
 
Si on suppose qu'on est dans le premier cas, intuitivement, je dirais que si on a une suite dans laquelle pour toute succession de 3 valeurs consécutives, 1 < a < b < c, on a a+c = 2b, alors l'algo glouton devrait être optimal, mais c'est clairement pas une condition nécessaire, car les suites (1, k, k^2, k^3, ..., k^N) sont elles aussi avec un algo glouton optimal il me semble.
J'ai l'impression que les suites dans laquelle pour toute succession de 2 valeurs consécutives, 1 < a < b on a b <= 2*a sont elles aussi avec un algo glouton optimal.
 
A+,

http://www.prologin.org/training/c [...] relaxation

Ben au moins, avec cet énoncé, il est clair qu'on est dans le premier cas, ce qui ne l'était pas avec ton énoncé:

En plus il y est pas demandé si l'algo glouton est systématiquement optimal, mais optimal pour une valeur donnée.
A+,

Aux cours de mes nombreuse recherche j'ai trouvé ça //fr.wikipedia.org/wiki/Probl%C3%A8me_du_rendu_de_monnaie
Ca m'aide pas vraiment parce que le paragraphe sur l’algorithme de Pearson est incomplet.