Le problème du rendu de monnaie
Un caissier qui rend la monnaie attrape la plus grande pièce qui rentre, puis la suivante, et pour les euros ou les dollars cela donne toujours le moins de pièces. Mais si les pièces valent 1, 3 et 4, la même habitude paie 6 avec trois pièces alors que deux suffiraient. La programmation dynamique trouve le vrai minimum pour n'importe quelles pièces.
Deux questions
Le problème du rendu de monnaie existe en deux versions. La première demande le minimum de pièces pour faire un montant exact ; c'est le problème du rendu de monnaie au sens strict. La seconde demande combien de combinaisons différentes de pièces le forment. Dans les deux cas, chaque sorte de pièce peut être utilisée autant de fois que l'on veut, et les deux se résolvent en construisant la réponse pour chaque montant à partir des réponses pour les montants plus petits.
Minimum de pièces, étape par étape
Faites une rangée de cases pour les montants de 0 jusqu'à la cible. Le montant 0 demande 0 pièce ; tous les autres partent de l'infini. Parcourez les montants dans l'ordre, et pour chacun essayez chaque pièce c qui rentre : la case du montant moins c, plus une pièce, est un candidat. Gardez le plus petit. Chaque case ne dépend que de cases à sa gauche, déjà définitives, donc un seul passage remplit la rangée.
Un exemple
Avec les pièces 1, 3 et 4 : le montant 1 demande 1 pièce, 2 en demande 2, 3 en demande 1 (une seule pièce de 3) et 4 en demande 1. Pour 5, on essaie 1 (4 demande 1, donc 2 pièces), 3 (2 demande 2, donc 3 pièces) et 4 (1 demande 1, donc 2 pièces) : le mieux est 2. Pour 6, on essaie 1 (5 demande 2, donc 3), 3 (3 demande 1, donc 2) et 4 (2 demande 2, donc 3) : le mieux est 2, avec 3 + 3. Le glouton aurait payé 4 + 1 + 1.
Compter les façons
Pour compter les combinaisons, ajoutez les pièces une par une. Avec seulement la première pièce, chaque montant se fait d'une seule façon ou pas du tout. Quand une nouvelle pièce c arrive, les façons de faire un montant a sont les anciennes façons, sans c, plus les façons de faire a − c avec c de nouveau permise, car chacune d'elles devient une façon de faire a en ajoutant une pièce c de plus. Avec les pièces 1, 2 et 5, il y a 4 façons de faire 5 : 5, 2 + 2 + 1, 2 + 1 + 1 + 1 et 1 + 1 + 1 + 1 + 1.
Quand le glouton suffit
Un système de pièces pour lequel le glouton donne toujours le moins de pièces est dit canonique. La plupart des monnaies modernes sont conçues ainsi, et en 1994 David Pearson a décrit un test qui vérifie un système de pièces en un nombre d'étapes qui ne croît que de façon polynomiale avec le nombre de pièces. Les anciennes pièces britanniques n'étaient pas canoniques : le glouton paie 48 pence avec une demi-couronne, un shilling et un sixpence, alors que deux florins suffiraient.
À vous de jouer
Ouvrez l'application, passez à la vue Tableau et appuyez sur Étape. En mode Minimum de pièces, la case orange est le montant en cours de calcul et la case bleue est le montant plus petit que laisse la pièce ; la ligne du dessous garde la dernière pièce, et à la fin on relit les pièces le long de cette ligne. Passez en mode Nombre de façons et regardez les nombres grandir ligne après ligne à mesure que chaque pièce arrive.
Questions fréquemment posées
Le problème du rendu de monnaie est-il un problème du sac à dos ?
Un proche parent. La version du minimum de pièces est un problème du sac à dos non borné où chaque pièce est un objet dont le poids est sa valeur faciale, le sac doit être rempli exactement, et le but est d'avoir le moins d'objets possible.
Quelle est la complexité en temps ?
O(k·A) pour k sortes de pièces et un montant A, dans les deux versions. Le tableau du minimum de pièces a A + 1 cases, et celui des façons (k + 1)·(A + 1), mais une seule ligne suffit si les cases sont mises à jour sur place.
Pourquoi compter les pièces dans un ordre fixe ?
Si chaque montant essayait chaque pièce, 1 + 2 et 2 + 1 compteraient pour deux façons. Ajouter les pièces une ligne à la fois signifie qu'une combinaison est toujours construite d'abord avec les pièces précédentes, si bien que chacune est comptée exactement une fois.
Peut-on relire les pièces pour le nombre de façons ?
Pas sous forme d'une réponse unique, car il y en a beaucoup. La version du minimum de pièces garde la dernière pièce de chaque montant, ce qui suffit pour reconstruire une meilleure combinaison.
Prêt à l'essayer ?
Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.
Essayer le rendu de monnaie