Problem plecakowy: Różnice pomiędzy wersjami

Dodane 44 bajty ,  5 lat temu
nie uwglednili przypadku w którym nie nie da sie do konca pleceka zapełnić. Ogólnie ktoś zrobił kalke z angielskiego i jest duzo bledów w zalozeniach z chmurki
(nie uwglednili przypadku w którym nie nie da sie do konca pleceka zapełnić. Ogólnie ktoś zrobił kalke z angielskiego i jest duzo bledów w zalozeniach z chmurki)
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 ''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ć sumę wartości elementów, przy zachowaniu sumy ich wagi mniejszej bądź równej ''W''. Niech ''A''(''i'') będzie największą możliwą wartością, która może być otrzymana przy założeniu wagi mniejszej bądź równej ''i''. ''A''(''W'') jest rozwiązaniem problemu.
 
''A''(''i'') jest zdefiniowane rekurencyjnie:
* ''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. Po obliczeniu wysztkich wartości mozna odszukać najlepsze rozwiązanie w czasie n. 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>.
 
Powyższa złożoność nie neguje faktu, że problem plecakowy jest [[problem NP zupełny|NP zupełny]], ponieważ ''W'', w przeciwieństwie do ''n'', nie jest proporcjonalne do rozmiaru danych wejściowych dla problemu. Rozmiar wejścia jest proporcjonalny do ilości bitów w liczbie ''W'', nie do wartości ''W''.
Anonimowy użytkownik