Informatyczny kącik olimpijski

Jeszcze dwa zadania do plecaka

W kąciku kontynuujemy przygodę z zadaniami, do których rozwiązania przydaje się znajomość problemu plecakowego. Tym razem w nieco trudniejszej jego wersji, w której każdy przedmiot ma swój rozmiar $|m[i]$ oraz wartość $|w[i]:$ Standardowe pytanie, które możemy wtedy zadać, to np. jaka jest największa sumaryczna wartość przedmiotów, które możemy zapakować do plecaka, nie przekraczając jego udźwigu $M$

Zacznijmy od zadania Meble z Obozu Naukowo-Treningowego im. A. Kreczmara z roku 2013. Chcemy urządzić mieszkanie i w tym celu zakupiliśmy $|n$ rodzajów mebli do samodzielnego montażu. Mamy $ci$ sztuk mebla rodzaju $|i$ ; złożenie pierwszej sztuki tego rodzaju zajmie nam $ti$ minut, a wraz z postępem prac będziemy nabierać wprawy i złożenie kolejnej sztuki zajmie nam o $| di$ minut krócej niż poprzedniej (zakładamy, że $|ti > (ci− 1)di$ ). Chcemy wiedzieć, ile minimalnie czasu potrzebujemy, aby złożyć dowolnych $|M$ mebli.

Naturalne jest tu zastosowanie programowania dynamicznego. Jeśli oznaczymy przez $dp[i, j]$ minimalny czas złożenia $| j$ mebli, gdy rozważamy jedynie rodzaje od 1 do $|i,$ to odpowiedzią będzie $dp[n, M],$ a rekurencją do niej prowadzącą wzór:

dp[i, j] = min0DkDmin ci, j (dp[i − 1, j −k] + Ti,k),

gdzie $k Ti,k = kti− (2)di$ jest czasem montażu $k$ mebli rodzaju $i.$ To rozwiązanie działa w czasie $O(nM2).$

Intuicyjnie rzecz biorąc, jeśli już zaczęliśmy składać meble danego rodzaju, to opłaca się nam wykorzystać zdobyte doświadczenie do maksimum. A formalnie: istnieje optymalne rozwiązanie, w którym mamy co najwyżej jeden rodzaj mebla $i,$ którego złożymy więcej niż 0, ale mniej niż $ci$ sztuk. Istotnie, załóżmy, że mamy co najmniej dwa takie nietrywialne rodzaje $|i1$ i $i2,$ których składamy odpowiednio $ℓ1$ i $|ℓ2$ sztuk. Jeśli ostatni mebel rodzaju $|i 1$ składamy nie dłużej niż ostatni mebel rodzaju $i , 2$ to składając dodatkowe $ℓ = min(ci1− ℓ1,ℓ2)$ sztuk rodzaju $|i1$ zamiast $ℓ$ sztuk rodzaju $|i2,$ nie pogorszymy czasu, a zmniejszymy liczbę nietrywialnych rodzajów mebli.

Rozważmy zatem wszystkie możliwości wyboru nietrywialnego mebla $i.$ Dla ustalonego $|i$ pogrupujmy pozostałe rodzaje mebli $j$ w paczki o rozmiarach $|m[ j] = c j$ i czasach montażu $w[ j] = T j ,cj$ i rozwiążmy dla nich problem plecakowy, w którym pytamy się o najmniejszą wartość przedmiotów całkowicie wypełniających plecak o udźwigu $M.$ Dzięki temu w czasie $|O(nM)$ dostaniemy tablicę $d[0..M], |$ w której $d[j] |$ oznaczać będzie minimalny czas potrzebny na złożenie dokładnie $j$ mebli, jeśli pochodzić będą z pewnej liczby w całości złożonych paczek. Zatem, dokładając do tego $|ℓ$ sztuk mebla $i$ (dla wszystkich wartości $0 < ℓ < ci$ ), zmontujemy $|M$ mebli w czasie $Ti, | ℓ+ d[M$ Złożoność czasowa tego rozwiązania to $O(n2M).$

Zauważmy, że główny koszt algorytmu to rozwiązanie problemu plecakowego dla każdego podzbioru $n | − 1$ przedmiotów. Używając techniki, o której pisaliśmy w zeszłym miesiącu, możemy zmniejszyć złożoność czasową do $O(nM$

Drugie zadanie pochodzi z Wiosennego Turnieju w Programowaniu Zespołowym organizowanego przez Politechnikę Poznańską (a konkretnie z 8. edycji z roku 2004) i ma tytuł (kto by się spodziewał) Pakowanie plecaka. W zadaniu mamy plecak o udźwigu $|M$ i $n |$ przedmiotów, z których każdy ma swój rozmiar $m[i]$ oraz użyteczność $|w[i]$ (przy czym niektóre przedmioty mogą być wyjątkowo nieprzydatne i mieć ujemną użyteczność). Chcemy znaleźć maksymalne upakowanie plecaka (tzn. takie, do którego nie będzie można dołożyć żadnego przedmiotu) o największej sumie użyteczności zabranych przedmiotów (zatem, być może, będziemy zmuszeni zabrać jakiś nieprzydatny przedmiot tylko po to, by dociążyć plecak).

Zauważmy, że jeśli będziemy chcieli zostawić w plecaku puste miejsce o wielkości $|ℓ,$ to wszystkie przedmioty o rozmiarach nie większych niż $|ℓ$ będą musiały znaleźć się w plecaku (inaczej moglibyśmy dołożyć do plecaka co najmniej jeden z nich). Posortujmy zatem przedmioty względem ich rozmiarów i podzielmy na grupę $| j$ przedmiotów "dużych" i $n − j$ przedmiotów "małych", co po ewentualnym przenumerowaniu przedmiotów da nam

w[1]⩾ w[2] ⩾...⩾ w[ j] > ℓ ⩾ w[ j + 1] ⩾ ... ⩾w[n].

Do plecaka na pewno weźmiemy wszystkie "małe" przedmioty o łącznym rozmiarze $m⋆ = PiA jm[i]$ i użyteczności $w⋆ = PiAj w[i].$ Pozostałe przedmioty muszą zająć w plecaku miejsce o wielkości dokładnie $|M$ ale poza tym możemy je wybrać dowolnie. Zatem wystarczy, że rozwiążemy dla nich problem plecakowy maksymalizujący wartość zabranych przedmiotów - odpowiedzią będzie $d[M$

Jeśli przeiterujemy po wartościach $ℓ$ w kolejności malejącej, to każdy przedmiot dokładnie raz zmieni swój status z "małego" na "duży". Możemy więc na bieżąco rozwiązywać problem plecakowy i uaktualniać wartości $|m⋆$ i $|w⋆ .$ Wtedy koszt każdej takiej zmiany wyniesie $O(M),$ a cały algorytm będzie miał złożoność czasową $|O(nlog n+ nM).$