Wariant problemu plecakowego

Jak podchodziłbyś do problemu plecaka w sytuacji dynamicznego programowania, gdybyś musiał teraz ograniczyć liczbę przedmiotów w plecaku o stałe $p$ ? Jest to ten sam problem (maksymalna waga $W$ , każdy przedmiot ma wartość $v$ i ciężar $w$ ), ale można dodać tylko $p$ przedmiotów do plecaka i oczywiście trzeba zoptymalizować wartość plecaka.

Czy potrzebujemy trzeciego wymiaru, czy moglibyśmy znaleźć inne podejście bez niego? Próbowałem po prostu dodać liczbę przedmiotów do plecaka w komórce i przyjąć maksymalną wartość na końcu z liczbą przedmiotów <= $p$ ale nie jest to NAJLEPSZE rozwiązanie.

Bardzo miłe pytanie!

Masz dwa razy rację:

1. Propagowanie liczby przedmiotów w plecaku nie prowadzi do optymalnych rozwiązań.
2. Jedno rozwiązanie polega na dodaniu trzeciego wymiaru. Jest to dość proste, ale należy przy tym wziąć pod uwagę kilka faktów. Zauważ jednak, że nie jest to jedyna alternatywa

Poniżej zakładam, że znasz rozwiązanie oparte na programowaniu dynamicznym. W szczególności nie będę omawiać sposobu przechodzenia do tyłu tabeli w celu ustalenia rozwiązania .

Najpierw skupmy się na typowym przypadku: liczba elementów jest nieograniczona . W tym przypadku wystarczy zbudować tabelę której T i , j zawiera optymalną wartość, gdy ogólna pojemność plecaka jest równa i i brane są pod uwagę tylko pierwsze j przedmioty. Stąd:$T$$T_{i,j}$$i$$j$

$T_{i,j} =\max\{T_{i,j-1}, T_{i-w_j,j-1}+v_j\}$

gdzie i oznaczają odpowiednio wagę i wartość tej pozycji. Jeśli jest ogólną pojemnością twojego plecaka i jest w sumie przedmiotów, optymalne rozwiązanie daje . Ten algorytm jest znany z działania w pseudo-wielomianowym czasie, a jedną z jego zalet jest to, że bierze pod uwagę tylko te kombinacje, które pasują do maksymalnej wydajności.v j j C N T C , $w_j$$v_j$$j$$C$$N$$T_{C, N}$

Jednak to nie wystarczy przy dodawaniu ograniczenia: maksymalna liczba elementów . Powodem jest to, że poprzednia formuła powtarzalności nie uwzględnia różnych kombinacji pozycji:$p$

1. Po pierwsze, jeśli następnie tak, że przez -ty element jest dodawany do plecaka pomimo maksymalna ilość elementów uznawanych, --- tak, że może być naruszenie swoje ograniczenia. Cóż, możesz ulec pokusie zastosowania poprzedniej formuły, śledząc liczbę elementów wstawianych na każdym kroku i nie dodawaj innych, jeśli liczba elementów w plecaku przekracza ale,$T_{i,j-1}<(T_{i-w_j,j-1}+v_j)$$T_{i,j}=(T_{i-w_j,j-1}+v_j)$$j$$p$$p$
2. Po drugie, jeśli to , aby ten element nie został dodany, ale może to być duży błąd, jeśli optymalne rozwiązanie już składa się z maksymalnej liczby elementów, które można wstawić do plecaka. Powodem jest to, że nie porównujemy odpowiednio: z jednej strony, aby zachować optymalne rozwiązanie składające się z elementów wybranych spośród poprzednich ; z drugiej strony, aby wstawić -ty element i dodatkowo rozważyć najlepszy podzbiór z wśród poprzednich .$T_{i,j-1}>(T_{i-w_j,j-1}+v_j)$$T_{i,j}=T_{i,j-1}$$T_{i,j-1}$$p$$(j-1)$$j$$(p-1)$$(j-1)$

Tak więc pierwsze rozwiązanie polega na dodaniu trzeciego wymiaru. W twoim przypadku, niech będzie optymalnym rozwiązaniem, gdy pojemność plecaka wynosi , brane są pod uwagę tylko pierwsze przedmioty i nie wolno umieszczać więcej niż przedmiotów w plecaku. Teraz,$T_{i, j, k}$$i$$j$$k$

• Jeśli dla liczby elementów ściśle mniejszych lub równych liczbie elementów, które można wstawić ( ), postępuj jak zwykle, ale używając tej samej wartości :$T_{i, j, k}$$j\leq k$$k$$T_{i,j,k} =\max\{T_{i,j-1,k}, T_{i-w_j,j-1,k}+v_j\}$
• Teraz, jeśli musisz obliczyć dla liczby elementów ściśle większych niż liczba elementów, które można wstawić ( ), to:$T_{i, j, k}$$j> k$$T_{i,j,k} =\max\{T_{i,j-1,k}, T_{i-w_j,j-1,k-1}+v_j\}$

Pierwsze wyrażenie powinno być jasne. Drugi działa, ponieważ -ta warstwa tabeli śledzi najlepszą kombinację elementów wśród pierwszych zgodnie z powyższym wymaganiem.$(k-1)$$T$$(k-1)$$(j-1)$

Wydajna implementacja tego algorytmu nie musi obliczać dla wszystkich . Zauważ, że poprzednie relacje powtarzalności dotyczą warstwy z a zatem możliwe jest przełączanie między dwiema kolejnymi warstwami (np. Jeśli jesteś zainteresowany optymalnym rozwiązaniem z , po prostu używasz dwóch kolejnych warstw: 0 oraz 1, 1 i 2, 2 i 3, 3 i 4 i gotowe). Innymi słowy, algorytm ten zajmuje dwukrotnie więcej pamięci wymaganej przez tradycyjne podejście oparte na programowaniu dynamicznym, a zatem może być nadal uruchomiony w czasie pseudo-wielomianowym. k k ( k - 1 ) k = $T_{i, j, k}$$k$$k$$(k-1)$$k=4$

Pamiętaj jednak, że nie jest to jedyne rozwiązanie! Jest jeszcze jeden, który może być bardziej elegancki. W poprzednich formułach uzyskaliśmy optymalne rozwiązanie, które składało się z nie więcej niż pozycji spośród pierwszych jako . Jednak powinno być jasne, że jest to dokładnie równe tylko przy użyciu oryginalnej tabeli !! tj. optymalne rozwiązanie z nie więcej niż pozycji można również znaleźć, biorąc pod uwagę optymalne rozwiązania z 1 pozycją, 2 pozycjami, 3 pozycjami, ...( j - 1 ) T i , j - 1 , k - 1 max p = 0 , j - 1 { T i , p } k ( j - 1 ) k$(k-1)$$(j-1)$$T_{i, j-1, k-1}$$\max\limits_{p=0,j-1}\{T_{i, p}\}$$k$$(j-1)$przedmioty ... Aby ten preparat działał, należy również śledzić liczbę elementów branych pod uwagę w każdym częściowym rozwiązaniu, tak aby potrzebne były dwie liczby całkowite na komórkę. To zajęcie pamięci skutkuje dokładnie tymi samymi wymaganiami pamięciowymi dla algorytmu pokazanego powyżej (przy użyciu trzeciego wymiaru w postaci warstw )$k$ .

Mam nadzieję że to pomoże,