Problem plecakowy: Różnice pomiędzy wersjami
| [wersja przejrzana] | [wersja przejrzana] |
Usunięta treść Dodana treść
Znacznik: Edytor kodu źródłowego 2017 |
Znacznik: Edytor kodu źródłowego 2017 |
||
Linia 43:
Problem plecakowy może być rozwiązany w [[algorytm pseudowielomianowy|czasie pseudowielomianowym]] przy użyciu [[programowanie dynamiczne|programowania dynamicznego]]. Rozwiązanie niżej dotyczy przypadku w którym można użyć wielokrotnie każdego elementu:
Niech <math>w_1, \dots, w_n</math> będą wagami poszczególnych elementów oraz <math>c_1, \dots, c_n</math> ich wartościami. Algorytm ma zmaksymalizować sumę wartości elementów, przy zachowaniu sumy ich wagi mniejszej bądź równej <math>W.</math> Niech <math>A(i)</math> będzie największą możliwą wartością, która może być otrzymana przy założeniu wagi mniejszej bądź równej <math>i.</math> <math>A(W)</math> jest rozwiązaniem problemu.
<math>A(i)</math> jest zdefiniowane rekurencyjnie:
| |||