dynamic-programming
Rucksack Problem

Bemerkungen

0-1 Rucksackproblem

Angenommen, Sie werden angesichts des Gesamtgewichts, das Sie am Rucksack tragen können, und einiger Gegenstände mit ihrem Gewicht und ihren Werten gefragt, wie können Sie diese Gegenstände so nehmen, dass die Summe ihrer Werte maximal ist, die Summe ihrer Gewichte jedoch nicht das Gesamtgewicht, das Sie tragen können, nicht überschreiten? Das 0-1 zeigt an, dass Sie den Artikel auswählen oder nicht. Wir haben auch eine Menge von jedem Artikel. Das bedeutet, dass Sie den Artikel nicht teilen können. Wenn es sich nicht um ein 0: 1-Rucksack-Problem handelte , das heißt, wenn Sie die Artikel hätten aufteilen können, gibt es eine gierige Lösung, die als fraktionales Rucksack-Problem bezeichnet wird .

Konzentrieren wir uns zunächst auf unser aktuelles Problem. Nehmen wir an, wir haben eine Rucksackkapazität von 7 . Wir haben 4 Artikel. Ihre Gewichte und Werte sind:

+----------+---+---+---+---+
|   Item   | 1 | 2 | 3 | 4 |
+----------+---+---+---+---+
|  Weight  | 1 | 3 | 4 | 5 |
+----------+---+---+---+---+
|   Value  | 1 | 4 | 5 | 7 |
+----------+---+---+---+---+

Eine Brute-Force-Methode würde alle möglichen Kombinationen von Elementen annehmen. Dann können wir ihre Gesamtgewichte berechnen und ausschließen, die die Kapazität unseres Rucksacks übersteigen, und das Gewicht ermitteln, das den maximalen Wert ergibt. Für 4 Elemente müssen wir ( 4! - 1 ) = 23 mögliche Kombinationen (außer eine ohne Elemente) prüfen. Dies ist ziemlich umständlich, wenn die Anzahl der Artikel zunimmt. Hier einige Aspekte, die wir bemerken können, das heißt:

• Wir können weniger Artikel verwenden und den maximalen Wert berechnen, den wir für diese Artikel verwenden können, und sie kombinieren. So kann unser Problem in Teilprobleme unterteilt werden.
• Wenn wir die Kombinationen für item {1,2} berechnen, können wir sie verwenden, wenn wir {1, 2, 3} berechnen.
• Wenn wir das Gewicht minimieren und den Wert maximieren, können wir unsere optimale Lösung herausfinden.

Aus diesen Gründen verwenden wir die dynamische Programmierung, um unser Problem zu lösen. Unsere Strategie lautet: Wann immer ein neuer Artikel kommt, prüfen wir, ob wir den Artikel auswählen können oder nicht, und wir wählen erneut die Artikel mit dem höchsten Wert aus. Wenn wir nun den Artikel auswählen, ist unser Wert der Wert des Artikels zuzüglich des Wertes, den wir erhalten können, indem der Wert von unserer Kapazität abgezogen wird und das Maximum, das wir für das verbleibende Gewicht erhalten können. Wenn wir den Artikel nicht auswählen, wählen wir den Artikel mit dem höchsten Wert aus, ohne den Artikel einzuschließen. Versuchen wir es mit unserem Beispiel zu verstehen:

Wir nehmen eine 2D-Array- Tabelle , in der die Anzahl der Spalten der maximale Wert ist, den wir erhalten können, wenn die Elemente + 1 genommen werden. Die Anzahl der Zeilen entspricht der Anzahl der Elemente. Unser Array wird wie folgt aussehen:

+-------+--------+---+---+---+---+---+---+---+---+
| Value | Weight | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+-------+--------+---+---+---+---+---+---+---+---+
|   1   |    1   | 0 |   |   |   |   |   |   |   |
+-------+--------+---+---+---+---+---+---+---+---+
|   4   |    3   | 0 |   |   |   |   |   |   |   |
+-------+--------+---+---+---+---+---+---+---+---+
|   5   |    4   | 0 |   |   |   |   |   |   |   |
+-------+--------+---+---+---+---+---+---+---+---+
|   7   |    5   | 0 |   |   |   |   |   |   |   |
+-------+--------+---+---+---+---+---+---+---+---+

Wir haben das Gewicht und den Wert jedes Elements in das Array aufgenommen, um Ihnen die Bequemlichkeit zu erleichtern. Denken Sie daran, dass diese nicht Teil des Arrays sind. Sie dienen nur zu Berechnungszwecken. Sie müssen diese Werte nicht in einem Tabellenarray speichern.

Unsere erste Spalte ist mit 0 gefüllt. Das heißt, wenn unsere maximale Kapazität 0 ist , egal was wir haben, da wir keine Artikel auswählen können, ist unser Maximalwert 0 . Beginnen wir mit Tabelle [0] [1] . Wenn wir Tabelle [1] [1] füllen, fragen wir uns, ob unsere maximale Kapazität 1 betrug und wir nur den ersten Artikel hatten. Welches wäre unser maximaler Wert? Das Beste, was wir tun können, ist 1 , indem wir den Artikel auswählen. Für Tabelle [0] [2] bedeutet dies, wenn unsere maximale Kapazität 2 ist und wir nur das erste Element haben, der maximale Wert, den wir erhalten können, 1 . Dies wird für Tabelle [0] [3] , Tabelle [0] [4] , Tabelle [0] [5] , Tabelle [0] [6] und Tabelle [0] [7] gleich sein . Dies liegt daran, dass wir nur einen Artikel haben, der uns Wert 1 gibt . Da wir nur 1 Quantität jedes Einzelteils haben, unabhängig davon , wie wir die Kapazität unserer Ranzen erhöhen, von einem Element, 1 ist der beste Wert , den wir machen können. So sieht unser Array so aus:

+-------+--------+---+---+---+---+---+---+---+---+
| Value | Weight | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+-------+--------+---+---+---+---+---+---+---+---+
|   1   |    1   | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
+-------+--------+---+---+---+---+---+---+---+---+
|   4   |    3   | 0 |   |   |   |   |   |   |   |
+-------+--------+---+---+---+---+---+---+---+---+
|   5   |    4   | 0 |   |   |   |   |   |   |   |
+-------+--------+---+---+---+---+---+---+---+---+
|   7   |    5   | 0 |   |   |   |   |   |   |   |
+-------+--------+---+---+---+---+---+---+---+---+

Für Tabelle [1] [1] fragen wir uns, ob wir die Punkte 1 und 2 hatten und ob die maximale Kapazität unseres Rucksacks 1 betrug. Welchen maximalen Wert können wir erzielen? Wenn wir sowohl Punkt 1 als auch Punkt 2 nehmen , wird das Gesamtgewicht 4 sein , was unsere derzeitige Rucksackkapazität übersteigen wird. Daher kann Punkt 2 nicht ausgewählt werden. Was ist das Beste, was wir tun können, ohne Punkt 2 zu nehmen ? Der Wert von oben, das ist Tabelle [0] [1], der den maximalen Wert enthält, den wir erhalten können, wenn wir die maximale Kapazität 1 haben und das zweite Element nicht ausgewählt haben. Für Tabelle [1] [2] können wir den Artikel nicht nehmen, da 2 weniger als das Gewicht [2] ist, dh das Gewicht des zweiten Elements. Wir können also feststellen, dass wir den Artikel nicht nehmen können, wenn das Gewicht des aktuellen Artikels die maximale Kapazität überschreitet. In diesem Fall nehmen wir einfach den Wert von oben, der den maximalen Wert darstellt, den wir ohne den Artikel annehmen können.

if weight[i] > j
    Table[i][j] := Table[i-1][j]
end if

Für Tabelle [1] [3] haben wir zwei Möglichkeiten, da unsere maximale Kapazität unserem aktuellen Gewicht entspricht.

• Wir wählen den Artikel aus und addieren seinen Wert mit dem maximalen Wert, den wir von anderen verbleibenden Artikeln erhalten können, nachdem wir diesen Artikel genommen haben.
• Wir können diesen Artikel ausschließen.

Unter den beiden Optionen wählen wir diejenige aus, aus der wir den maximalen Wert erzielen können. Wenn wir den Artikel auswählen, erhalten wir: Wert für diesen Artikel + Maximalwert aus dem Rest der Artikel, nachdem dieser Artikel = 4 + 0 = 4 genommen wurde . Wir erhalten 4 (Wert des Elements) aus unserem Gewicht Array und die 0 (maximale Wert , den wir aus Rest der Elemente nach der Einnahme dieses Produkt bekommen kann) kommt durch 1 geht Schritt oben und drei Schritte zurück. Das ist Tabelle [0] [0] . Warum? Wenn wir den Artikel nehmen, beträgt unsere verbleibende Kapazität 3 - 3 = 0 und der verbleibende Artikel ist der erste Artikel. Wenn Sie sich erinnern, speichert Tabelle [0] [0] den maximalen Wert, den wir erhalten können, wenn unsere Kapazität 0 ist und wir nur das erste Element hatten. Wenn wir den Artikel jetzt nicht auswählen, wird der maximale Wert, den wir erhalten können, von 1 Schritt oben, dh 1, bestimmt . Nun nehmen wir das Maximum dieser beiden Werte ( 4 , 1 ) und setzen Tabelle [1] [2] = 4 . Bei Tabelle [1] [4] ist die maximale Rucksackkapazität von 4 größer als 3 , dem Gewicht unseres aktuellen Artikels. Wir haben wieder zwei Optionen. Wir nehmen max ( Gewicht [2] + Tabelle [0] [4-Gewicht [2]] , Tabelle [0] [4] ) = max ( Gewicht [2] + Tabelle [0] [1] , Tabelle [0]) [4] ) = max ( 4 + 1 , 1 ) = 5 .

if weight[i] <= j
    w := weight[i]
    Table[i][j] := max(w + Table[i][j-w], Table[i-1][j])
end if

Mit diesen beiden Formeln können wir das gesamte Table- Array füllen. Unser Array wird wie folgt aussehen:

+-------+--------+---+---+---+---+---+---+---+---+
| Value | Weight | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+-------+--------+---+---+---+---+---+---+---+---+
|   1   |    1   | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
+-------+--------+---+---+---+---+---+---+---+---+
|   4   |    3   | 0 | 1 | 1 | 4 | 5 | 5 | 5 | 5 |
+-------+--------+---+---+---+---+---+---+---+---+
|   5   |    4   | 0 | 1 | 1 | 4 | 5 | 6 | 6 | 9 |
+-------+--------+---+---+---+---+---+---+---+---+
|   7   |    5   | 0 | 1 | 1 | 4 | 5 | 7 | 8 | 9 |
+-------+--------+---+---+---+---+---+---+---+---+

Der letzte Wert, den wir in unser Array eingefügt haben, Tabelle [3] [7], enthält unseren erforderlichen Maximalwert. Dies ist der Höchstwert, den wir erzielen können, wenn wir 4 Gegenstände hätten und unsere maximale Kapazität des Rucksacks 7 wäre .

Hier ist eines zu beachten, dass das Gewicht sogar für die erste Reihe größer sein kann als die Kapazität des Rucksacks. Wir müssen eine weitere Einschränkung beibehalten, um den Wert zu überprüfen, während die erste Zeile gefüllt wird. Oder wir können einfach eine andere Zeile nehmen und alle Werte der ersten Zeile auf 0 setzen . Der Pseudo-Code würde folgendermaßen aussehen:

Procedure Knapsack(Weight, Value, maxCapacity):
n := Item.size - 1
Table[n+1][maxCapacity+1]
for i from 0 to n
    Table[i][0] := 0
end for
for j from 1 to maxCapacity
    if j >= Weight[0]
        Table[0][j] := Weight[0]
    else
        Table[0][j] := 0
    end if
end for
for i from 1 to n
    for j from 1 to maxCapacity
        if Weight[i] >= j                                            //can't pick the item
            Table[i][j] := Table[i-1][j]        
        else                                                        //can pick the item
            w := Weight[i]
            Table[i][j] := max(w + Table[i-1][j-w], Table[i-1][j])
        end if
    end for
end for
Return Table[n][maxCapacity]

Die zeitliche Komplexität dieses Algorithmus ist O(n*maxCapacity) , wobei n die Anzahl der Elemente und maxCapacity die maximale Kapazität unseres Rucksacks ist.

Bisher haben wir den maximalen Wert gefunden, den wir aus unserem Beispiel erhalten können. Es bleibt noch eine Frage. Was sind die eigentlichen Gegenstände? Wir werden die Werte in unserem Tabellen- Array nachvollziehen, um herauszufinden, welche Elemente wir genommen haben. Wir werden zwei Strategien verfolgen:

• Wenn für jeden Artikel der Wert von der obigen Position stammt, haben wir den aktuellen Artikel nicht übernommen. Wir gehen einen Schritt weiter.
• Wenn der Wert nicht von der obigen Position stammt, haben wir den Artikel genommen. Wir gehen also einen Schritt nach oben und x einen Schritt zurück, wobei x das Gewicht des aktuellen Artikels ist.

Der Pseudo-Code lautet:

Procedure printItems(Table, maxCapacity, Value):
i := Item.size - 1
j := maxCapacity
while j is not equal to 0
    if Table[i][j] is equal to Table[i-1][j]
        i := i - 1
    else
        Print: i
        j := j - weight[i]
        i := i - 1
    end if
end while

Wenn wir unser Beispiel nachvollziehen, erhalten wir:

Daraus können wir sagen, dass wir Punkt 2 und 3 nehmen können , um den maximalen Wert zu erhalten.