Omówienie zadania Pakowanie plecaka (II etap XXVIII OI)

Mamy \(n\) przedmiotów o wagach \(w_1,\ldots,w_n\). Dla każdego \(k\leq n\) obliczyć, jaki jest minimalny udźwig plecaka, do którego wejdzie co najmniej \(k\) przedmiotów, jeśli pakujemy je zachłannie (przedmioty próbujemy wkładać po kolei).

Podzadanie 1

Jeżeli ustalimy sobie rozmiar plecaka, to w czasie \(O(n)\) możemy zachłanną procedurą pakowania sprawdzić, ile przedmiotów zmieści się w plecaku. Jeśli rozważymy wszystkie możliwe rozmiary plecaka od 1 do \(S = \sum_i w_i\), da nam to algorytm o złożoności \(O(nS)\).

Ale nie musimy rozpatrywać wszystkich rozmiarów plecaka, tylko te dla których istnieje jakiś podzbiór przedmiotów o sumarycznej wadze równej takiemu rozmiarowi. Możemy zatem sprawdzić wszystkie wagi dla \(2^n\) podzbiorów, co da algorytm o złożoności \(O(n2^n)\).

Podzadanie 3 (programowanie dynamiczne)

Ponieważ jest to zadanie o pakowaniu plecaka, więc aż narzuca się sprawdzić, czy być może mamy jakieś rozwiązanie, w którym użyjemy programowania dynamicznego. Niech w dwuwymiarowej tablicy \(dp\) wartość \(dp[i,j]\) oznacza minimalny rozmiar plecaka dla \(j\)-przedmiotów wybranych procedurą zachłanną spośród sufiksu przedmiotów \(w_i,\ldots,w_n\).

Niech \(R=dp[i+1,j]\) będzie minimalną wielkością plecaka potrzebną, gdybyśmy nie wzięli przedmiotu \(w_i\). Jeśli \(R < w_i\) to dla plecaka rozmiaru \(R\) procedura zachłanna nie weźmie przedmiotu \(w_i\), ale zmieścimy tam \(j\) przedmiotów. Z kolei dla \(R \geq w_i\) potrzebny nam plecak co najmniej rozmiaru \(R\), zatem procedura zachłanna musi wziąć \(w_i\), a pozostałe \(j-1\) przedmiotów musimy dobrać z sufiksu \(w_{i+1},\ldots,w_n\). Zatem: \[dp[i,j] = \left\{\begin{array}{ll}R & \textrm{dla}\ R < w_i, \\ w_i + dp[i+1,j-1] & \textrm{w przeciwnym wypadku}. \end{array}\right.\]

Wartości brzegowe to \(dp[i,0] = 0\) dla dowolnego \(i\) oraz \(dp[n+1,j]=\infty\) dla \(j>0\). Tabelka \(dp\) jest rozmiaru \(O(n^2)\), a każdą jej komórkę obliczamy w czasie stałym. Tak więc złożoność czasowa tego rozwiązania to właśnie \(O(n^2)\).

Pełne rozwiązanie (programowanie dynamiczne)

To programowanie dynamiczne można przyspieszyć, dokładniej analizując, jak wyglądają obliczenia w naszej procedurze rekurencyjnej, a konkretnie, jak wygląda przejście z wiersza \(dp[i + 1,\cdot]\) do wiersza \(dp[i,\cdot]\). Na początek przyda nam się obserwacja, że wszystkie wartości w wierszu są rosnące.

Dowód: załóżmy, że do plecaka rozmiaru \(R\) procedura zachłanna zmieści \(k\) przedmiotów, a ostatnim wybranym przedmiotem było \(w_j\). Jeżeli teraz w tym rozwiązaniu usuniemy \(w_j\), to widać że pozostałe \(k - 1\) przedmiotów zmieści się w plecaku rozmiaru \(R - w_j\), zatem optymalna odpowiedź dla \(k-1\) jest ostro mniejsza niż optymalna odpowiedź dla \(k\).

Czyli wiemy, że wszystkie elementy w wierszach tworzą ciąg rosnący (być może poza elementami końcowymi, które mogą być równe \(\infty\)).

Podzielmy sobie wiersz \(dp[i+1,\cdot]\) na dwie części: \(dp[i+1,1..\ell]\) będzie zawierać wartości mniejsze niż \(w_i\), natomiast \(dp[i+1,\ell+1 .. n]\) będzie zawierać wartości większe równe \(w_i\). Jeżeli popatrzymy sobie na równanie rekurencyjne, to wiersz \(i\) składa się ze skopiowanego fragmentu \(dp[i+1,1..\ell]\) oraz skopiowanego fragmentu \(dp[i+1,\ell..n]\), w którym wartości zwiększamy o \(w_i\).

Czyli jeżeli będziemy mieli teraz strukturę danych, która umożliwi nam przechowywanie ciągu rosnących elementów i wykonywanie następujących operacji:

• znalezienie pierwszego elementu większego równego od jakiegoś \(w_i\),

• wstawienie nowego elementu do ciągu (zachowując posortowanie),

• dodanie wartości \(w_i\) do wszystkich elementów na przedziale,

to wtedy nasz algorytm sprowadzi się do \(n\) faz i w każdej fazie będziemy wykonywali stałą liczbę tych operacji. Taką strukturę danych możemy zaimplementować jako odpowiednio wzbogacone, zrównoważone drzewo poszukiwań binarnych i wtedy każdą z tych operacji będziemy w stanie zrobić w czasie \(O(\log n)\). Czyli całe rozwiązanie będzie miało złożoność \(O(n \log n)\).

Podzadanie 2 (algorytm zachłanny)

Nasze zadanie można nie tylko rozwiązać programowaniem dynamicznym, ale istnieje dla niego również algorytm zachłanny. Przyjrzyjmy się zbiorowi przedmiotów \(Z_k\) wybieranych przez algorytm zachłanny dla minimalnego plecaka rozmiaru \(R_k\) dla jakiejś ustalonej wartości \(k\) oraz zbiorowi przedmiotów \(Z_{k+1}\) dla minimalnego plecaka \(R_{k+1}\) dla wartości \(k+1\). Niech \(w_j\) będzie pierwszym przedmiotem, na którym te zbiory się różnią. Zatem musi być tak, że \(w_j \not\in Z_k\) oraz \(w_j \in Z_{k+1}\). Teraz, jeżeli spojrzymy sobie na resztę rozwiązania \(Z_k\) (dla przedmiotów następujących po \(w_j\)) to wiemy, że tutaj mamy minimalną wielkość plecaka, która pozwala na dołożenie \(\ell\) przedmiotów. A rozwiązanie \(Z_{k+1}\) również musi na tej pozostałej części upchnąć \(\ell\) przedmiotów, więc jeżeli chce to zrobić optymalnie, to musi zastosować dokładnie to samo rozwiązanie, które było w optymalnym rozwiązaniu \(Z_k\). Widać zatem, że te rozwiązania mogą różnić się jedynie na jednym dodanym przedmiocie, czyli \(Z_{k+1} = Z_k \cup \{w_j\}\).

To pozwala nam już napisać pierwsze rozwiązanie zachłanne, które będzie utrzymywało zbiór wybranych przedmiotów i będzie wykonywało \(n\) faz. W \(k\)-tej fazie będziemy przechodzić ze zbioru \(Z_k\) do zbioru \(Z_{k+1}\).

Żeby zrobić takie przejście możemy przeiterować się po wszystkich jeszcze niewybranych przedmiotach \(w_j\) i dla każdego z nich sprawdzić, czy dodanie tego przedmiotu spowoduje, że algorytm zachłanny zadziała tak, że wybierze \(k + 1\) przedmiotów. To znaczy uruchamiamy naszą zwykłą procedurę na plecaku wielkości \(R_k + w_j\) (czyli suma przedmiotów ze zbioru \(Z_k\) plus wielkość przedmiotu, który aktualnie analizujemy). Jeżeli dla takiego rozmiaru plecaka procedura wyboru zwróci nam \(k + 1\) elementów, to możemy zwiększyć nasz zbiór \(Z_k\) o ten element. W przypadku, gdy więcej elementów spełnia tę własność, oczywiście wybierzemy ten, który jest najmniejszy, a w przypadku remisów ten, który znajduje się bardziej po lewo.

Złożoność czasowa takiego rozwiązania to będzie \(O(n^3)\) ponieważ mamy \(n\) faz, a w każdej testujemy \(O(n)\) przedmiotów, wykonując procedurę pakowania działającą w czasie \(O(n)\).

Podzadanie 3 (algorytm zachłanny)

Aby przyspieszyć ten algorytm, spróbujmy szybciej decydować, czy dany element może zostać wybrany przez rozwiązanie zachłanne, jeżeli zwiększymy rozmiar plecaka z \(R_k\) do jakiegoś większego. Rozwiązanie zachłanne dla ustalonego \(k\) i wielkości plecaka \(R_k\) wybierze pewien zestaw przedmiotów. Ustalmy niewybrany przedmiot \(w_i\) i zastanówmy się, kiedy ten przedmiot zacznie być wybierany przez rozwiązanie zachłanne, gdy będziemy zwiększać rozmiar plecaka. Niech \(r_i\) będzie miejscem w plecaku, które pozostało w momencie decydowania o przedmiocie \(w_i\) (czyli jest to suma wag przedmiotów wybranych przez procedurę zachłanną z sufiksu \(w_{i+1},\ldots,w_n\)). Żeby \(w_i\) był wybrany, to miejsce musiało być równe co najmniej \(w_i\), zatem początkowy rozmiar plecaka musiałby być równy \(R_k + s_i\), gdzie \(s_i = w_i - r_i\).

Teraz odpowiedzmy sobie na pytanie, jakie warunki muszą być spełnione, żeby przedmiot \(w_i\) był tym przedmiotem, który rozszerza zachłanne rozwiązanie \(Z_k\) do zachłannego rozwiązania \(Z_{k + 1}\). Po pierwsze musimy zwiększyć rozmiar naszego plecaka do \(R_k + w_i\), ale musimy jeszcze zagwarantować, że żaden niewybrany przedmiot z prefiksu \(w_1,\ldots,w_{i-1}\) nie zostanie wybrany. To znaczy, że wszystkie wartości \(s_1,\ldots,s_{i-1}\) muszą być ostro większe od \(w_i\) (bo to znaczy, że zwiększenie plecaka o \(w_i\) będzie za mało, żeby te wartości mogły być rozważane jako wzięte przez rozwiązanie zachłanne).

Dzięki tym obserwacjom jesteśmy w stanie przyspieszyć procedurę wyboru naszych przedmiotów, dlatego że teraz w każdej fazie zrobimy sobie dwa przejścia po ciągu przedmiotów. Najpierw zrobimy jedno przejście od strony prawej do lewej, żeby wyliczyć wszystkie wartości \(s_i\) (na bieżąco będziemy sobie utrzymywali sumę wybranych przedmiotów w sufiksie i dzięki temu będziemy obliczali kolejno wartości \(s_i\) dla niewybranych przedmiotów). Jak już będziemy mieli wszystkie wartości \(s_i\), to zrobimy przejście od strony lewej do prawej, utrzymując na bieżąco minimum dla prefiksu po wszystkich wartościach \(s_i\) i za każdym razem, kiedy analizujemy jakiś przedmiot \(w_i\), sprawdzając, czy to minimum jest większe od \(w_i\) (jeżeli tak, to przedmiot \(w_i\) jest dobrym kandydatem na wzięcie przez rozwiązanie zachłanne).

Cały algorytm będzie działał w czasie \(O(n^2)\).

Pełne rozwiązanie (algorytm zachłanny)

Okazuje się, że równie prosto można wykonać to rozwiązanie zachłanne od tyłu, a mianowicie przechodząc ze zbioru \(Z_{k + 1}\) do zbioru \(Z_k\). Co ciekawe, w tym momencie warunek jest jeszcze prostszy, bo jeżeli zastanawiamy się, czy dany element \(w_i\) mógł zostać usunięty, żeby stworzyć zbiór \(Z_k\), to warunek jest \(s_i > 0\) (to znaczy, że w rozwiązaniu \(Z_k\) ten element nie byłby wzięty, ponieważ on wymagał ściśle zwiększenia pojemności plecaka z \(R_k\) do jakiejś większej liczby).

Czyli możemy napisać algorytm, który idzie od tyłu i w każdej fazie wybiera jakiś element, dla którego \(s_i > 0\), a jeżeli jest więcej takich elementów, to wybiera ten, który ma największą wagę. A tak naprawdę możemy wybrać element pierwszy z lewej, dlatego, że wszyscy kandydaci, którzy będą mieli \(s_i > 0\), będą w kolejności lewej do prawej uporządkowani malejąco względem wag. Jest to oczywiste, bo gdyby było tak, że \(i < j\) i \(w_i \leq w_j\), to ponieważ \(s_i = w_i -{}\) suma wszystkich wziętych elementów z sufiksu (a w tej sumie również zawiera się \(w_j\)), więc \(s_i < 0\) co daje sprzeczność.

To już nas prowadzi do rozwiązania, w którym będziemy mogli użyć statycznego drzewa przedziałowego, w którym będziemy utrzymywali ciąg wartości \(s_i\). Będziemy potrzebowali operacji znajdowania pierwszego elementu dodatniego oraz operacji, które pozwolą aktualizować ciąg \(s_i\) w momencie, kiedy będziemy wykreślali elementy ze zbioru \(Z_k\) (a to sprowadzi się do aktualizowania wartości w pojedynczym punkcie oraz dodanie wartości \(w_j\) na przedziale). Każda taka operacja będzie działała w czasie \(O(\log n)\).

W każdej z \(n\) faz zrobimy po jednej z tych operacji, wobec tego ostateczna złożoność czasowa tego rozwiązania to będzie \(O(n \log n)\).