Problem plecakowy: Różnice pomiędzy wersjami

Usunięte 31 bajtów ,  6 lat temu
(Poprawiona literówka w przypisie zdjecia)
 
=== Ciągły problem plecakowy ===
Można go rozwiązać za pomocą algorytmu zachłannego, takiego samego jak w przypadku aproksymacyjnego algorytmu dla dyskretnego problemu plecakowego: obliczyć dla każdego elementu stosunek wartości do wagi <math>h_j = \frac{c_j}{w_j}</math>, uszeregować uzyskane wartości od największej do najmniejszej (można to zrobić w czasie <math>\Theta(n \cdot \log{n})</math>), a następnie wstawiać kolejne elementy do plecaka dopóki <math>\sum w_j < B</math>. Jest to rozwiązanie optymalne.
 
== Bibliografia ==
Anonimowy użytkownik