Pourquoi l'algorithme de changement de pièces par gourmandise ne fonctionne-t-il pas pour certains jeux de pièces ?

Question

Je comprends comment fonctionne l'algorithme gourmand pour le problème du changement de pièces (payer un montant spécifique avec le plus petit nombre possible de pièces) - il sélectionne toujours la pièce dont la dénomination est la plus grande et qui ne dépasse pas la somme restante - et qu'il trouve toujours la solution correcte pour des ensembles de pièces spécifiques.

Mais pour certains ensembles de pièces, il existe des sommes pour lesquelles l'algorithme gourmand échoue. Par exemple, pour l'ensemble {1, 15, 25} et la somme 30, l'algorithme gourmand choisit d'abord 25, laissant un reste de 5, puis cinq 1 pour un total de six pièces. Mais la solution avec le nombre minimal de pièces est de choisir deux fois 15.

Quelles conditions un ensemble de pièces doit-il remplir pour que l'algorithme glouton trouve la solution minimale pour toutes les sommes ?

Answer 1

Un ensemble qui forme un matroïde ( https://en.wikipedia.org/wiki/Matroid ) peut être utilisé pour résoudre le problème de l'échange de pièces de monnaie en utilisant l'approche gloutonne. En bref, un matroïde est une paire ordonnée M = (S,l) satisfaisant les conditions suivantes :

1. S est un ensemble fini non vide
2. l est une famille non vide de sous-ensembles de S, appelés sous-ensembles indépendants, telle que si B->l et A est un sous-ensemble de B, alors A -> l
3. Si A-> l, B-> l et |A| < |B|, alors il existe un élément x-> B-A tel que A U {x} ->l

Dans notre question de changement de pièces, S est un ensemble de toutes les pièces par ordre décroissant de valeur. Nous devons obtenir une valeur de V en utilisant un nombre minimal de pièces dans S.

Dans notre cas, l est un ensemble indépendant contenant tous les sous-ensembles tels que, pour chaque sous-ensemble, la somme des valeurs qu'ils contiennent est <=V

Si notre ensemble est un matroïde, alors notre réponse est l'ensemble maximal A dans l, dans lequel aucun x ne peut être ajouté.

Pour vérifier, nous voyons si les propriétés de la matroïde sont valables dans l'ensemble S = {25,15,1} où V = 30 Maintenant, il y a deux sous-ensembles dans S : A = {25} et B= {15,15} Puisque |A| < |B|, alors il existe un élément x-> B-A tel que A U {x} ->l (Selon 3) Ainsi, {25,15} devrait appartenir à l, mais c'est une contradiction puisque 25+15>30

Ainsi, S n'est pas un matroïde et donc l'approche gourmande ne fonctionnera pas sur lui.

Answer 2

Dans tous les cas où il n'existe aucune pièce dont la valeur, ajoutée à la dénomination la plus basse, est inférieure au double de celle de la dénomination immédiatement inférieure, l'algorithme de la cupidité fonctionne.

Par exemple, {1,2,3} fonctionne car [1,3] et [2,2] s'additionnent pour donner la même valeur. mais {1, 15, 25} ne fonctionne pas car (pour le changement 30) 15+15>25+1

Answer 3

Un système de pièces est canonique si le nombre de pièces rendu en monnaie par l'algorithme gourmand est optimal pour tous les montants.

Cet article propose un algorithme O(n^3) pour décider si un système de pièces est canonique, où n est le nombre de types de pièces différents.

Pour un système de pièces non canonique, il y a un montant c pour lequel l'algorithme glouton produit un nombre sous-optimal de pièces ; c est appelé un contre-exemple. Un système de pièces est serré si son plus petit contre-exemple est plus grand que la plus grande pièce unique.

Answer 4

Il s'agit d'un problème de récurrence. Étant donné un ensemble de pièces de monnaie {Cn, Cn-1, . . ., 1} de telle sorte que pour 1 <= k <= n, Ck > Ck-1 l'algorithme de la cupidité donnera le nombre minimal de pièces si Ck > Ck-1 + Ck-2 et pour la valeur V=(Ck + Ck-1) - 1 en appliquant l'algorithme de la cupidité au sous-ensemble de pièces {Ck, Ck-1, . . ., 1} donde Ck <= V donne moins de pièces que le nombre résultant de l'application de l'algorithme de la cupidité au sous-ensemble de pièces. {Ck-1, Ck-2, . . ., 1} .

Le test est simple : pour `1 <= k <= n, testez le nombre de pièces que l'algorithme Greedy donne pour une valeur de Ck + Ck-1 - 1. Faites-le pour les ensembles de pièces {Ck, Ck-1, . . ., 1} et {Ck-1, Ck-2, . . ., 1}. Si pour n'importe quel k, le second donne moins de pièces que le premier, l'algorithme de la cupidité ne fonctionnera pas pour ce jeu de pièces.

Par exemple, avec n=4, on considère l'ensemble de pièces {C4, C3, C2, 1} = {50,25,10,1}. Commençons par k=n=4, puis V = Cn + Cn-1 - 1 = 50+25-1 = 74 comme valeur test. Pour V=74, G{50,25,10,1} = 7 pièces. G{25, 10, 1} = 8 pièces. Jusqu'ici, tout va bien. Maintenant, laissons k=3. Alors V=25+10-1=34. G{25, 10, 1} = 10 pièces mais G{10, 1} = 7 pièces. Nous savons donc que l'algorithme de la cupidité ne minimisera pas le nombre de pièces pour l'ensemble de pièces {50,25,10,1}. Par contre, si nous ajoutons une pièce de 5 cents à cet ensemble de pièces, G{25, 10, 5, 1} = 6 et G{10, 5, 1} = 7. De même, pour V=10+5-1=14, nous obtenons G{10, 5, 1} = 5, mais G{5,1} = 6. Nous savons donc que le Greedy fonctionne pour {50,25,10,5,1}.

D'où la question suivante : quelle devrait être la dénomination des pièces, satisfaisant l'algorithme de la cupidité, qui aboutit au plus petit nombre de pièces dans le pire des cas pour toute valeur de 1 à 100 ? La réponse est assez simple : 100 pièces, chacune ayant une valeur différente de 1 à 100. On peut dire que ce n'est pas très utile, car il s'agit d'une recherche linéaire de pièces à chaque transaction. Sans parler du coût de la frappe de tant de dénominations différentes et de leur suivi.

Maintenant, si nous voulons d'abord minimiser le nombre de dénominations tout en minimisant ensuite le nombre de pièces résultant pour toute valeur de 1 à 100 produite par Greedy, alors les pièces en dénominations de puissances de 2 : {64, 32, 16, 8, 4, 2, 1} donnent un maximum de 6 pièces pour toute valeur 1:100 (le nombre maximum de 1 dans un nombre de sept bits dont la valeur est inférieure à 100 en décimal). Mais cela nécessite 7 dénominations de pièces. Le pire cas pour les cinq dénominations {50, 25, 10, 5, 1} est 8, ce qui se produit à V=94 et V=99. Les pièces en puissances de 3 {1, 3, 9, 27, 81} ne nécessitent également que 5 dénominations pour être utilisables par Greedy mais donnent également un pire cas de 8 pièces aux valeurs de 62 et 80. Enfin, l'utilisation de n'importe quel sous-ensemble de cinq dénominations de {64, 32, 16, 8, 4, 2, 1} qui ne peut exclure '1' et qui satisfait Greedy, donnera également un maximum de 8 pièces. Il y a donc un compromis linéaire. L'augmentation du nombre de dénominations de 5 à 7 réduit le nombre maximal de pièces nécessaires pour représenter toute valeur comprise entre 1 et 100 de 8 à 6, respectivement.

D'un autre côté, si vous voulez minimiser le nombre de pièces de monnaie échangé entre un acheteur et un vendeur, en supposant que chacun a au moins une pièce de chaque dénomination dans sa poche, alors ce problème est équivalent au plus petit nombre de poids qu'il faut pour équilibrer tout poids de 1 à N livres. Il s'avère que le plus petit nombre de pièces échangées lors d'un achat est atteint si les dénominations des pièces sont données en puissances de 3 : {1, 3, 9, 27, . . .} .

Voir https://puzzling.stackexchange.com/questions/186/whats-the-fewest-weights-you-need-to-balance-any-weight-from-1-to-40-pounds .

Answer 5

Eh bien, il faut vraiment reformuler cette question... L'algorithme greedy consiste essentiellement à essayer d'obtenir la valeur cible en utilisant les dénominations de pièces fournies. Toute modification apportée à l'algorithme greedy change simplement la façon d'atteindre la valeur cible. Il ne tient pas compte du nombre minimum de pièces utilisées..... Pour mieux dire, un coup sûr n'existe pas pour ce problème. Une pièce de plus grande valeur peut permettre d'atteindre rapidement la valeur cible, mais ce n'est pas un mouvement sûr. Exemple {50,47,51,2,9} pour obtenir 100 Le choix le plus avisé serait de prendre la pièce de plus grande valeur pour atteindre 100 plus rapidement... 51+47+2 C'est atteint, mais 50+50 devrait suffire...

Prenons {50,47,51,9} pour obtenir 100 S'il fait un choix gourmand de la pièce la plus haute 51 il a besoin de 49 dans l'ensemble. Il ne sait pas si c'est possible ou non. Il essaie d'atteindre 100 mais il ne peut pas Et changer le choix gourmand change simplement la façon d'atteindre 100. Ces types de problèmes créent un ensemble de solutions et forment une branche de l'arbre de décision.