Problem plecakowy: Różnice pomiędzy wersjami

Przejdź do nawigacji Przejdź do wyszukiwania

Problem plecakowy (edytuj)

Wersja z 14:47, 21 mar 2016

Usunięte 104 bajty ,  6 lat temu
m
niedozwolone komentarze
(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)
m (niedozwolone komentarze)
== Realizacje algorytmu ==
=== Przegląd zupełny ===
Przegląd zupełny ([[bruteforce]], metoda Tymeckiegosił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.
 
=== 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:
 
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''.
</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:
Źródło: „https://pl.wikipedia.org/wiki/Specjalna:Różnica_mobilna/45361559”

Menu nawigacyjne