# 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.
```python
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 `p` disponible telle que `p ≤ s` :
```
rendu(s) = 1 + min( rendu(s - p) ) pour toute pièce p ≤ s
```
On essaie toutes les pièces et on garde le minimum.
---
### Version naïve (récursive)
```python
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)
```python
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`.
```python
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.