0/1-Rucksack-Problem

Gegeben ein Rucksack mit Kapazität c . Gegeben n Objekte 1,2,3,...,n . Objekt i habe Gewicht w_i und Profit p_i . Ziel ist es, den Rucksack mit größtmöglichem Profit zu füllen, d.h., gesucht sind v₁,v₂,...,v_n $\in$ {0,1} mit

und

wird maximiert.

Der naive Lösungsansatz überprüft alle 2ⁿ Möglichkeiten. Ein Dynamic-Programming-Ansatz definiert

F[i,x] : = maximaler Profit, den die Objekte 1,...,i in einem Rucksack mit Kapazität x erreichen können.

Offenbar

Eine iterative Formulierung füllt die Profitmatrix F zeilenweise:

FOR x := 1 TO w₁ -1 DO F[1,x] := 0 END;
FOR x := w₁ TO c DO F[1,x] := p₁ END;

FOR i := 2 TO n DO
     FOR x := 1 TO c DO
         F[i, x] := max { F[i-1,x], F[i-1, x- w_i ] + p_i}
     END
END Die Laufzeit beträgt O(n · c) .

Bemerkung:

Dies ist ein Exponentialzeitalgorithmus, da der Wert von c exponentiell zu seiner Darstellung ist.

Einträge der Profitmatrix F für das 0/1 -Rucksack-Problem. Für die Berechnung F[i,x] sind F[i - 1,x] und F[i - 1,x - w_i] notwendig.

Zur parallelen Abarbeitung mit einer CREW-PRAM verwendet man c Prozessoren. Während der i -ten Iteration ist Prozessor P_x zuständig für die Bestimmung von F[i,x] . Die Laufzeit beträgt offenbar O(n) , die Kosten O(n · c) , also liegt ein kostenoptimaler Algorithmus vor.

Zur parallelen Abarbeitung auf einem Hypercube verwendet man c Prozessoren. Jeder Prozessor kennt alle Gewichte w_i und alle Profitwerte p_i . Prozessor P_x ist zuständig für Spalte x der Profitmatrix F . Während der i -ten Iteration kann P_x auf das lokal vorhandene F[i - 1,x] zugreifen; der Wert F[i - 1,x - w_i] muß besorgt werden durch einen zyklischen Shift über die Distanz w_i , ausgeführt von allen Prozessoren. Die Laufzeit hierfür beträgt log (c) . Die Gesamtzeit beträgt daher O(n · log c) , die Kosten O(n · c · log c) .

Bei p Prozessoren im Hypercube ist jeder Prozessor für c/p Spalten zuständig. Während der i -ten Iteration kann Prozessor P_x auf c/p lokale Werte zugreifen und muß weitere c/p Werte durch einen zyklischen Shift besorgen. Die Zeit dafür beträgt c/p + log p . Die Gesamtzeit beträgt daher O(n · c/p + n · log p) , die Kosten O(n · c + n · p · log p) . Für c = $\Omega$(p · log p) ist dies kostenoptimal.