Problem plecakowy: Różnice pomiędzy wersjami

Dodane 57 bajtów ,  5 lat temu
Przegląd zupełny ([[bruteforce]], metoda Tymeckiego) – metoda nieefektywna obliczeniowo (ale optymalna, gdyż znajduje rozwiązanie najlepsze); w jego przypadku [[złożoność obliczeniowa]] al­gorytmu 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:
 
</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:
Anonimowy użytkownik