Problem plecakowy: Różnice pomiędzy wersjami

Dodane 10 bajtów ,  9 lat temu
drobne redakcyjne
m (Bot: Dodanie tytułów do linków w przypisach (patrz FAQ); zmiany kosmetyczne)
(drobne redakcyjne)
 
=== Algorytm aproksymacyjny ===
[[Plik:Knapsack greedy.svg|thumb|300px|W pierwszej części algorytmu zachłannego przedmioty są sortowane wgwedług 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 1. i 3. o łącznej wartości 11$ i wadze 11 kg. Optymalnym wynikiem byłyby jednak przedmioty 1. i 5. o łącznej wadze 14 kg 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 Chair of Algorithms and Complexity (Freiburg)<!-- Tytuł wygenerowany przez bota -->]</ref>. Złożoność obliczeniowa algorytmu zależy od sortowania (<math>\Theta(n \cdot \log{n})</math>).
 
Pseudokod:
<pre>
posortuj nierosnąco przedmioty wgwedług wartości c[j]/w[j]
aktualna_waga:=0