0/1 Knapsack Problem

Q: Comment trouver quels éléments le problème du sac à dos 0/1 a sélectionnés ?

Conservez le tableau complet et remontez à partir de best[n][capacity] . Si best[i][c] diffère de best[i-1][c] , l’élément i-1 a été placé dans le sac : notez-le et soustrayez son poids de c . Sinon, passez à la ligne i-1 en gardant le même c .

MoyenProgrammation dynamique

+10

Vous avez n articles. L’article i pèse weights[i] et vaut values[i]. Votre sac peut transporter un poids total d’au plus capacity. Chaque article existe en un seul exemplaire, et vous le prenez en entier ou le laissez de côté. Renvoyez la valeur totale maximale que vous pouvez emporter.

Fonction

knapsack(weights: integer-array, values: integer-array, capacity: integer) → integer

weightsinteger-array: le poids de chaque élément
valuesinteger-array: la valeur de chaque élément
capacityinteger: le poids maximal que le sac peut porter
Renvoieinteger: la valeur totale maximale des objets dont le poids ne dépasse pas la capacité

Contraintes

1 ≤ n ≤ 100, où n = weights.length = values.length
1 ≤ weights[i] ≤ 1000
1 ≤ values[i] ≤ 10⁴
1 ≤ capacity ≤ 1000

Exemples

Entrée: weights = [4, 2, 3, 5]values = [10, 4, 7, 12]capacity = 7
Sortie: 17
Explication: Les éléments 0 et 2 pèsent 4 + 3 = 7 et valent 10 + 7 = 17. En choisissant d’abord l’élément le plus précieux (poids 5, valeur 12), il ne reste de la place que pour l’élément 1, pour une valeur totale de 16.

Pour aller plus loin

Supposons que la capacité puisse atteindre 10^9 tandis que la somme des valeurs est d’au plus 10^4. Quel élément utiliserais-tu comme indice du tableau ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

Aucun ordre glouton ne fonctionne : placer d’abord l’objet le plus précieux donne 16, et non 17, dans le premier exemple. La meilleure valeur à partir de l’objet i dépend uniquement de i et de la capacité restante, un nombre entier jusqu’à 1000. Une cellule du tableau par paire donne O(n × capacity), et une seule ligne suffit si tu parcours les capacités en ordre décroissant.

Essaie les deux choix pour chaque élément

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Soit best(i, room) la valeur maximale des objets à partir de i pouvant être ajoutés avec room unités libres ; après le dernier objet, cette valeur est 0. Ne pas prendre l’objet i donne best(i+1, room). Le prendre, lorsque weights[i] ≤ room, donne values[i] + best(i+1, room-weights[i]). On garde la plus grande valeur. Chaque combinaison d’objets qui tient dans le sac correspond à une séquence de choix entre prendre et ne pas prendre, et la récursion les essaie toutes.

Chaque objet double le nombre de chemins. Lorsque les 100 objets tiennent ensemble, comme avec un poids de 10 chacun dans un sac de 1000, cela représente 2^100 chemins.

Algorithme

Écrivez best(i, room) ; renvoyez 0 lorsque i dépasse le dernier élément.
Définissez skip comme best(i+1, room).
Si weights[i] > room, renvoyez skip.
Sinon, renvoyez la plus grande valeur entre skip et values[i] + best(i+1, room-weights[i]).
Renvoyez best(0, capacity).

def knapsack(weights, values, capacity):
    n = len(weights)

    # The most value items i, i+1, ... can add with room units of weight left
    def best(i, room):
        if i == n:
            return 0
        skip = best(i + 1, room)
        if weights[i] > room:
            return skip
        take = values[i] + best(i + 1, room - weights[i])
        return max(skip, take)

    return best(0, capacity)

Remplissez un tableau par élément et capacité

Intuition

La récursion atteint la même paire (i, room) en suivant de nombreux chemins. Il y a au plus 101 × 1001, soit environ 10^5 paires, donc calcule chacune une seule fois.

Soit best[i][c] la valeur maximale que les i premiers objets peuvent mettre dans un sac de capacité c ; la ligne 0 ne contient que des 0. Pour l’objet i-1, de poids w et de valeur v, ne pas le prendre donne best[i-1][c], et le mettre dans le sac, lorsque w ≤ c, donne best[i-1][c-w] + v. La ligne i ne lit que la ligne i-1, donc chaque objet entre dans une cellule au plus une fois.

Dans le premier exemple, l’objet 2 (poids 3, valeur 7) fait passer la capacité 7 à best[2][4] + 7 = 17. L’objet 3 ne propose ensuite que best[3][2] + 12 = 16, donc la réponse reste 17.

Algorithme

Crée un tableau de n+1 lignes et de capacity+1 colonnes, toutes à 0.
Pour chaque ligne i de 1 à n, prends w = weights[i-1] et v = values[i-1].
Pour chaque capacité c, définis best[i][c] comme best[i-1][c].
Si w ≤ c et que best[i-1][c-w] + v est supérieur, stocke cette valeur à la place.
Renvoie best[n][capacity].

def knapsack(weights, values, capacity):
    n = len(weights)
    # best[i][c]: the most value from the first i items within capacity c
    best = [[0] * (capacity + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        w, v = weights[i - 1], values[i - 1]
        for c in range(capacity + 1):
            best[i][c] = best[i - 1][c]  # leave item i-1 out
            if w <= c and best[i - 1][c - w] + v > best[i][c]:
                best[i][c] = best[i - 1][c - w] + v  # put it in
    return best[n][capacity]

Une ligne, capacités parcourues en ordre décroissant

Intuition

La ligne i n’a besoin que de la ligne i-1, alors conserve une seule ligne best[c] et écrase-la élément par élément. Le sens du parcours détermine si la réponse est correcte.

En parcourant c dans l’ordre croissant, best[c-w] peut déjà inclure l’élément courant. Un élément de poids 3 et de valeur 5 avec une capacité de 6 donne une valeur de 5 pour la capacité 3, puis la capacité 6 le lit et passe à 10 : deux copies. En parcourant les capacités à rebours, de capacity à w, la cellule lue se trouve en dessous de celle écrite et sera écrasée plus tard ; elle contient donc toujours la valeur de la ligne précédente.

Le parcours croissant est la bonne boucle lorsque les éléments peuvent être pris en nombre illimité. Ici, le temps reste O(n × capacity) et la mémoire passe à une seule ligne.

Algorithme

Crée best avec capacity + 1 entrées, toutes à 0.
Pour chaque objet de poids w et de valeur v, parcours c de capacity jusqu’à w.
Si best[c-w] + v est supérieur à best[c], stocke cette valeur dans best[c].
Retourne best[capacity].

def knapsack(weights, values, capacity):
    # best[c]: the most value from the items seen so far within capacity c
    best = [0] * (capacity + 1)
    for w, v in zip(weights, values):
        # Walk the capacities downward so each item goes in at most once
        for c in range(capacity, w - 1, -1):
            if best[c - w] + v > best[c]:
                best[c] = best[c - w] + v
    return best[capacity]

Pièges et cas limites

Parcourir les capacités dans l'ordre croissant dans la version à une seule rangée permet de compter un objet deux fois : un objet de poids 3 et de valeur 5 dans un sac de capacité 6 rapporte 10 au lieu de 5.
Une rangée de capacity entrées au lieu de capacity + 1. Renvoyer ensuite best[capacity-1] fait perdre toute combinaison qui remplit exactement le sac, comme un poids de 1 dans un sac de capacité 1.
Initialiser les entrées à moins l'infini. Le sac n'a pas besoin d'être plein, donc chaque entrée est initialisée à 0 ; avec moins l'infini, le troisième exemple renvoie moins l'infini au lieu de 0.
Un objet plus lourd que le sac doit être ignoré. Dans le troisième exemple, une plage fermée w...capacity arrête le programme en Swift, et (w+1):(capacity+1) compte à rebours en R.

Questions fréquentes3

Quelle est la complexité temporelle du problème du sac à dos 0/1 ?

Le tableau s’exécute en O(n × capacity), soit environ 10^5 étapes pour 100 éléments et une capacité de 1000, et la version à une ligne utilise une mémoire en O(capacity). La borne est pseudo-polynomiale : elle croît avec la valeur de la capacité, et non avec son nombre de chiffres. Le problème général est NP-difficile.

Pourquoi un algorithme glouton ne fonctionne-t-il pas pour le problème du sac à dos 0/1 ?

Une règle gloutonne n’annule jamais un choix, même lorsque l’objet laisse un espace qui reste inoccupé. Avec une capacité de 7, l’objet de poids 5 et de valeur 10 a le meilleur ratio, à égalité, et pourtant les objets de poids 4 et 3 valent ensemble 13. La stratégie gloutonne par ratio est optimale uniquement pour le problème du sac à dos fractionnaire, où tu peux découper les objets.

Comment trouver quels éléments le problème du sac à dos 0/1 a sélectionnés ?

Conservez le tableau complet et remontez à partir de best[n][capacity]. Si best[i][c] diffère de best[i-1][c], l’élément i-1 a été placé dans le sac : notez-le et soustrayez son poids de c. Sinon, passez à la ligne i-1 en gardant le même c.

def knapsack(weights, values, capacity):
    # Écrivez le code ici

Test #1

Test #2

Test #3

Arguments

weights = [4, 2, 3, 5]
values = [10, 4, 7, 12]
capacity = 7

Résultat attendu

0/1 Knapsack Problem

Fonction

Contraintes

Exemples

Indices

Solution

Essaie les deux choix pour chaque élément

Remplissez un tableau par élément et capacité

Une ligne, capacités parcourues en ordre décroissant

Pièges et cas limites

Questions fréquentes3

Problèmes similaires