Problem plecakowy: Różnice pomiędzy wersjami

Usunięte 126 bajtów ,  10 lat temu
WP:SK, drobne techniczne
m (robot dodaje: tr:Sırt çantası problemi)
(WP:SK, drobne techniczne)
[[GrafikaPlik:Knapsack.svg|thumb|300px|right|thumb|Które pudełka powinny być wybrane, aby zmaksymalizować wartość przedmiotów w plecaku i jednocześnie nie zabrać więcej niż 15 kg?]]
'''Dyskretny problem plecakowy''' ([[Językjęzyk angielski|ang.]] ''discrete knapsack problem'') jest jednym z najczęściej poruszanych [[problem optymalizacyjny|problemów optymalizacyjnych]]. Nazwa zagadnienia pochodzi od maksymalizacyjnego problemu wyboru przedmiotów, tak by ich sumaryczna wartość była jak największa i jednocześnie mieściły się w plecaku. Przy podanym zbiorze elementów o podanej wadze i wartości, należy wybrać taki podzbiór by suma wartości była możliwie jak największa, a suma wag była nie większa od danej pojemności plecaka.
 
Problem plecakowy często przedstawia się jako problem złodzieja rabującego sklep – znalazł on N towarów; j–ty przedmiot jest wart <math>c_{j}</math> oraz waży <math>w_{j}</math>. Złodziej dąży do zabrania ze sobą jak najwartościowszego łupu, przy czym nie może zabrać więcej niż B kilogramów. Nie może też zabierać ułamkowej części przedmiotów (byłoby to możliwe w ciągłym problemie plecakowym).
 
== Definicja ==
Definicja formalna: mamy do dys­pozycji plecak o maksymalnej pojemności <math>B</math> oraz zbiór <math>N</math> elementów <math>\{x_1, x_j, ..., x_N\}</math>, przy czym każdy element ma określoną wartość <math>c_{j}</math> oraz wielkość <math>w_{j}</math>.
 
'''Dyskretny problem plecakowy''' (ang. ''0-1 knapsack problem'')
: formalnie problem może być zdefiniowany:
: zmaksymalizuj <math>\sum_{j=1}^N c_j x_j.</math>
: przy założeniach: <math>\sum_{j=1}^N w_j x_j \le B, \quad \quad x_j = 0\;\mbox{lub}\;1, \quad j=1,\dots,n.</math>
 
'''Problem plecakowy''', w którym liczba elementów danego typu jest ograniczona przez podaną wartość (ang. ''bounded knapsack problem'').
: Formalnie:
: zmaksymalizuj <math>\sum_{j=1}^N c_j x_j.</math>
: przy założeniach: <math>\sum_{j=1}^N w_j x_j \le B, \quad \quad 0 \le x_j \le b_j, \quad j=1,\dots,n.</math>
 
Można rozważać także przypadek w którym nie ma wartości ograniczającej liczbę elementów danego typu (ang. ''unbounded knapsack problem'').
 
W '''ciągłym problemie plecakowym''' można brać ułamkowe części przedmiotów.
 
W przypadku, gdy problem jest rozważany przy założeniach, że
Pseudokod (rozwiązanie znajduje się w komórce A[W], tablica A[0..W] przechowuje wyniki, wagi znajdują się w tablicy w[1..n], a wartości w tablicy c[1..n]):
<pre>
for i:=0 to W do
A[i]:= 0
 
for i:=0 to W do
for j:=1 to n do
if ( w[j] <= i ) then //sprawdzenie czy j-ty element mieści się w plecaku o rozmiarze i
A[i] = max(A[i], A[i-w[j]] + c[j])
</pre>
 
Podobne rozwiązanie może zostać zastosowane dla dyskretnego problemu plecakowego, także działające w czasie pseudowielomianowym. Niech ''w<sub>1</sub>'', ..., ''w<sub>n</sub>'' będzie wagą elementów oraz ''c<sub>1</sub>'', ..., ''c<sub>n</sub>'' wartościami. Algorytm ma zmaksymalizować wartość elementów, przy zachowaniu sumy ich wagi mniejszej bądź równej ''W''. Niech ''A''(''i'', ''j'') będzie największą możliwą wartością, która może być otrzymana przy założeniu wagi mniejszej bądź równej ''j'' i wykorzystaniu pierwszych ''i'' elementów. ''A''(''n'',''W'') jest rozwiązaniem problemu.
 
Funkcję ''A''(''i'',''j'') definiowana jest rekurencyjnie:
* ''A''(0, ''j'') = 0
* ''A''(''i'', 0) = 0
* ''A''(''i'', ''j'') = ''A''(''i'' - 1, ''j'') jeśli w<sub>i</sub> > ''j''
* ''A''(''i'', ''j'') = max(''A''(''i'' - 1, ''j''), c<sub>i</sub> + ''A''(''i'' - 1, ''j'' - w<sub>i</sub>)) jeśli w<sub>i</sub> ≤ ''j''
 
Rozwiązaniem problemu jest wynik dla A(''n'',''W''). Do efektywnego wykonania algorytmu używa się tablicy do zapamiętywania obliczonych podproblemów. Złożoność obliczenia wynosi podobnie jak wyżej <math>\Theta(nW)</math>, podobnie jak złożoność pamięciowa. Przy niewielkich modyfikacjach można jednak zredukować ilość potrzebnej pamięci do rzędu <math>\Theta(W)</math>.
Pseudokod (tablica A[1..n,0..W] przechowuje wyniki, wagi znajdują się w tablicy w[1..n], a wartości w tablicy c[1..n], rozwiązanie znajduje się w komórce A[n,W]):
<pre>
for i:=0 to n do
A[i,0]:= 0
for j:=0 to W do
A[0,j]:= 0
 
for i:=1 to n do //rozważanie kolejno i pierwszych przedmiotów
for j:=0 to W do
if ( w[i] > j ) then //sprawdzenie czy i-ty element mieści się w plecaku o rozmiarze j
A[i,j] = A[i-1,j]
else
A[i,j] = max(A[i-1,j], A[i-1,j-w[i]] + c[i])
</pre>
 
=== Algorytm aproksymacyjny ===
[[GrafikaPlik:Knapsack greedy.svg|thumb|right|300px|W pierwszej części algorytmu zachłannego przedmioty są sortowane wg stosunku wartości do wagi (po lewej), po czym wybierane są kolejno od góry te elementy które się jeszcze mieszą w plecaku. W wyniku wybrane zostały przedmioty o wartości 11$ i wadze 11kg, optymalny wynik to przedmioty o wadze 14kg i wartości 12$.]]
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 ''k'' jest maksymalną wartością przedmiotów w optymalnie upakowanym plecaku, algorytm zachłanny osiąga wyniki nie gorsze niż ''k''/2<ref name="uni-freiburg">http://www.informatik.uni-freiburg.de/~souza/knapsack.pdf</ref>. Złożoność obliczeniowa algorytmu zależy od sortowania (<math>\Theta(n \cdot \log{n})</math>).
 
aktualna_waga := aktualna_waga + w[i]
</pre>
Po wykonaniu tej części algorytmu należy porównać wynik z plecakiem w którym jest przedmiot o największej wartości<ref name="uni-freiburg"/>.
 
Po raz pierwszy zachłanny algorytm aproksymacyjny został zaproponowany przez [[George Dantzig|George'a Dantziga]] w [[1957]] roku.
 
== Bibliografia ==
* {{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
| imię2=David J.
| autor link=
| inni=
| 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
| imię2=Paolo
| autor link=
| inni=
| 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
| imię2=Ulrich
| nazwisko3=Pisinger
| imię3=David| tytuł=Knapsack Problems
| autor link=
| inni=
| tytuł=Knapsack Problems
| data=
| wydawca=Springer
| strony=
}}
* {{Cytuj książkę
| nazwisko= Cormen
| imię=Thomas H
| nazwisko4= Diks
| imię4=Krzysztof
| inni=
| tytuł= Wprowadzenie do algorytmów
| data=2003
}}
 
== {{Przypisy ==}}
<references/>
 
== Linki zewnętrzne ==
* [http://www.cse.unl.edu/~goddard/Courses/CSCE310J/Lectures/Lecture8-DynamicProgramming.pdf Wykład dotyczący problemu plecakowego]
 
[[Kategoria:Kryptologia]]