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ść xi 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 (pi/wi), 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ę ith pozycja jest wi a zysk z wyboru tej pozycji wynosi pi. 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 - wi dolarów i wartość rozwiązania S jest Vi 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 = <v1, v2, …, vn> i w = <w1, w2, …, wn>

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.