Przeskocz do treści

Delta mi!

Loading

Informatyczny kącik olimpijski

Jeszcze dwa zadania do plecaka

Tomasz Idziaszek

o artykule ...

  • Publikacja w Delcie: wrzesień 2015
  • Publikacja elektroniczna: 31-08-2015
  • Wersja do druku [application/pdf]: (51 KB)

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).

Notice: Undefined index: story_alias_uuid in /home/misc/deltami/public_html/ui/inc/site_php_include/index.inc on line 23 Notice: Undefined index: story_alias_uri in /home/misc/deltami/public_html/ui/inc/site_php_include/index.inc on line 24