DAA - plecak 0-1

W tym samouczku omówiliśmy wcześniej problem z ułamkowym plecakiem przy użyciu podejścia Chciwego. Pokazaliśmy, że podejście Greedy daje optymalne rozwiązanie dla Fractional Knapsack. Jednak w tym rozdziale omówimy problem plecakowy 0-1 i jego analizę.

W plecaku 0-1 przedmioty nie mogą zostać zniszczone, co oznacza, że ​​złodziej powinien zabrać przedmiot w całości lub powinien go zostawić. Z tego powodu nazywa się go plecakiem 0-1.

Stąd w przypadku plecaka 0-1 wartość x_i może być 0 lub 1, gdzie inne ograniczenia pozostają takie same.

0-1 Plecak nie może być rozwiązany przez Chciwość. Chciwe podejście nie zapewnia optymalnego rozwiązania. W wielu przypadkach podejście Greedy może dać optymalne rozwiązanie.

Poniższe przykłady potwierdzą nasze stwierdzenie.

Przykład 1

Weźmy pod uwagę, że pojemność plecaka wynosi W = 25, a przedmioty są zgodne z poniższą tabelą.

Pozycja	ZA	b	do	re
Zysk	24	18	18	10
Waga	24	10	10	7

Bez uwzględnienia zysku na jednostkę masy (p_i/w_i), jeśli zastosujemy podejście Greedy do rozwiązania tego problemu, pierwsza pozycja Azostanie wybrany jako przyczyni max _í mama zysk spośród wszystkich elementów.

Po wybraniu pozycji A, żaden element nie zostanie wybrany. Stąd dla tego zbioru pozycji całkowity zysk wynosi24. Natomiast optymalne rozwiązanie można osiągnąć wybierając pozycje,B i C, gdzie całkowity zysk to 18 + 18 = 36.

Przykład-2

Zamiast wybierać elementy na podstawie ogólnej korzyści, w tym przykładzie elementy są wybierane na podstawie współczynnika p _I / w _I . Weźmy pod uwagę, że pojemność plecaka wynosi W = 60, a pozycje są zgodne z poniższą tabelą.

Pozycja	ZA	b	do
Cena £	100	280	120
Waga	10	40	20
Stosunek	10	7	6

Korzystając z podejścia Greedy, pierwsza pozycja Ajest zaznaczony. Następnie następny elementBjest wybrany. Stąd całkowity zysk wynosi100 + 280 = 380. Jednak optymalne rozwiązanie tej instancji można osiągnąć wybierając elementy,B i C, gdzie jest całkowity zysk 280 + 120 = 400.

W związku z tym można stwierdzić, że podejście Greedy może nie dać optymalnego rozwiązania.

Aby rozwiązać 0-1 Knapsack, wymagane jest podejście do programowania dynamicznego.

Stwierdzenie problemu

Złodziej jest rabowania do przechowywania i mogą zawierać maksymalny _ı mal ciężarWdo jego plecaka. Tam sąn sztuk i wagę i^th pozycja jest w_i a zysk z wyboru tej pozycji wynosi p_i. Jakie przedmioty powinien zabrać złodziej?

Podejście do programowania dynamicznego

Pozwolić i być pozycją o najwyższym numerze w optymalnym rozwiązaniu S dla Wdolarów. NastępnieS^' = S - {i} jest optymalnym rozwiązaniem dla W - w_i dolarów i wartość rozwiązania S jest V_i plus wartość podproblemu.

Fakt ten możemy wyrazić wzorem: zdefiniuj c[i, w] być rozwiązaniem dla przedmiotów 1,2, … , ioraz maksymalną _i ciężar mamaw.

Algorytm przyjmuje następujące dane wejściowe

• Maksymalne _i ciężar mamaW

• Liczba sztuk n

• Dwie sekwencje v = <v₁, v₂, …, v_n> i 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]

Zestaw przedmiotów do wzięcia można wywnioskować z tabeli, zaczynając od c[n, w] i śledzenie wstecz, skąd pochodzą optymalne wartości.

Jeśli c [i, w] = c [i-1, w] , to elementi nie jest częścią rozwiązania i kontynuujemy śledzenie za pomocą c[i-1, w]. W przeciwnym razie pozi jest częścią rozwiązania i kontynuujemy śledzenie za pomocą c[i-1, w-W].

Analiza

Algorytm ten wymaga θ ( n , w ) razy, ponieważ tabela c ma ( n + 1). ( W + 1) wpisów, gdzie każdy wpis wymaga θ (1) czasu do obliczenia.