Problem plecakowy: Różnice pomiędzy wersjami

Usunięte 1207 bajtów ,  10 lat temu
m (Wycofano edycje użytkownika 84.10.241.176 (dyskusja). Autor przywróconej wersji to 83.29.169.86.)
 
=== 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 15kg i wartości 13$.]]
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>).
 
Pseudokod:
<pre>
posortuj nierosnąco przedmioty wg wartości c[j]/w[j]
aktualna_waga:=0
 
for i:=1 to n do
if w[i] + aktualna_waga <= W then
dodaj i-ty przedmiot do plecaka
Anonimowy użytkownik