49. Exemple Glouton : Problème du Rendu de Monnaie (Cas Simple)

Le Problème du Rendu de Monnaie demande : étant donné un ensemble de dénominations de pièces, quel est le nombre minimum de pièces requis pour atteindre un montant donné ?

Système de Pièces Américain (Où l'approche Gloutonne Fonctionne)

Dans la monnaie américaine standard (1, 5, 10, 25 cents), l'approche gloutonne (choisir toujours la plus grande dénomination possible) garantit le nombre minimum de pièces.

Objectif : 41 cents

1. Prendre la plus grande pièce <= 41 : 25. Restant : 16.
2. Prendre la plus grande pièce <= 16 : 10. Restant : 6.
3. Prendre la plus grande pièce <= 6 : 5. Restant : 1.
4. Prendre la plus grande pièce <= 1 : 1. Restant : 0.

Total des pièces : 4. C'est la solution optimale.

L'Algorithme

python coins = [25, 10, 5, 1] # Assumes sorted descending def greedy_change(amount, coins): count = 0 for coin in coins: while amount >= coin: amount -= coin count += 1 return count