Problème du sac à dos 0/1

Étant donnés des objets avec des poids entiers non négatifs $w_i$ et des valeurs $v_i$, choisissez chaque objet au plus une fois pour maximiser la valeur totale sous une capacité $C$ :

$$\max \sum_i v_i x_i \quad\text{subject to}\quad \sum_i w_i x_i \le C,\qquad x_i\in\{0,1\}.$$

État et transition

Soit dp[c] la meilleure valeur réalisable avec les objets traités et la capacité c. Pour chaque objet, mettez à jour les capacités par ordre décroissant :

def knapsack(weights: list[int], values: list[int], capacity: int) -> int:
    dp = [0] * (capacity + 1)
    for weight, value in zip(weights, values, strict=True):
        for current in range(capacity, weight - 1, -1):
            dp[current] = max(dp[current], dp[current - weight] + value)
    return dp[capacity]

L'ordre décroissant garantit que dp[current - weight] appartient toujours à la couche d'objets précédente, de sorte qu'un objet ne puisse pas être réutilisé. L'ordre croissant implémente au contraire une transition à usage non borné.

Coût et interprétation

• Temps : $O(n(C+1))$.
• Espace pour la valeur uniquement : $O(C+1)$.
• La reconstruction des objets sélectionnés nécessite de stocker les décisions ou de recalculer.

Ce temps d'exécution est pseudo-polynomial : il est polynomial par rapport à la capacité numérique $C$, et non par rapport au nombre de bits nécessaires pour coder $C$.

Les variantes sont des problèmes différents

• Le sac à dos fractionnaire permet de fractionner les objets et admet une solution gloutonne.
• Le sac à dos non borné permet une réutilisation illimitée et modifie l'ordre de mise à jour.
• Le sac à dos borné fournit une multiplicité finie par objet.

Précisez la variante avant de choisir une récurrence.

Pourquoi comparer les deux choix

Avant compression, D[i,c] n'utilise que les i premiers objets. Tout optimum exclut l'objet i, donnant D[i-1,c], ou l'inclut s'il tient, donnant v_i + D[i-1,c-w_i]. Ces cas sont exhaustifs ; retirer l'objet inclus laisse exactement le sous-problème annoncé. La ligne sans objet vaut zéro, car ne rien choisir est permis : on n'exige pas de remplir exactement le sac.

Pour les poids [2,3], les valeurs [3,4] et la capacité 5, les lignes aux capacités 0 à 5 sont [0,0,0,0,0,0], [0,0,3,3,3,3], puis [0,0,3,4,4,7]. Des mises à jour croissantes produiraient déjà 6 à la capacité 4 avec le premier objet seul, en l'utilisant illégalement deux fois.

Capacité et poids doivent être des entiers non négatifs, et les listes de même longueur ; zip(..., strict=True) exige Python 3.10+. Un objet de poids nul est traité une fois par capacité : sa valeur positive n'est ajoutée qu'une fois, même à capacité nulle. L'explication des mises à jour non bornées suppose des poids positifs : une infinité d'objets de poids nul et de valeur positive rendrait l'optimum non borné. L'entrée vide donne zéro. Pour une capacité 6 et les objets (poids,valeur)=(4,5),(3,3),(3,3), le choix 0/1 par densité donne 5, mais la programmation dynamique trouve 6 avec les deux objets de poids 3.

assert knapsack([2, 3], [3, 4], 5) == 7
assert knapsack([4, 3, 3], [5, 3, 3], 6) == 6
assert knapsack([0], [5], 0) == 5
assert knapsack([], [], 0) == 0

Source

• CP-Algorithms: Knapsack Problem

Mes lectures · Les notes ouvertes sont mémorisées dans ce navigateur.