201 lines
6.3 KiB
Markdown
201 lines
6.3 KiB
Markdown
# 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>.
|