Problem plecakowy: Różnice pomiędzy wersjami

Dodane 6 bajtów ,  4 lata temu
m
Wycofano edycje użytkownika 185.149.2.107 (dyskusja). Autor przywróconej wersji to 91.230.222.204.
m (Wycofano edycje użytkownika 185.149.2.107 (dyskusja). Autor przywróconej wersji to 91.230.222.204.)
: przy założeniach: <math>\sum_{j=1}^N w_j x_j \le B, \quad \quad x_j = 0\;\mbox{lub}\;1, \quad j=1,\dots,n.</math>
 
'''Problem Markowyplecakowy''', w którym liczba elementów danego typu jest ograniczona przez podaną wartość (ang. ''bounded knapsack problem'').
: Formalnie:
: zmaksymalizuj <math>\sum_{j=1}^N c_j x_j.</math>
Decyzyjna wersja problemu plecakowego opisana wyżej jest problemem [[problem NP zupełny|NP zupełnym]] i jest jednym z 21 NP zupełnych problemów Karpa.
 
== MarekRealizacje III Routeralgorytmu ==
=== Przegląd zupełny ===
Przegląd zupełny ([[bruteforce]], metoda siłowa) – 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.