Hier ist ein Rucksack wie ein Behälter oder eine Tasche. Angenommen, wir haben einige Artikel angegeben, die bestimmte Gewichte oder Gewinne haben. Wir müssen einige Gegenstände so in den Rucksack packen, dass der Gesamtwert einen maximalen Gewinn ergibt.

Das Gewicht des Behälters beträgt beispielsweise 20 kg. Wir müssen die Artikel so auswählen, dass die Summe des Gewichts der Artikel entweder kleiner oder gleich dem Gewicht des Behälters ist und der Gewinn maximal ist.

Es gibt zwei Arten von Rucksackproblemen:

• 0/1 Rucksackproblem
• Bruchteil des Rucksackproblems

Wir werden beide Probleme einzeln besprechen. Zuerst lernen wir das 0/1-Rucksackproblem kennen.

Was ist das 0/1-Rucksackproblem?

Das 0/1-Rucksackproblem bedeutet, dass die Gegenstände entweder vollständig oder gar nicht in einen Rucksack gefüllt sind. Wir haben zum Beispiel zwei Artikel mit einem Gewicht von 2 kg bzw. 3 kg. Wenn wir den 2-kg-Artikel auswählen, können wir nicht den 1-kg-Artikel aus dem 2-kg-Artikel auswählen (Artikel ist nicht teilbar); Wir müssen den 2-kg-Artikel vollständig auswählen. Dies ist ein 0/1-Rucksackproblem, bei dem wir entweder den Gegenstand vollständig auswählen oder diesen Gegenstand auswählen. Das 0/1-Rucksackproblem wird durch die dynamische Programmierung gelöst.

Was ist das Bruchteil-Rucksack-Problem?

Das gebrochene Rucksackproblem bedeutet, dass wir den Gegenstand teilen können. Wenn wir zum Beispiel einen Artikel mit 3 kg haben, können wir den Artikel mit 2 kg auswählen und den Artikel mit 1 kg übrig lassen. Das fraktionierte Rucksackproblem wird durch den Greedy-Ansatz gelöst.

Beispiel für ein 0/1-Rucksackproblem.

Betrachten Sie das Problem mit Gewichten und Gewinnen wie folgt:

Gewichte: {3, 4, 6, 5}

Gewinne: {2, 3, 1, 4}

Das Gewicht des Rucksacks beträgt 8 kg

Die Anzahl der Artikel beträgt 4

Das obige Problem kann mit der folgenden Methode gelöst werden:

X_ich= {1, 0, 0, 1}

= {0, 0, 0, 1}

Ganzzahl-Doppel-Java

= {0, 1, 0, 1}

Die oben genannten sind die möglichen Kombinationen. 1 bedeutet, dass der Artikel vollständig kommissioniert wurde und 0 bedeutet, dass kein Artikel kommissioniert wurde. Da es 4 Elemente gibt, sind folgende mögliche Kombinationen möglich:

2⁴= 16; Also. Es gibt 16 mögliche Kombinationen, die mit der obigen Aufgabe erstellt werden können. Sobald alle Kombinationen erstellt sind, müssen wir die Kombination auswählen, die den maximalen Gewinn bringt.

Ein weiterer Ansatz zur Lösung des Problems ist der dynamische Programmieransatz. Beim dynamischen Programmieransatz wird das komplizierte Problem in Teilprobleme unterteilt, dann finden wir die Lösung eines Teilproblems und die Lösung des Teilproblems wird verwendet, um die Lösung eines komplexen Problems zu finden.

Wie kann dieses Problem mithilfe des dynamischen Programmieransatzes gelöst werden?

Erste,

Wir erstellen eine Matrix wie unten dargestellt:

In der obigen Matrix stellen die Spalten das Gewicht dar, d. h. 8. Die Zeilen stellen die Gewinne und Gewichte der Artikel dar. Hier haben wir das Gewicht 8 nicht direkt genommen, das Problem ist in Unterprobleme unterteilt, nämlich 0, 1, 2, 3, 4, 5, 6, 7, 8. Die Lösung der Unterprobleme wird in gespeichert Zellen und die Antwort auf das Problem würden in der letzten Zelle gespeichert. Zuerst schreiben wir die Gewichte in aufsteigender Reihenfolge und gewinnen entsprechend ihrer Gewichte wie folgt:

In_ich= {3, 4, 5, 6}

P_ich= {2, 3, 4, 1}

Die erste Zeile und die erste Spalte wären 0, da es für w=0 kein Element gibt

Wenn i=1, W=1

In₁= 3; Da wir im Set nur einen Artikel mit dem Gewicht 3 haben, das Fassungsvermögen des Rucksacks jedoch 1 beträgt, können wir den Artikel mit 3 kg nicht in den Rucksack mit der Kapazität von 1 kg füllen, also fügen Sie 0 bei M[1][1] hinzu, wie unten gezeigt :

Wenn i = 1, W = 2

In₁= 3; Da wir im Set nur einen Artikel mit dem Gewicht 3 haben, die Kapazität des Rucksacks aber 2 beträgt, können wir den Artikel mit 3 kg nicht in den Rucksack mit der Kapazität von 2 kg füllen, also fügen Sie 0 bei M[1][2] hinzu, wie unten gezeigt :

Wenn i=1, W=3

In₁= 3; Da wir nur einen Gegenstand im Set haben, dessen Gewicht 3 beträgt und das Gewicht des Rucksacks ebenfalls 3 beträgt; Daher können wir den Rucksack mit einem Gegenstand mit einem Gewicht von 3 füllen. Wir setzen den Gewinn, der dem Gewicht 3 entspricht, d. h. 2, bei M[1][3], wie unten gezeigt:

Wenn i=1, W = 4

_W1= 3; Da wir nur einen Gegenstand im Set haben, dessen Gewicht 3 beträgt und das Gewicht des Rucksacks 4 beträgt; Daher können wir den Rucksack mit einem Gegenstand mit einem Gewicht von 3 füllen. Wir setzen den Gewinn entsprechend dem Gewicht 3, d. h. 2, bei M[1][4] ein, wie unten gezeigt:

Wenn i=1, W = 5

_W1= 3; Da wir nur einen Gegenstand im Set haben, dessen Gewicht 3 beträgt und das Gewicht des Rucksacks 5 beträgt; Daher können wir den Rucksack mit einem Gegenstand mit einem Gewicht von 3 füllen. Wir setzen den Gewinn entsprechend dem Gewicht 3, d. h. 2, auf M[1][5], wie unten gezeigt:

Wenn i =1, W=6

_W1= 3; Da wir nur einen Gegenstand im Set haben, der das Gewicht 3 hat und das Gewicht des Rucksacks 6 beträgt; Daher können wir den Rucksack mit einem Gegenstand mit einem Gewicht von 3 füllen. Wir setzen den Gewinn, der dem Gewicht 3 entspricht, d. h. 2, bei M[1][6], wie unten gezeigt:

Wenn i=1, W = 7

_W1= 3; Da wir nur einen Gegenstand im Set haben, der das Gewicht 3 hat und das Gewicht des Rucksacks 7 beträgt; Daher können wir den Rucksack mit einem Gegenstand mit einem Gewicht von 3 füllen. Wir setzen den Gewinn entsprechend dem Gewicht 3, d. h. 2, bei M[1][7] ein, wie unten gezeigt:

Wenn i =1, W =8

_W1= 3; Da wir nur einen Gegenstand im Set haben, der das Gewicht 3 hat und das Gewicht des Rucksacks 8 beträgt; Daher können wir den Rucksack mit einem Gegenstand mit einem Gewicht von 3 füllen. Wir setzen den Gewinn entsprechend dem Gewicht 3, d. h. 2, bei M[1][8] ein, wie unten gezeigt:

Jetzt wird der Wert von „i“ erhöht und beträgt 2.

Wenn i =2, W = 1

Das dem Wert 2 entsprechende Gewicht ist 4, also w₂= 4. Da wir in der Menge nur einen Gegenstand mit einem Gewicht von 4 haben und das Gewicht des Rucksacks 1 beträgt, können wir den Gegenstand mit dem Gewicht 4 nicht in einen Rucksack stecken, also fügen wir 0 bei M[2][1 hinzu ] wird wie folgt angezeigt:

Wenn i =2, W = 2

Das dem Wert 2 entsprechende Gewicht ist 4, also w₂= 4. Da wir in der Menge nur einen Gegenstand mit einem Gewicht von 4 haben und das Gewicht des Rucksacks 2 beträgt, können wir den Gegenstand mit dem Gewicht 4 nicht in einen Rucksack stecken, also fügen wir 0 bei M[2][2 hinzu ] wird wie folgt angezeigt:

Wenn i =2, W = 3

Das dem Wert 2 entsprechende Gewicht ist 4, also w₂= 4. Da wir in der Menge zwei Gegenstände mit den Gewichten 3 und 4 haben und das Gewicht des Rucksacks 3 beträgt, können wir den Gegenstand mit dem Gewicht 3 in einen Rucksack stecken, also addieren wir 2 bei M[2][3] wie unten dargestellt:

Wenn i =2, W = 4

Das dem Wert 2 entsprechende Gewicht ist 4, also w₂= 4. Da wir in der Menge zwei Gegenstände mit den Gewichten 3 und 4 haben und das Gewicht des Rucksacks 4 beträgt, können wir einen Gegenstand mit dem Gewicht 4 in einen Rucksack stecken, da der Gewinn, der dem Gewicht 4 entspricht, größer ist als der des Gegenstands mit dem Gewicht 3, also fügen wir 3 bei M[2][4] hinzu, wie unten gezeigt:

Wenn i = 2, W = 5

Das dem Wert 2 entsprechende Gewicht ist 4, also w₂= 4. Da wir im Set zwei Gegenstände mit den Gewichten 3 und 4 haben und das Gewicht des Rucksacks 5 beträgt, können wir einen Gegenstand mit dem Gewicht 4 in einen Rucksack stecken und der dem Gewicht entsprechende Gewinn beträgt 3, also addieren wir 3 bei M[2][5] wird wie folgt angezeigt:

Wenn i = 2, W = 6

Das dem Wert 2 entsprechende Gewicht ist 4, also w₂= 4. Da wir in der Menge zwei Gegenstände mit den Gewichten 3 und 4 haben und das Gewicht des Rucksacks 6 beträgt, können wir einen Gegenstand mit dem Gewicht 4 in einen Rucksack stecken und der dem Gewicht entsprechende Gewinn beträgt 3, also addieren wir 3 bei M[2][6] wird wie folgt angezeigt:

Wenn i = 2, W = 7

Das dem Wert 2 entsprechende Gewicht ist 4, also w₂= 4. Da wir in der Menge zwei Gegenstände mit den Gewichten 3 und 4 haben und das Gewicht des Rucksacks 7 beträgt, können wir Gegenstände mit den Gewichten 4 und 3 in einen Rucksack stecken und die den Gewichten entsprechenden Gewinne betragen 2 und 3; Daher beträgt der Gesamtgewinn 5, also addieren wir 5 bei M[2][7], wie unten gezeigt:

Wenn i = 2, W = 8

Das dem Wert 2 entsprechende Gewicht ist 4, also w₂= 4. Da wir in der Menge zwei Gegenstände mit den Gewichten 3 und 4 haben und das Gewicht des Rucksacks 7 beträgt, können wir Gegenstände mit den Gewichten 4 und 3 in einen Rucksack stecken und die den Gewichten entsprechenden Gewinne betragen 2 und 3; Daher beträgt der Gesamtgewinn 5, also addieren wir 5 bei M[2][7], wie unten gezeigt:

Jetzt wird der Wert von „i“ erhöht und beträgt 3.

Wenn i = 3, W = 1

String-Array

Das dem Wert 3 entsprechende Gewicht ist 5, also w₃= 5. Da wir in der Menge drei Gegenstände mit den Gewichten 3, 4 und 5 haben und das Gewicht des Rucksacks 1 beträgt, können wir keinen der Gegenstände in einen Rucksack stecken, also addieren wir 0 bei M[3][ 1] wie folgt dargestellt:

Wenn i = 3, W = 2

Das dem Wert 3 entsprechende Gewicht ist 5, also w₃= 5. Da wir in der Menge drei Gegenstände mit den Gewichten 3, 4 und 5 haben und das Gewicht des Rucksacks 1 beträgt, können wir keinen der Gegenstände in einen Rucksack stecken, also addieren wir 0 bei M[3][ 2] wie folgt dargestellt:

Wenn i = 3, W = 3

Das dem Wert 3 entsprechende Gewicht ist 5, also w₃= 5. Da wir drei Gegenstände in der Menge mit den Gewichten 3, 4 und 5 haben und das Gewicht des Rucksacks 3 beträgt, kann der Gegenstand mit dem Gewicht 3 in den Rucksack gesteckt werden und der dem Gegenstand entsprechende Gewinn beträgt 2, also fügen wir 2 bei M[3][3] hinzu, wie unten gezeigt:

Wenn i = 3, W = 4

Das dem Wert 3 entsprechende Gewicht ist 5, also w₃= 5. Da wir drei Gegenstände in der Menge mit den Gewichten 3, 4 und 5 haben und das Gewicht des Rucksacks 4 beträgt, können wir den Gegenstand entweder mit dem Gewicht 3 oder 4 behalten; Der Gewinn (3), der dem Gewicht 4 entspricht, ist größer als der Gewinn, der dem Gewicht 3 entspricht, also addieren wir 3 bei M[3][4], wie unten gezeigt:

Wenn i = 3, W = 5

Das dem Wert 3 entsprechende Gewicht ist 5, also w₃= 5. Da wir drei Gegenstände in der Menge mit den Gewichten 3, 4 und 5 haben und das Gewicht des Rucksacks 5 beträgt, können wir den Gegenstand entweder mit dem Gewicht 3, 4 oder 5 behalten; Der Gewinn (3), der dem Gewicht 4 entspricht, ist größer als der Gewinn, der den Gewichten 3 und 5 entspricht, also addieren wir 3 bei M[3][5], wie unten gezeigt:

Wenn i =3, W = 6

Das dem Wert 3 entsprechende Gewicht ist 5, also w₃= 5. Da wir drei Gegenstände in der Menge mit den Gewichten 3, 4 und 5 haben und das Gewicht des Rucksacks 6 beträgt, können wir den Gegenstand entweder mit dem Gewicht 3, 4 oder 5 behalten; Der Gewinn (3), der dem Gewicht 4 entspricht, ist größer als der Gewinn, der den Gewichten 3 und 5 entspricht, also addieren wir 3 bei M[3][6], wie unten gezeigt:

Wenn i =3, W = 7

Das dem Wert 3 entsprechende Gewicht ist 5, also w₃= 5. Da wir drei Gegenstände in der Menge mit den Gewichten 3, 4 und 5 haben und das Gewicht des Rucksacks 7 beträgt, können wir in diesem Fall beide Gegenstände mit den Gewichten 3 und 4 behalten, die Summe des Gewinns wäre gleich (2 + 3), also 5, also addieren wir 5 bei M[3][7], wie unten gezeigt:

Wenn i = 3, W = 8

Ausnahmebehandlung Java

Das dem Wert 3 entsprechende Gewicht ist 5, also w₃= 5. Da wir drei Elemente in der Menge mit den Gewichten 3, 4 und 5 haben und das Gewicht des Rucksacks 8 beträgt. In diesem Fall können wir beide Elemente mit den Gewichten 3 und 4 behalten, die Summe der Der Gewinn wäre gleich (2 + 3), also 5, also addieren wir 5 bei M[3][8], wie unten gezeigt:

Jetzt wird der Wert von „i“ erhöht und beträgt 4.

Wenn i = 4, W = 1

Das dem Wert 4 entsprechende Gewicht ist 6, also w₄= 6. Da wir vier Gegenstände in der Menge mit den Gewichten 3, 4, 5 und 6 haben und das Gewicht des Rucksacks 1 beträgt, ist das Gewicht aller Gegenstände größer als das Gewicht des Rucksacks, also können wir das nicht fügen Sie einen beliebigen Gegenstand in den Rucksack ein; Daher fügen wir 0 bei M[4][1] hinzu, wie unten gezeigt:

Wenn i = 4, W = 2

Das dem Wert 4 entsprechende Gewicht ist 6, also w₄= 6. Da wir vier Gegenstände in der Menge mit den Gewichten 3, 4, 5 und 6 haben und das Gewicht des Rucksacks 2 beträgt, ist das Gewicht aller Gegenstände größer als das Gewicht des Rucksacks, also können wir das nicht fügen Sie einen beliebigen Gegenstand in den Rucksack ein; Daher fügen wir 0 bei M[4][2] hinzu, wie unten gezeigt:

Wenn i = 4, W = 3

Das dem Wert 4 entsprechende Gewicht ist 6, also w₄= 6. Da wir vier Gegenstände im Satz mit den Gewichten 3, 4, 5 und 6 haben und das Gewicht des Rucksacks 3 beträgt, kann der Gegenstand mit einem Gewicht von 3 in den Rucksack gesteckt werden und der entsprechende Gewinn erzielt werden Gewicht 4 ist 2, also werden wir 2 bei M[4][3] hinzufügen, wie unten gezeigt:

Wenn i = 4, W = 4

Das dem Wert 4 entsprechende Gewicht ist 6, also w₄= 6. Da wir vier Gegenstände im Satz mit den Gewichten 3, 4, 5 und 6 haben und das Gewicht des Rucksacks 4 beträgt, kann der Gegenstand mit einem Gewicht von 4 in den Rucksack gesteckt werden und der entsprechende Gewinn erzielt werden Gewicht 4 ist 3, also werden wir 3 bei M[4][4] hinzufügen, wie unten gezeigt:

Wenn i = 4, W = 5

Das dem Wert 4 entsprechende Gewicht ist 6, also w₄= 6. Da wir vier Gegenstände im Satz mit den Gewichten 3, 4, 5 und 6 haben und das Gewicht des Rucksacks 5 beträgt, kann der Gegenstand mit einem Gewicht von 4 in den Rucksack gesteckt werden und der entsprechende Gewinn erzielt werden Gewicht 4 ist 3, also werden wir 3 bei M[4][5] hinzufügen, wie unten gezeigt:

Wenn i = 4, W = 6

Das dem Wert 4 entsprechende Gewicht ist 6, also w₄= 6. Da wir vier Gegenstände in der Menge mit den Gewichten 3, 4, 5 und 6 haben und das Gewicht des Rucksacks 6 beträgt, können wir in diesem Fall die Gegenstände mit den Gewichten 3 und 4 in den Rucksack legen , 5 oder 6, aber der Gewinn, d. h. 4 entsprechend dem Gewicht 6, ist unter allen Posten am höchsten; Daher fügen wir 4 bei M[4][6] hinzu, wie unten gezeigt:

Wenn i = 4, W = 7

Das dem Wert 4 entsprechende Gewicht ist 6, also w₄= 6. Da wir vier Elemente in der Menge mit den Gewichten 3, 4, 5 und 6 haben und das Gewicht des Rucksacks 7 beträgt, ergibt sich hier das Maximum, wenn wir zwei Elemente mit den Gewichten 3 und 4 hinzufügen Gewinn, d. h. (2 + 3) ist gleich 5, also addieren wir 5 bei M[4][7], wie unten gezeigt:

Wenn i = 4, W = 8

Das dem Wert 4 entsprechende Gewicht ist 6, also w₄= 6. Da wir vier Elemente in der Menge mit den Gewichten 3, 4, 5 und 6 haben und das Gewicht des Rucksacks 8 beträgt, ergibt sich hier das Maximum, wenn wir zwei Elemente mit den Gewichten 3 und 4 hinzufügen Gewinn, d. h. (2 + 3) ist gleich 5, also addieren wir 5 bei M[4][8], wie unten gezeigt:

Wie wir in der obigen Tabelle sehen können, ist 5 der maximale Gewinn aller Einträge. Der Zeiger zeigt auf die letzte Zeile und die letzte Spalte mit 5 Werten. Jetzt vergleichen wir den Wert 5 mit der vorherigen Zeile; Wenn die vorherige Zeile, d. h. i = 3, den gleichen Wert 5 enthält, verschiebt sich der Zeiger nach oben. Da die vorherige Zeile den Wert 5 enthält, wird der Zeiger nach oben verschoben, wie in der folgenden Tabelle gezeigt:

Wieder vergleichen wir den Wert 5 aus der obigen Zeile, d. h. i = 2. Da die obige Zeile den Wert 5 enthält, wird der Zeiger erneut nach oben verschoben, wie in der folgenden Tabelle gezeigt:

Auch hier vergleichen wir den Wert 5 aus der obigen Zeile, d. h. i = 1. Da die obige Zeile nicht denselben Wert enthält, betrachten wir die Zeile i=1 und das der Zeile entsprechende Gewicht beträgt 4. Daher , wir haben das Gewicht 4 ausgewählt und die unten gezeigten Gewichte 5 und 6 verworfen:

x = { 1, 0, 0}

Der dem Gewicht entsprechende Gewinn beträgt 3. Daher ist der verbleibende Gewinn (5 - 3) gleich 2. Nun vergleichen wir diesen Wert 2 mit der Zeile i = 2. Da die Zeile (i = 1) den Wert 2 enthält ; Daher wurde der Zeiger wie unten gezeigt nach oben verschoben:

Wieder vergleichen wir den Wert 2 mit einer obigen Zeile, d. h. i = 1. Da die Zeile i = 0 den Wert 2 nicht enthält, wird Zeile i = 1 ausgewählt und das Gewicht, das i = 1 entspricht, wird mit 3 angezeigt unten:

X = {1, 1, 0, 0}

Der dem Gewicht entsprechende Gewinn beträgt 2. Daher beträgt der verbleibende Gewinn 0. Wir vergleichen den 0-Wert mit der obigen Zeile. Da die obige Zeile einen Wert von 0 enthält, der dieser Zeile entsprechende Gewinn jedoch 0 ist, werden in diesem Problem zwei Gewichte ausgewählt, d. h. 3 und 4, um den Gewinn zu maximieren.