Problem plecakowy: Różnice pomiędzy wersjami
| [wersja nieprzejrzana] | [wersja nieprzejrzana] |
Usunięta treść Dodana treść
Linia 39:
Przegląd zupełny ([[bruteforce]], metoda Tymeckiego) – metoda nieefektywna obliczeniowo (ale optymalna, gdyż znajduje rozwiązanie najlepsze); w jego przypadku [[złożoność obliczeniowa]] algorytmu wyniesie <math>\Theta(2^n)</math>, co zdecydowanie zawyży czas działania dla dużych n. Złożoność wynosi <math>\Theta(2^n)</math> ponieważ jest tyle możliwych ciągów zero jedynkowych na n polach. Złożoność można również obliczyć ze wzoru dwumianowego Newtona ([[dwumian Newtona]]) podstawiając za a i b jedynki.
=== Rozwiązania dynamiczne[ten co to pisał coś pokićkał] ===
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:
Linia 63:
</pre>
Podobne rozwiązanie może zostać zastosowane dla[a powyższy to jaki??] dyskretnego problemu plecakowego, także działające w czasie pseudowielomianowym. Niech ''w<sub>1</sub>'', ..., ''w<sub>n</sub>'' będzie wagą elementów oraz ''c<sub>1</sub>'', ..., ''c<sub>n</sub>'' wartościami. Algorytm ma zmaksymalizować wartość elementów, przy zachowaniu sumy ich wagi mniejszej bądź równej ''W''. Niech ''A''(''i'', ''j'') będzie największą możliwą wartością, która może być otrzymana przy założeniu wagi mniejszej bądź równej ''j'' i wykorzystaniu pierwszych ''i'' elementów. ''A''(''n'',''W'') jest rozwiązaniem problemu.
Funkcję ''A''(''i'',''j'') definiowana jest rekurencyjnie:
| |||