Rendu de Monnaie
Le problème
Énoncé : On dispose d'un ensemble de pièces de valeurs données (par exemple : 1€, 3€, 5€). On souhaite rendre une somme exacte en utilisant le moins de pièces possible.
Exemple : Rendre 11€ avec des pièces de 1€, 3€ et 5€.
Une solution possible : 5 + 3 + 3 = 11€ → 3 pièces
Pourquoi l'algorithme glouton ne suffit pas
En classe de Première, vous avez étudié l'algorithme glouton : à chaque étape, on choisit la plus grande pièce possible.
def rendu_glouton(pieces, somme):
pieces_triees = sorted(pieces, reverse=True)
nb_pieces = 0
for piece in pieces_triees:
while somme >= piece:
somme -= piece
nb_pieces += 1
return nb_pieces
Le glouton fonctionne bien avec les pièces européennes (1, 2, 5, 10, 20, 50 centimes...). Mais il échoue sur d'autres systèmes :
Contre-exemple : pièces = [1, 3, 4], somme = 6
- Glouton : 4 + 1 + 1 = 3 pièces
- Optimal : 3 + 3 = 2 pièces
Le glouton n'est pas optimal dans le cas général. La programmation dynamique, elle, trouve toujours la solution optimale.
Formulation récursive
Notons rendu(s) le nombre minimum de pièces pour rendre la somme s.
- Cas de base :
rendu(0) = 0(aucune pièce nécessaire pour rendre 0) - Cas récursif : pour chaque pièce
pdisponible telle quep ≤ s:
On essaie toutes les pièces et on garde le minimum.
Version naïve (récursive)
def rendu_naif(pieces, somme):
if somme == 0:
return 0
minimum = float('inf') # infini : pas encore de solution trouvée
for piece in pieces:
if piece <= somme:
nb = 1 + rendu_naif(pieces, somme - piece)
if nb < minimum:
minimum = nb
return minimum
Problème : Comme pour Fibonacci, de nombreux sous-problèmes sont recalculés plusieurs fois. La complexité est exponentielle.
Version Top-Down (mémoïsation)
def rendu_memo(pieces, somme):
memo = {}
def rendu(s):
if s == 0:
return 0
if s in memo:
return memo[s]
minimum = float('inf')
for piece in pieces:
if piece <= s:
nb = 1 + rendu(s - piece)
if nb < minimum:
minimum = nb
memo[s] = minimum
return memo[s]
return rendu(somme)
Chaque valeur de rendu(s) n'est calculée qu'une seule fois et mémorisée dans le dictionnaire.
Version Bottom-Up (tableau)
On remplit un tableau tableau où tableau[s] représente le nombre minimum de pièces pour rendre la somme s, en partant de s = 0 jusqu'à s = somme.
def rendu_bottom_up(pieces, somme):
tableau = [float('inf')] * (somme + 1)
tableau[0] = 0 # cas de base : 0 pièce pour rendre 0€
for s in range(1, somme + 1):
for piece in pieces:
if piece <= s:
if tableau[s - piece] + 1 < tableau[s]:
tableau[s] = tableau[s - piece] + 1
return tableau[somme]
Visualisation du tableau
Exemple : pièces = [1, 3, 4], somme = 6
On initialise : tableau = [0, ∞, ∞, ∞, ∞, ∞, ∞]
| s | Pièce testée | Calcul | tableau[s] |
|---|---|---|---|
| 1 | 1 | tableau[0] + 1 = 1 |
1 |
| 2 | 1 | tableau[1] + 1 = 2 |
2 |
| 3 | 1 | tableau[2] + 1 = 3 |
3 |
| 3 | 3 | tableau[0] + 1 = 1 |
1 |
| 4 | 1 | tableau[3] + 1 = 2 |
2 |
| 4 | 3 | tableau[1] + 1 = 2 |
2 |
| 4 | 4 | tableau[0] + 1 = 1 |
1 |
| 5 | 1 | tableau[4] + 1 = 2 |
2 |
| 5 | 3 | tableau[2] + 1 = 3 |
2 |
| 5 | 4 | tableau[1] + 1 = 2 |
2 |
| 6 | 1 | tableau[5] + 1 = 3 |
3 |
| 6 | 3 | tableau[3] + 1 = 2 |
2 |
| 6 | 4 | tableau[2] + 1 = 3 |
2 |
Résultat final : tableau[6] = 2 → 2 pièces (3 + 3). L'algorithme a bien trouvé la solution optimale que le glouton avait ratée.
Complexité
| Version | Temps | Espace |
|---|---|---|
| Naïve | exponentielle | O(somme) pile |
| Top-Down | O(n × somme) | O(somme) |
| Bottom-Up | O(n × somme) | O(somme) |
Avec n = nombre de pièces différentes.
Auteur : Florian Mathieu
Licence CC BY NC
Ce cours est mis à disposition selon les termes de la Licence Creative Commons Attribution - Pas d'Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 International.