DAA - 0-1 Rucksack

In diesem Tutorial haben wir zuvor das Fractional Knapsack-Problem unter Verwendung des Greedy-Ansatzes erörtert. Wir haben gezeigt, dass der Greedy-Ansatz eine optimale Lösung für Fractional Knapsack bietet. In diesem Kapitel werden jedoch das 0-1-Rucksackproblem und seine Analyse behandelt.

In 0-1 Knapsack können Gegenstände nicht zerbrochen werden, was bedeutet, dass der Dieb den Gegenstand als Ganzes nehmen oder verlassen sollte. Dies ist der Grund, warum man es als 0-1 Knapsack bezeichnet.

Daher ist im Fall von 0-1 Knapsack der Wert von x_i Kann beides sein 0 oder 1, wo andere Einschränkungen gleich bleiben.

0-1 Rucksack kann nicht durch gierigen Ansatz gelöst werden. Ein gieriger Ansatz gewährleistet keine optimale Lösung. In vielen Fällen kann der gierige Ansatz eine optimale Lösung bieten.

Die folgenden Beispiele begründen unsere Aussage.

Beispiel 1

Nehmen wir an, dass die Kapazität des Rucksacks W = 25 beträgt und die Elemente wie in der folgenden Tabelle gezeigt sind.

Artikel	EIN	B.	C.	D.
Profitieren	24	18	18	10
Gewicht	24	10	10	7

Ohne Berücksichtigung des Gewinns pro Gewichtseinheit (p_i/w_i), wenn wir den gierigen Ansatz anwenden, um dieses Problem zu lösen, erster Punkt Awird ausgewählt , da es max beitragen _i mum Gewinn unter allen Elementen.

Nach Auswahl des Elements Awird kein Element mehr ausgewählt. Daher beträgt für diesen gegebenen Satz von Gegenständen der Gesamtgewinn24. Während die optimale Lösung durch Auswahl von Elementen erreicht werden kann,B und C, wobei der Gesamtgewinn 18 + 18 = 36 beträgt.

Beispiel-2

Anstatt die Elemente basierend auf dem Gesamtnutzen auszuwählen, werden in diesem Beispiel die Elemente basierend auf dem Verhältnis p _i / w _{i ausgewählt} . Nehmen wir an, dass die Kapazität des Rucksacks W = 60 beträgt und die Elemente wie in der folgenden Tabelle gezeigt sind.

Artikel	EIN	B.	C.
Preis	100	280	120
Gewicht	10	40	20
Verhältnis	10	7	6

Mit dem Greedy-Ansatz, erster Punkt Aist ausgewählt. Dann der nächste PunktBist gewählt. Daher ist der Gesamtgewinn100 + 280 = 380. Die optimale Lösung dieser Instanz kann jedoch durch Auswahl von Elementen erreicht werden.B und C, wo der Gesamtgewinn ist 280 + 120 = 400.

Daraus kann geschlossen werden, dass der gierige Ansatz möglicherweise keine optimale Lösung bietet.

Um 0-1 Knapsack zu lösen, ist ein dynamischer Programmieransatz erforderlich.

Problemstellung

Ein Dieb raubt ein Geschäft und kann einen max tragen _i mal GewichtWin seinen Rucksack. Es gibtn Artikel und Gewicht von i^th Artikel ist w_i und der Gewinn der Auswahl dieses Artikels ist p_i. Welche Gegenstände sollte der Dieb mitnehmen?

Dynamischer Programmieransatz

Lassen i Seien Sie der Artikel mit der höchsten Nummer in einer optimalen Lösung S zum WDollar. DannS^' = S - {i} ist eine optimale Lösung für W - w_i Dollar und der Wert der Lösung S ist V_i plus den Wert des Unterproblems.

Wir können diese Tatsache in der folgenden Formel ausdrücken: define c[i, w] die Lösung für Gegenstände sein 1,2, … , iund der max _i mum Gewichtw.

Der Algorithmus verwendet die folgenden Eingaben

• Der max _i mum GewichtW

• Die Anzahl der Elemente n

• Die zwei Sequenzen v = <v₁, v₂, …, v_n> und w = <w₁, w₂, …, w_n>

Dynamic-0-1-knapsack (v, w, n, W) 
for w = 0 to W do 
   c[0, w] = 0 
for i = 1 to n do 
   c[i, 0] = 0 
   for w = 1 to W do 
      if wi ≤ w then 
         if vi + c[i-1, w-wi] then 
            c[i, w] = vi + c[i-1, w-wi] 
         else c[i, w] = c[i-1, w] 
      else 
         c[i, w] = c[i-1, w]

Die Menge der zu entnehmenden Gegenstände kann ab der Tabelle aus der Tabelle abgeleitet werden c[n, w] und rückwärts verfolgen, woher die optimalen Werte kamen.

Wenn c [i, w] = c [i-1, w] , dann Punkti ist nicht Teil der Lösung, und wir verfolgen weiter mit c[i-1, w]. Ansonsten Artikeli ist Teil der Lösung, und wir verfolgen weiter mit c[i-1, w-W].

Analyse

Dieser Algorithmus benötigt θ ( n , w ) mal, da Tabelle c ( n + 1) ( w + 1) Einträge hat, wobei jeder Eintrag θ (1) Zeit zum Berechnen benötigt.