Problem plecakowy: Różnice pomiędzy wersjami
| [wersja przejrzana] | [wersja przejrzana] |
Usunięta treść Dodana treść
m r2.6.5) (robot dodaje: sl:Preprosti problem nahrbtnika |
→Rozwiązania dynamiczne: A(i) = max{c(j) |
||
Linia 46:
''A''(''i'') jest zdefiniowane rekurencyjnie:
* ''A''(0) = 0
* ''A''(''i'') = max { ''c<sub>j</sub>'' + ''A''(''i'' − ''w<sub>j</sub>'') : ''w<sub>j</sub>'' ≤ ''i'' }
Rozwiązanie dla pustego plecaka jest równe zero. Obliczenie wyników kolejno dla ''A''(0), ''A''(1)... aż do ''A''(''W'') pozwala obliczyć wynik. Ponieważ obliczenie ''A''(''i'') wymaga sprawdzenia ''n'' elementów, a wartości ''A''(''i'') do obliczenia jest ''W'', złożoność obliczeniowa programu wynosi <math>\Theta(nW)</math>.
| |||