Le Sac à Dos

Le problème

Pourquoi le glouton échoue (encore)

Formulation récursive

Version Top-Down (mémoïsation)

Version Bottom-Up (tableau 2D)

Visualisation du tableau

Reconstruction de la solution

Complexité

É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

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 ✓

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
)

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)

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

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]

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

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

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

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

i=0 (aucun objet)

i=1 (Tente 4kg,10)

i=2 (+Nourriture 3kg,7)

i=3 (+Trousse 2kg,6)

i=4 (+Lampe 1kg,3)

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.