0/1 Knapsack Problem

Q: Wie findest du heraus, welche Elemente der 0/1-Rucksack ausgewählt hat?

Behalte die vollständige Tabelle bei und gehe von best[n][capacity] zurück. Wenn sich best[i][c] von best[i-1][c] unterscheidet, wurde Element i-1 eingepackt. Halte es also fest und ziehe sein Gewicht von c ab. Andernfalls gehe zur Zeile i-1 mit demselben c .

MittelDynamische Programmierung

+10

Du hast n Gegenstände. Gegenstand i wiegt weights[i] und ist values[i] wert. Deine Tasche kann höchstens ein Gesamtgewicht von capacity tragen. Jeder Gegenstand ist nur einmal vorhanden, und du kannst ihn entweder vollständig einpacken oder zurücklassen. Gib den größten Gesamtwert zurück, den du einpacken kannst.

Funktion

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

weightsinteger-array: das Gewicht jedes Elements
valuesinteger-array: der Wert jedes Elements
capacityinteger: das maximale Gewicht, das die Tasche tragen kann
Gibt zurückinteger: der größte Gesamtwert der Gegenstände, deren Gewichte in die Kapazität passen

Einschränkungen

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

Beispiele

Eingabe: weights = [4, 2, 3, 5]values = [10, 4, 7, 12]capacity = 7
Ausgabe: 17
Erklärung: Die Gegenstände 0 und 2 wiegen 4 + 3 = 7 und sind 10 + 7 = 17 wert. Wenn du zuerst den wertvollsten Gegenstand einpackst (Gewicht 5, Wert 12), bleibt nur noch Platz für Gegenstand 1, sodass der Gesamtwert 16 beträgt.

Weiterführende Frage

Angenommen, die Kapazität kann 10^9 erreichen, während sich die Werte auf höchstens 10^4 summieren. Wonach würdest du die Tabelle indizieren?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Keine gierige Reihenfolge funktioniert: Wenn man zuerst den wertvollsten Gegenstand einpackt, erhält man im ersten Beispiel 16 statt 17. Der beste Wert ab Gegenstand i hängt nur von i und dem verbleibenden Platz ab, einer ganzen Zahl bis zu 1000. Eine Tabellenzelle pro Paar ergibt O(n × capacity), und eine Zeile reicht aus, wenn du die Kapazitäten absteigend durchgehst.

Probiere bei jedem Element beide Optionen aus

Korrekt, wird aber bei den größten Tests nicht fertig

Idee

Sei best(i, room) der größtmögliche Wert, den die Gegenstände ab i mit room freien Einheiten hinzufügen können; nach dem letzten Gegenstand ist er 0. Den Gegenstand i auszulassen ergibt best(i+1, room). Ihn einzupacken ergibt, wenn weights[i] ≤ room, values[i] + best(i+1, room-weights[i]). Behalte den größeren Wert. Jedes Packen, das hineinpasst, entspricht einer Folge von Einpack- und Auslassentscheidungen, und die Rekursion probiert sie alle aus.

Jeder Gegenstand verdoppelt die Pfade. Wenn alle 100 Gegenstände zusammen hineinpassen, wie bei einem Gewicht von jeweils 10 in einer Tasche mit einer Kapazität von 1000, sind das 2^100 Pfade.

Algorithmus

Schreibe best(i, room); gib 0 zurück, wenn i hinter dem letzten Element liegt.
Setze skip auf best(i+1, room).
Wenn weights[i] > room, gib skip zurück.
Gib andernfalls den größeren Wert von skip und values[i] + best(i+1, room-weights[i]) zurück.
Gib best(0, capacity) zurück.

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)

Eine Tabelle nach Gegenstand und Fassungsvermögen ausfüllen

Idee

Die Rekursion erreicht dasselbe Paar (i, room) über viele Pfade. Es gibt höchstens 101 × 1001, also etwa 10^5 Paare. Berechne daher jedes nur einmal.

Sei best[i][c] der größte Wert, den die ersten i Gegenstände in einen Rucksack mit Kapazität c packen können; Zeile 0 besteht nur aus 0. Für Gegenstand i-1 mit Gewicht w und Wert v ergibt das Weglassen best[i-1][c] und das Einpacken, wenn w ≤ c, ergibt best[i-1][c-w] + v. Zeile i liest nur Zeile i-1, daher wird jeder Gegenstand höchstens einmal in eine Zelle eingetragen.

Im ersten Beispiel erhöht Gegenstand 2 (Gewicht 3, Wert 7) die Kapazität 7 auf best[2][4] + 7 = 17. Gegenstand 3 bietet dann nur best[3][2] + 12 = 16, sodass die Antwort 17 bleibt.

Algorithmus

Erstelle eine Tabelle mit n+1 Zeilen und capacity+1 Spalten, die alle den Wert 0 enthalten.
Nimm für jede Zeile i von 1 bis n w = weights[i-1] und v = values[i-1].
Setze für jede Kapazität c best[i][c] auf best[i-1][c].
Wenn w ≤ c gilt und best[i-1][c-w] + v größer ist, speichere stattdessen diesen Wert.
Gib best[n][capacity] zurück.

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]

Eine Zeile, Kapazitäten absteigend durchlaufen

Idee

Zeile i benötigt nur Zeile i-1, also behalten wir eine Zeile best[c] bei und überschreiben sie Element für Element. Die Laufrichtung entscheidet, ob das Ergebnis korrekt ist.

Wenn wir c aufwärts durchlaufen, kann best[c-w] das aktuelle Element bereits enthalten. Bei einem Element mit Gewicht 3 und Wert 5 ergibt die Kapazität 6 für Kapazität 3 zunächst den Wert 5; dann liest Kapazität 6 diesen Wert und wird zu 10: zwei Kopien. Wenn wir von capacity abwärts bis w laufen, liegt die gelesene Zelle unter der Zelle, die wir schreiben, und wird erst später überschrieben. Daher enthält sie weiterhin den Wert aus der vorherigen Zeile.

Der aufsteigende Durchlauf ist die richtige Schleife, wenn Elemente unbegrenzt oft verwendet werden können. Hier bleibt die Laufzeit bei O(n × capacity), und der Speicherbedarf sinkt auf eine Zeile.

Algorithmus

Erstelle best mit capacity + 1 Einträgen, alle mit dem Wert 0.
Gehe für jedes Element mit Gewicht w und Wert v c von capacity abwärts bis w durch.
Wenn best[c-w] + v größer als best[c] ist, speichere den Wert in best[c].
Gib best[capacity] zurück.

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]

Stolperfallen und Grenzfälle

Wenn man die Kapazitäten in der Version mit einer Zeile aufsteigend durchläuft, wird ein Gegenstand zweimal eingepackt: Ein Gegenstand mit Gewicht 3 und Wert 5 erzielt in einem Rucksack mit Kapazität 6 einen Wert von 10 statt 5.
Eine Zeile mit capacity Einträgen statt capacity + 1. Die Rückgabe von best[capacity-1] geht dann verloren, wenn der Rucksack genau gefüllt wird, etwa bei Gewicht 1 in einem Rucksack mit Kapazität 1.
Einträge mit minus unendlich initialisieren. Der Rucksack muss nicht voll sein, daher werden alle Einträge mit 0 initialisiert; mit minus unendlich gibt das dritte Beispiel minus unendlich statt 0 zurück.
Ein Gegenstand, der schwerer als der Rucksack ist, muss übersprungen werden. Im dritten Beispiel stoppt ein geschlossener Bereich w...capacity das Programm in Swift, und (w+1):(capacity+1) zählt in R rückwärts.

Häufige Fragen3

Wie hoch ist die Zeitkomplexität des 0/1-Rucksackproblems?

Die Tabelle läuft in O(n × capacity) Zeit, etwa 10^5 Schritte für 100 Elemente und eine Kapazität von 1000, und die Version mit einer Zeile benötigt O(capacity) Speicher. Die Schranke ist pseudopolynomiell: Sie wächst mit dem Wert der Kapazität, nicht mit der Anzahl ihrer Ziffern. Das allgemeine Problem ist NP-schwer.

Warum funktioniert ein Greedy-Algorithmus beim 0/1-Rucksackproblem nicht?

Eine gierige Regel macht eine Wahl niemals rückgängig, selbst wenn der Gegenstand Platz lässt, der von nichts ausgefüllt wird. Bei einer Kapazität von 7 hat der Gegenstand mit Gewicht 5 und Wert 10 das beste Verhältnis, doch die Gegenstände mit Gewicht 4 und 3 sind zusammen 13 wert. Die gierige Auswahl nach Verhältnis ist nur beim fraktionalen Rucksackproblem optimal, bei dem du Gegenstände teilen kannst.

Wie findest du heraus, welche Elemente der 0/1-Rucksack ausgewählt hat?

Behalte die vollständige Tabelle bei und gehe von best[n][capacity] zurück. Wenn sich best[i][c] von best[i-1][c] unterscheidet, wurde Element i-1 eingepackt. Halte es also fest und ziehe sein Gewicht von c ab. Andernfalls gehe zur Zeile i-1 mit demselben c.

def knapsack(weights, values, capacity):
    # Schreibe hier den Code

Test #1

Test #2

Test #3

Argumente

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

Erwartete Ausgabe

0/1 Knapsack Problem

Funktion

Einschränkungen

Beispiele

Tipps

Lösung

Probiere bei jedem Element beide Optionen aus

Eine Tabelle nach Gegenstand und Fassungsvermögen ausfüllen

Eine Zeile, Kapazitäten absteigend durchlaufen

Stolperfallen und Grenzfälle

Häufige Fragen3

Ähnliche Aufgaben