TermNSI/Programmation_Dynamique/SAC_A_DOS.md

# Le Sac à Dos

### Le problème

> **Énoncé** : Vous partez en randonnée avec un sac à dos d'une capacité maximale de **W kilogrammes**. Vous avez devant vous **n objets**, chacun ayant un **poids** et une **valeur**. Vous souhaitez maximiser la valeur totale des objets emportés, sans dépasser la capacité du sac.
>
> Contrainte : chaque objet est **pris entièrement ou laissé** (pas de fraction possible). C'est le problème du **sac à dos 0/1**.

**Exemple :**

| Objet | Poids | Valeur |
|-------|-------|--------|
| Tente | 4 kg | 10 |
| Nourriture | 3 kg | 7 |
| Trousse médicale | 2 kg | 6 |
| Lampe | 1 kg | 3 |

Capacité du sac : **5 kg**

---

### Pourquoi le glouton échoue (encore)

L'idée "prendre en priorité les objets avec le meilleur ratio valeur/poids" ne donne pas toujours la solution optimale.

| Objet | Poids | Valeur | Ratio valeur/poids |
|-------|-------|--------|--------------------|
| Tente | 4 | 10 | 2,5 |
| Nourriture | 3 | 7 | 2,33 |
| Trousse | 2 | 6 | 3,0 ← meilleur |
| Lampe | 1 | 3 | 3,0 ← meilleur |

Glouton (capacité 5) : Trousse (2kg, val 6) + Lampe (1kg, val 3) + ... reste 2kg, Nourriture trop lourde → **valeur = 9**

Optimal : Nourriture (3kg, val 7) + Trousse (2kg, val 6) = 5kg → **valeur = 13** ✓

---

### Formulation récursive

Notons `sac(i, w)` la valeur maximale qu'on peut atteindre en choisissant parmi les `i` premiers objets avec une capacité restante de `w`.

- **Cas de base :** `sac(0, w) = 0` (aucun objet disponible) et `sac(i, 0) = 0` (capacité épuisée)
- **Cas récursif :** Pour l'objet `i` de poids `p_i` et de valeur `v_i` :
  - Si `p_i > w` : on ne peut pas le prendre → `sac(i, w) = sac(i-1, w)`
  - Sinon, on choisit le meilleur entre le prendre et ne pas le prendre :

```
sac(i, w) = max(
    sac(i-1, w),              ← on ne prend pas l'objet i
    v_i + sac(i-1, w - p_i)  ← on prend l'objet i
)
```

---

### Version Top-Down (mémoïsation)

```python
def sac_memo(objets, capacite):
    """
    objets : liste de tuples (poids, valeur)
    capacite : capacité maximale du sac (entier)
    """
    n = len(objets)
    memo = {}

    def sac(i, w):
        if i == 0 or w == 0:
            return 0
        if (i, w) in memo:
            return memo[(i, w)]
        poids, valeur = objets[i - 1]
        if poids > w:
            resultat = sac(i - 1, w)
        else:
            sans_objet = sac(i - 1, w)
            avec_objet = valeur + sac(i - 1, w - poids)
            resultat = max(sans_objet, avec_objet)
        memo[(i, w)] = resultat
        return resultat

    return sac(n, capacite)
```

---

### Version Bottom-Up (tableau 2D)

On construit un tableau `tableau[i][w]` représentant la valeur maximale avec les `i` premiers objets et une capacité `w`.

```python
def sac_bottom_up(objets, capacite):
    """
    objets : liste de tuples (poids, valeur)
    capacite : capacité maximale du sac (entier)
    """
    n = len(objets)
    # tableau[i][w] = valeur max avec les i premiers objets, capacité w
    tableau = [[0] * (capacite + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        poids, valeur = objets[i - 1]
        for w in range(capacite + 1):
            if poids > w:
                tableau[i][w] = tableau[i - 1][w]
            else:
                tableau[i][w] = max(
                    tableau[i - 1][w],
                    valeur + tableau[i - 1][w - poids]
                )

    return tableau[n][capacite]
```

---

### Visualisation du tableau

**Exemple :** objets = [(4,10), (3,7), (2,6), (1,3)], capacité = 5

`tableau[i][w]` = valeur maximale avec les `i` premiers objets et capacité `w`

|   | w=0 | w=1 | w=2 | w=3 | w=4 | w=5 |
|---|-----|-----|-----|-----|-----|-----|
| i=0 (aucun objet) | 0 | 0 | 0 | 0 | 0 | 0 |
| i=1 (Tente 4kg,10) | 0 | 0 | 0 | 0 | 10 | 10 |
| i=2 (+Nourriture 3kg,7) | 0 | 0 | 0 | 7 | 10 | 10 |
| i=3 (+Trousse 2kg,6) | 0 | 0 | 6 | 7 | 10 | 13 |
| i=4 (+Lampe 1kg,3) | 0 | 3 | 6 | 9 | 10 | **13** |

La valeur optimale est `tableau[4][5] = 13`.

---

### Reconstruction de la solution

Le tableau nous donne la valeur optimale, mais pas quels objets choisir. Pour le savoir, on **remonte le tableau** depuis `tableau[n][capacite]` :

```python
def sac_reconstruction(objets, capacite):
    """
    Retourne (valeur_max, liste_objets_choisis)
    """
    n = len(objets)
    tableau = [[0] * (capacite + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        poids, valeur = objets[i - 1]
        for w in range(capacite + 1):
            if poids > w:
                tableau[i][w] = tableau[i - 1][w]
            else:
                tableau[i][w] = max(
                    tableau[i - 1][w],
                    valeur + tableau[i - 1][w - poids]
                )

    # Reconstruction : on remonte le tableau
    objets_choisis = []
    w = capacite
    for i in range(n, 0, -1):
        # Si la valeur a changé entre i et i-1, c'est qu'on a pris l'objet i
        if tableau[i][w] != tableau[i - 1][w]:
            objets_choisis.append(objets[i - 1])
            w -= objets[i - 1][0]    # on réduit la capacité restante

    return tableau[n][capacite], objets_choisis


# Exemple d'utilisation
objets = [(4, 10), (3, 7), (2, 6), (1, 3)]
valeur, choix = sac_reconstruction(objets, 5)
print(f"Valeur maximale : {valeur}")
print(f"Objets choisis : {choix}")
# Valeur maximale : 13
# Objets choisis : [(2, 6), (3, 7)]  → Trousse + Nourriture
```

---

### Complexité

| Version | Temps | Espace |
|---------|-------|--------|
| Naïve | O(2ⁿ) | O(n) pile |
| Top-Down | O(n × W) | O(n × W) |
| Bottom-Up | O(n × W) | O(n × W) |

Avec n = nombre d'objets, W = capacité du sac.

> **Attention :** si W est très grand, cette complexité peut devenir prohibitive. Le sac à dos 0/1 est un problème NP-difficile — la programmation dynamique le résout efficacement pour des valeurs raisonnables de W.

---

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>.