Problem plecakowy: Różnice pomiędzy wersjami
| [wersja przejrzana] | [wersja przejrzana] |
Usunięta treść Dodana treść
m robot dodaje: tr:Sırt çantası problemi |
WP:SK, drobne techniczne |
||
Linia 1:
[[
'''Dyskretny problem plecakowy''' ([[
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).
Linia 9:
== Definicja ==
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, ..., 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
Linia 54:
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:
Linia 69:
* ''A''(0, ''j'') = 0
* ''A''(''i'', 0) = 0
* ''A''(''i'', ''j'') = ''A''(''i''
* ''A''(''i'', ''j'') = max(''A''(''i''
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>.
Linia 76:
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 ===
[[
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>).
Linia 103:
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.
Linia 111:
== 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▼
▲ | 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▼
▲ | 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
Linia 145 ⟶ 139:
| imię2=Ulrich
| nazwisko3=Pisinger
| imię3=David| tytuł=Knapsack Problems
| data=
| wydawca=Springer
Linia 155 ⟶ 146:
| strony=
}}
* {{Cytuj książkę
| nazwisko= Cormen
| imię=Thomas H
Linia 164 ⟶ 155:
| nazwisko4= Diks
| imię4=Krzysztof
| tytuł= Wprowadzenie do algorytmów
| data=2003
Linia 173 ⟶ 163:
}}
== Linki zewnętrzne ==
* [http://www.cse.unl.edu/~goddard/Courses/CSCE310J/Lectures/Lecture8-DynamicProgramming.pdf Wykład dotyczący problemu plecakowego]
[[Kategoria:Kryptologia]]
| |||