Problem plecakowy: Różnice pomiędzy wersjami

[[Problem decyzyjny (teoria obliczeń)|Decyzyjna]] wersja przedstawionego zagadnienia to pytanie „czy wartość co najmniej ''<math>C''</math> może być osiągnięta bez przekraczania wagi ''<math>W''</math>?”

Definicja formalna: mamy do dyspozycji plecak o maksymalnej pojemności <math>B</math> oraz zbiór <math>N</math> elementów <math>\{x_1, x_j, ...\dots, x_N\},</math> przy czym każdy element ma określoną wartość <math>c_j</math> oraz wielkość <math>w_j.</math>

: zmaksymalizuj <math>\sum_{j=1}^N c_j x_j.</math>

: zmaksymalizuj <math>\sum_{j=1}^N c_j x_j.</math>

* jest problemem decyzyjnym,

* jest dyskretny,

* dla każdego elementu waga równa się wartości <math>w_j=c_j,</math>

utożsamiany jest z problemem: czy dla danego zbioru liczb całkowitych istnieje taki jego podzbiór, że suma jego liczb wynosi dokładnie ''<math>W''</math>? Zagadnienie to nazywane jest [[problem sumy podzbioru|problemem sumy podzbioru]].

Przegląd zupełny ([[Atak brute force|bruteforce]], metoda siłowa) – metoda nieefektywna obliczeniowo (ale optymalna, gdyż znajduje rozwiązanie najlepsze); w jego przypadku [[złożoność obliczeniowa]] algorytmu wyniesie <math>\Theta(2^n),</math> co zdecydowanie zawyży czas działania dla dużych n. Złożoność wynosi <math>\Theta(2^n)</math> ponieważ jest tyle możliwych ciągów zero jedynkowych na n polach. Złożoność można również obliczyć ze wzoru dwumianowego Newtona ([[dwumian Newtona]]) podstawiając za, a i b jedynki.

Niech ''w<submath>1</sub>''w_1, ...\dots, ''w_{nw_n</submath>'' będzie wagą elementów oraz ''c<submath>1}''c_1, ...\dots, ''c<sub>nc_n</submath>'' wartościami. Algorytm ma zmaksymalizować sumę wartości elementów, przy zachowaniu sumy ich wagi mniejszej bądź równej ''<math>W''.</math> Niech ''<math>A''(''i'')</math> będzie największą możliwą wartością, która może być otrzymana przy założeniu wagi mniejszej bądź równej ''<math>i''.</math> ''<math>A''(''W'')</math> jest rozwiązaniem problemu.

''<math>A''(''i'')</math> jest zdefiniowane rekurencyjnie:

* ''<math>A''(0) = 0,</math>

* ''<math>A''(''i'') = \max \{''c_j''c_j + ''A''(''i'' –- ''w_j''w_j):\colon ''w_j''w_j ≤\leqslant ''i''\}.</math>

Rozwiązanie dla pustego plecaka jest równe zero. Obliczenie wyników kolejno dla ''<math>A''(0), ''A''(1)...\dots</math> aż do ''<math>A''(''W'')</math> pozwala obliczyć wynik. Ponieważ obliczenie ''<math>A''(''i'')</math> wymaga sprawdzenia ''<math>n''</math> elementów, a wartości ''<math>A''(''i'')</math> do obliczenia jest ''<math>W'',</math> złożoność obliczeniowa programu wynosi <math>\Theta(nW).</math>

Powyższa złożoność nie neguje faktu, że problem plecakowy jest [[Problem NP-zupełny|NP zupełny]], ponieważ ''<math>W'',</math> w przeciwieństwie do ''<math>n'',</math> nie jest proporcjonalne do rozmiaru danych wejściowych dla problemu. Rozmiar wejścia jest proporcjonalny do ilości bitów w liczbie ''<math>W'',</math> nie do wartości ''<math>W''.</math>

if ( w[j] <= i ) then //sprawdzenie czy j-ty element mieści się w plecaku o rozmiarze i

Podobne rozwiązanie może zostać zastosowane dla dyskretnego problemu plecakowego, także działające w czasie pseudowielomianowym. Niech ''w<submath>1</sub>''w_1, ...\dots, ''w_{nw_n</submath>'' będzie wagą elementów oraz ''c<submath>1}''c_1, ...\dots, ''c<sub>nc_n</submath>'' wartościami. Algorytm ma zmaksymalizować wartość elementów, przy zachowaniu sumy ich wagi mniejszej bądź równej ''<math>W''.</math> Niech ''<math>A''(''i'', ''j'')</math> będzie największą możliwą wartością, która może być otrzymana przy założeniu wagi mniejszej bądź równej ''<math>j''</math> i wykorzystaniu pierwszych ''<math>i''</math> elementów. ''<math>A''(''n'','' W'')</math> jest rozwiązaniem problemu.

Funkcję ''<math>A''(''i'',''j'')</math> definiowana jest rekurencyjnie:

for i:=1 to n do //rozważanie kolejno i pierwszych przedmiotów

if ( w[i] > j ) then //sprawdzenie czy i-ty element mieści się w plecaku o rozmiarze j

W wersji [[algorytm zachłanny|zachłannej]] [[algorytm aproksymacyjny]] sortuje elementy w kolejności malejącej porównując stosunek wartości do wagi elementu <math>h_j = \frac{c_j}{w_j}.</math> Następnie wstawia je kolejno zaczynając od przedmiotu o największym ilorazie do plecaka. Jeśli jakiś element nie mieści się w plecaku to jest omijany, a algorytm przechodzi do następnego. W algorytmie wybierany jest maksymalny wynik z tak obliczonego upakowania plecaka oraz plecaka z elementem o największej wartości. Jeśli ''<math>k''</math> jest maksymalną wartością przedmiotów w optymalnie upakowanym plecaku, algorytm zachłanny osiąga wyniki nie gorsze niż ''<math>k''/2</math><ref name="uni-freiburg">{{Cytuj |url=http://www.informatik.uni-freiburg.de/~souza/knapsack.pdf |tytuł=Algorithms and Complexity (Freiburg)<!-- Tytuł wygenerowany przez bota --> |opublikowany=www.informatik.uni-freiburg.de |język=de |data dostępu=2017-11-26}}</ref>. Złożoność obliczeniowa algorytmu zależy od sortowania <math>(\Theta(n \cdot \log{n})).</math>.

* {{Cytuj książkę |nazwisko = Garey |imię = Michael R. |nazwisko2 = Johnson |imię2 = David J.| tytuł = Computers and intractability: a guide to the theory of NP-completeness |data = 1979 |wydawca = W.H. Freeman |miejsce = San Francisco |isbn = 0-7167-1045-5 |strony =}}

* {{Cytuj książkę |nazwisko = Martello |imię = Silvano |nazwisko2 = Toth |imię2 = Paolo| tytuł = Knapsack problems: algorithms and computer implementations |data = 1990 |wydawca = J. Wiley |miejsce = Chichester |isbn = 0-471-92420-2 |strony =}}

* {{Cytuj książkę |nazwisko = Kellerer |imię = Hans |nazwisko2 = Pferschy |imię2 = Ulrich |nazwisko3 = Pisinger |imię3 = David| tytuł = Knapsack Problems |wydawca = Springer |miejsce = |isbn = 3-540-40286-1 |strony =}}

* {{Cytuj książkę |nazwisko = Cormen |imię = Thomas H. |nazwisko2 = Leiserson |imię2 = Charles E. |nazwisko3 = Rivest |imię3 = Ronald L. |nazwisko4 = Stein |imię4 = Clifford |tytuł = Wprowadzenie do algorytmów |data = 2003 |wydawca = Wydawnictwa Naukowo-Techniczne |miejsce = Warszawa |isbn = 83-204-2800-9 |strony =}}