Problem plecakowy: Różnice pomiędzy wersjami

Dodane 56 bajtów ,  10 lat temu
m
m (Wycofano edycje użytkownika 109.243.186.152 (dyskusja). Autor przywróconej wersji to PawełMM.)
 
=== 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 1. i 3. o łącznej wartości 11$ i wadze 11kg,11 optymalnykg. wynikOptymalnym towynikiem byłyby jednak przedmioty 1. i 5. o łącznej wadze 15kg14 kg i wartości 1312$.]]
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>).
 
64 401

edycji