w tym tutorialu, wcześniej omówiliśmy ułamkowy problem plecaka za pomocą chciwego podejścia. Pokazaliśmy, że chciwe podejście daje optymalne rozwiązanie dla ułamkowego plecaka. Jednak ten rozdział obejmie 0-1 problem Plecaka i jego analizę.
w plecaku 0-1 przedmioty nie mogą zostać złamane, co oznacza, że złodziej powinien zabrać przedmiot jako całość lub powinien go zostawić., To jest powód, dla którego nazwaliśmy go „0-1 Knapsack”.
dlatego w przypadku plecaka 0-1 wartość xi może wynosić 0 LUB 1, gdzie inne ograniczenia pozostają takie same.
0-1 Knapsack nie może być rozwiązany przez chciwe podejście. Chciwe podejście nie zapewnia optymalnego rozwiązania. W wielu przypadkach chciwe podejście może dać optymalne rozwiązanie.
poniższe przykłady utwierdzą naszą wypowiedź.
przykład-1
przyjrzyjmy się, że pojemność plecaka wynosi W = 25, A pozycje są jak pokazano w poniższej tabeli.,
| pozycja | A | B | d | |
|---|---|---|---|---|
| zysk | 24 | 18 | 10 | |
| waga | 24 | 10 | 10 | 7 |
bez uwzględnienia zysku na jednostkę wagi (pi/Wi), jeśli zastosujemy chciwe podejście do rozwiązania tego problemu, pierwsza pozycja a zostanie wybrana, ponieważ przyniesie maksymalny zysk wśród wszystkich elementów.,
Po wybraniu elementu A nie zostanie wybrany żaden element. Stąd, dla tego podanego zestawu pozycji całkowity zysk wynosi 24. Natomiast optymalne rozwiązanie można osiągnąć wybierając pozycje, B i C, gdzie całkowity zysk wynosi 18 + 18 = 36.
przykład-2
zamiast wybierać elementy na podstawie ogólnej korzyści, w tym przykładzie elementy są wybierane na podstawie stosunku pi / wi. Weźmy pod uwagę, że pojemność plecaka wynosi W = 60, a pozycje są jak pokazano w poniższej tabeli.,
| Item | A | B | C |
|---|---|---|---|
| Price | 100 | 280 | 120 |
| Weight | 10 | 40 | 20 |
| Ratio | 10 | 7 | 6 |
Using the Greedy approach, first item A is selected. Then, the next item B is chosen. Hence, the total profit is 100 + 280 = 380., Jednak optymalne rozwiązanie tego przypadku można osiągnąć wybierając pozycje, B i C, gdzie całkowity zysk wynosi 280 + 120 = 400.
stąd można wnioskować, że chciwe podejście może nie dać optymalnego rozwiązania.
aby rozwiązać 0-1 Knapsack, wymagane jest dynamiczne podejście programistyczne.
problem ze stwierdzeniem
złodziej obrabuje sklep i może nosić maksymalną wagę W do plecaka. Istnieje n elementów i waga it-tego elementu jest wi, a zysk z wyboru tego elementu jest pi. Jakie przedmioty powinien zabrać złodziej?,
podejście dynamiczno-programistyczne
niech będę najwyżej numerowanym elementem w optymalnym rozwiązaniu S dla W. Wtedy S ' = S – {i} jest rozwiązaniem optymalnym dla w-wi, a wartość rozwiązania S wynosi Vi plus wartość pod-problemu.
możemy wyrazić ten fakt w następującym wzorze: zdefiniuj c jako rozwiązanie dla pozycji 1,2, … , i oraz maksymalnej wagi w.,
algorytm pobiera następujące wejścia
-
Maksymalna waga W
-
liczba pozycji n
-
dwie sekwencje v = <v1, V2, …, VN> I w = <W1, W2, …, WN>
zestaw elementów do pobrania można wywnioskować z tabeli, zaczynając od C i śledząc wstecz, skąd pochodzą optymalne wartości.
Analiza
algorytm ten przyjmuje θ(n, w) razy tyle, ile ma tabela c (n + 1).(w + 1) wpisy, gdzie każdy wpis wymaga θ(1) czasu na obliczenie.,