Problem plecakowy: Różnice pomiędzy wersjami
Poprawiona literówka w przypisie zdjecia
m (niedozwolone komentarze) |
(Poprawiona literówka w przypisie zdjecia) |
||
|
=== Algorytm aproksymacyjny ===
[[Plik:Knapsack greedy.svg|thumb|300px|W pierwszej części algorytmu zachłannego przedmioty są sortowane według stosunku wartości do wagi (po lewej), po czym wybierane są kolejno od góry te elementy które się jeszcze
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>).
| |||