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