Problème du rendu de monnaie
Introduction du problème
On gère un magasin où les clients peuvent payer en pièces et billets en euros. On souhaite trouver une solution permettant de rendre la monnaie d'un paiement en utilisant le moins de pièces possibles.
On considère les pièces suivantes : 1€, 2€, 5€.
Quels sont les cas possibles si on doit rendre 8€ ?
Combinaison | Pièces |
\(8 \times 1 \text{€}\) | 8 |
\(6 \times 1 \text{€} + 1 \times 2 \text{€}\) | 7 |
\(4 \times 1 \text{€} + 2 \times 2 \text{€}\) | 6 |
\(2 \times 1 \text{€} + 3 \times 2 \text{€}\) | 5 |
\(4 \times 2 \text{€}\) | 4 |
\(3 \times 1 \text{€} + 1 \times 5 \text{€}\) | 4 |
\(1 \times 1 \text{€} + 1 \times 2 \text{€} + 1 \times 5 \text{€}\) | 3 |
Définition : Problème du rendu de monnaie
Entrées :
Liste
monnaie: liste des pièces à notre disposition.Entier
somme: Somme à obtenir en utilisant des pièces demonnaie.
Sorties :
Entier : Nombre miimal de pièces à rendre.
Méthode : Algorithme glouton
Le but de l'algorithme glouton est de toujours rendre la plus grosse pièce possible, jusqu'à arriver à 0€.
Par exemple, pour rendre 8€ :
La plus grosse pièce possible est 5€. Il reste 3€ à rendre.
La plus grosse pièce possible est 2€. Il reste 1€ à rendre.
La plus grosse pièce possible est 1€. Il reste 0€ à rendre.
L'algorithme glouton renvoit un total de 3 pièces, qui est le résultat optimal.
Remarque : Optimalité du rendu de monnaie glouton en euros
Ce problème, en fonction du système de monnaie utilisé, peut être résolu de façon optimale grâce à un algorithme glouton. Dans ce cas, on parle de système de monnaie canonique.
Prenons l'exemple du système d'euros :
Dans le cas des pièces (ou billets) de 1€, 5€, 10€, 50€ et 100€, ils ne peuvent être utilisés qu'une seule fois de manière optimale. En effet, si on rend deux pièces de 1€, alors on peut simplifier ce résultat par une pièce de 2€ (ce que va faire l'algorithme glouton).
Dans le cas des pièces (ou billets) de 2€ et 20€, ils ne peuvent être utilisés que deux fois de manière optimale. En effet, si on rend trois pièces de 2€, alors on peut simplifier ce résultat par une pièce de 1€ et un bilelt de 5€ (ce que va faire l'algorithme glouton).