TermNSI/Programmation_Dynamique/RENDU_MONNAIE.md

# 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

<a rel="license" href="http://creativecommons.org/licenses/by-nc-sa/4.0/"><img alt="Licence Creative Commons" style="border-width:0" src="https://i.creativecommons.org/l/by-nc-sa/4.0/88x31.png" /></a> <br />Ce cours est mis à disposition selon les termes de la <a rel="license" href="http://creativecommons.org/licenses/by-nc-sa/4.0/">Licence Creative Commons Attribution - Pas d'Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 International</a>.