Problem plecakowy: Różnice pomiędzy wersjami

Rozmiar się nie zmienił ,  10 lat temu
optymalniejsze rozwiazanie (9+2+2+2)kg i (10+1+1+1)$
(WP:SK, drobne techniczne)
(optymalniejsze rozwiazanie (9+2+2+2)kg i (10+1+1+1)$)
 
=== Algorytm aproksymacyjny ===
[[Plik:Knapsack greedy.svg|thumb|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 14kg15kg i wartości 1213$.]]
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>).
 
Anonimowy użytkownik