Dyskretny problem plecakowy to kolejne zagadnienie algorytmiczne, które Stasiek zaraz rozłoży na łopatki ;)! Serdecznie zapraszam po "odbiór" zarówno wyjaśnień teoretycznych, jak i..."of course"...kodu źródłowego. Wejdziecie po darmową dawkę wiedzy?

DYSKRETNY PROBLEM PLECAKOWY. W ROLACH GŁÓWNYCH ZŁODZIEJ, PLECAK I PRZEDMIOTY!

Mamy taką zagwozdkę. Idzie sobie złodziej ukraść legalnie czyjeś własności ;). Włamuje się do czyjejś chałupy i zastanawia się które fanty wziąć do plecaka, żeby przyniosły największy zysk w złotówkach, jakby chciał je komuś "opchnąć". Chłopak nie ma bladego pojęcia, że dotyka problemu plecakowego (i Ty też możesz o tym nie wiedzieć ;))! Nauka klasyfikuje ten dylemat jako zagadnienie optymalizacyjne, w którym cała sztuka polega na wyborze takich przedmiotów, żeby suma ich wartości przyniosła największe zyski. Trzeba też pilnować tego, żeby suma ich wag nie przekraczała pojemności plecaka. Widzicie? Mamy funkcję celu (jak to ładnie określają matematycy) i ograniczenie. A dyskretny problem plecakowy (ang. "discrete knapsack problem") nie jest taki łatwy do rozwiązania przez komputer.

DLACZEGO?

Spokojnie, po kolei. Mamy pewne przedmioty charakteryzujące się wartością (trzymamy się waluty PLN) i wagą (dajmy na to w kilogramach). Przedstawmy obserwacje w tabelce, będzie Ci łatwiej:

Dajmy na to, że nasz plecaczek dysponuje pojemnością równą 6 kilo. Teraz proste pytanie: jak ocenić jaki podzbiór przedmiotów zmaksymalizuje zyski, żeby suma wag elementów była nie większa od 6 kilogramów? O ile dla takiego malutkiego zbioru można jeszcze oszacować tak "na oko", to przy dziesięciu elementach już byłby kłopot. Na pewno da się to jakoś ustalić. Tylko jak?

Problem: opracowanie podzbioru przedmiotów o największej wartości sumarycznej nieprzekraczającej pojemności plecaka

Muszę sprawić przykrość. "Wyciągnięcie" konkretnego podzbioru ze zbioru jest możliwe wyłącznie po sprawdzeniu wszystkich kombinacji. Zatem, dostępna jest tylko metoda "brute-force", tak jak przy problemie komiwojażera :(. Jaki płynie z tego istotny wniosek? Że złożoność obliczeniowa będzie wykładnicza (konkretnie to O(2ⁿ) - dowiesz się zaraz dlaczego), problem jest NP-zupełny, a metoda okaże się bezużyteczna dla dużych zbiorów danych! Ustalmy jeszcze wspólnie DLACZEGO tak się dzieje.

ZŁOŻONOŚĆ OBLICZENIOWA JEST TAKA, JAKA JEST

W najgorszym przypadku, taki "oblot" kosztować będzie 2ⁿ czasu! Jeśli Was zastanawia z czego to wynika, przypomnijcie sobie z matematyki takie terminy jak "permutacja bez powtórzeń" i "zbiór potęgowy". Dla trzech przedmiotów, problem plecakowy wymaga przeanalizowania 8 kombinacji, czyli 2³ kombinacji. A to dlatego, że dla każdego przedmiotu musimy się opowiedzieć czy bierzemy go (1), czy też nie (0). Tak naprawdę, to w tym artykule rozpatrujemy dyskretny problem plecakowy, w którym ideą jest uwzględnianie przedmiotu jako całości albo nieuwzględnianie go wcale (są też inne odmiany tego problemu). Jeżeli zatem każdy przedmiot możemy wybrać albo nie i trzeba tak samo zrobić dla wszystkich elementów zbioru, to powstanie nam taki oto zbiór potęgowy (zbiór wszystkich podzbiórów zbioru przedmiotów):

P(I) = {{0,0,0},{0,0,1},{0,1,0},{1,0,0},{1,0,1},{1,1,0},{0,1,1},{1,1,1}}

Jak przedstawię to na tabelce, powinno być lepiej widoczne do czego zmierzam:

"See"? Osiem kombinacji, w których trzeba przetrząsnąć wszystkie dostępne opcje. "Binarna" decyzja (bierzemy przedmiot albo nie), n przedmiotów do analizy, no i pasuje! Notacja dużego O jest nie inna jak O(2ⁿ). Uuu, fatalnie!

APROKSYMACJO, JESTEŚ TU?

Trzeba szukać szczęścia gdzie indziej. Jak przy problemie komiwojażera, tak i tutaj jest wiele sposobów i niestandardowych implementacji dostępnych w Internecie przynoszących rozwiązanie heurystyczne. A ja poczęstuję Was moją, wykorzystującą programowanie dynamiczne, o którym szepnę parę słów więcej w osobnym artykule. Wprowadzę Was w metodykę działania ;).

PROBLEM STAJE SIĘ ZA DUŻY? PODZIEL GO!

Programowanie dynamiczne charakteryzuje się dzieleniem zadanego problemu na mniejsze "podproblemy" (to nie działa tak samo, jak technika "dziel i rządź"!). Rozkłada się go na siatce (tablicy dwuwymiarowej) i na obu osiach odpowiednio definiuje się ograniczenia. To ma duży plus, zwłaszcza w sytuacji przed którą stoimy - przechowywanie dotychczasowych wyników swojej pracy redukuje złożoność obliczeniową, bo program nie traci czasu na ponowne kalkulacje tego samego, tylko sobie "sięga" do tabelki i już wszystko wie.

SIATKA "PODPROBLEMÓW"?

Czego to ludzie nie wymyślą, nie? Wiersze będą reprezentować podzbiory przedmiotów, w których zawierać się będą tylko te elementy, których indeks w kolejności nie przekracza numeru wiersza. Czyli dla pierwszego wiersza, będzie przypisany podzbiór jednoelementowy, w którym znajdzie się tylko laptop. Kolumny (to będzie głupio brzmieć, ale taka prawda) określają pojemności "podplecaków" i każda kolumna będzie "podnosić" tę pojemność o jedną jednostkę do góry, aż do rozmiaru plecaka "pełnego".

Wiem, że na pierwszy rzut oka to brzmi idiotycznie, jednak jak popatrzycie na metodykę, od razu wszystko stanie w blasku prawidłowego rozumienia. Trzeba jeszcze wspomnieć o osobnych komórkach, które będą oznaczały wartość sumaryczną przedmiotów dla danego podzbioru przy posiadaniu danego "podplecaka". Interpretować to jak rozwiązanie częściowe (lokalnie optymalne rozwiązanie, pamiętacie?), bo każda taka wartość to będzie krok bliżej do otrzymania globalnie optymalnego rozwiązania, które będzie tą ostatnią wartością (ostatni rząd i kolumna). No i należy też zwrócić uwagę, że jest to algorytm aproksymacyjny, zatem liczcie się z pewnym dopuszczalnym marginesem błędu ze strony heurystycznego podejścia do sprawy.

JAK TO DZIAŁA?

Dyskretny problem plecakowy "rozłożony" na czynniki pierwsze zgodnie z zasadą programowania dynamicznego prezentować się będzie o tak:

Na starcie każdej komórce przypisywana jest wartość zero. Rozpoczynamy zawsze od pierwszej komórki w lewym górnym rogu (dla "podplecaka" równego 1 i dla mocy podzbioru przedmiotów równej 1, czyli liczby elementów w zbiorze niekumaci ;)). Potem powstaje proste pytanie: czy przedmiot jako jedyny w podzbiorze zmieści się w "podplecaku" o pojemności jednego kilograma? Sięgamy do tabelki u góry i stwierdzamy że NIE, więc pozostaje zostawić wartość zero bez zmian.

Program przechodzi do kolejnej kolumny i zadaje to samo pytanie, ale już z "podplecakiem" równym 2. Dalej laptop się nie zmieści, więc czyni się to samo co poprzednio. Inna sprawa jak do "podplecaka" o 3 jednostkach już MOŻNA zmieścić przedmiot! Wtedy co się robi? Przypisuje się wartość jedynego przedmiotu, który tym razem można uwzględnić i komórka zawiera wartość równą 3000. Jaki płynie z tego wniosek? Że w każdym większym "podplecaku" TAKŻE zmieści się ten sam przedmiot! Przepisujemy te trzy tysiące w całym wierszu jak leci!

Oto dotychczasowe wyniki:

Dyskretny problem plecakowy został rozwiązany częściowo. Na chwilę obecną możemy na razie stwierdzić tyle, że laptop da się włożyć do plecaków o pojemności większej bądź równej 3 jednostki. Co się będzie działo dalej?

Algorytm przechodzi do następnego wiersza, a tam badamy teraz podzbiór DWUELEMENTOWY i odpowiadamy na pytanie czy do wskazanych "podplecaków" zmieści się laptop i smartfon! Badamy "podplecak" o pojemności jednej jednostki. Widzimy, że choć laptop nie wejdzie, to smartfon już damy radę włożyć! Odnotowujemy to we właściwej komórce pisząc wartość smartfona (2000) i od razu możemy zrobić to samo dla "podplecaka" o pojemności 2, bo i tutaj laptop nie ma prawa wejść. W kolejnej kolumnie pojawia się problem, który w tej sytuacji jest trywialny do rozwikłania, bowiem może zmieścić się i jeden, i drugi przedmiot (ale nie oba naraz). Wybieramy ten, który daje największą wartość w PLNach i okazuje się nim laptop. Przepisujemy wartość bez zmian. Dla "podplecaka" o pojemności równej 4 jednostki, mamy rewelacyjną sytuację, bo zmieszczą się wszystkie przedmioty w rozpatrywanym podzbiorze. Czyli komórka będzie sumą obu przedmiotów (laptop + smartfon = 5000). Nie mamy więcej przedmiotów do zbadania, więc w całej reszcie kolumn PRZEPISUJEMY. Algorytm rozprawił się z drugim wierszem, a tak wyglądają wyniki:

Mamy ostatni wiersz do rozpracowania i dyskretny problem plecakowy przestanie być problemem!

Algorytm przechodzi do ostatniego wiersza i teraz mamy dostępny komplet przedmiotów (już nie fragment)! Badamy zbiór trzyelementowy i stoimy na "podplecaku" o pojemności równej jeden. To samo pytanie: czy którykolwiek z tych trzech przedmiotów się zmieści? Tylko smartfon. Zatem nic nie ulega zmianie z poprzedniego wiersza, więc prze-pi-su-je-my. Widać gołym okiem, że jeśli konsola do gier ma wagę 5, to nie będzie żadnych innych alternatyw dla "podplecaków" o pojemności mniejszej bądź równej 4. Wiecie co macie robić. Dla kolejnego "podplecaka" algorytm już zadaje sobie pytanie: czy wartość konsoli do gier przewyższy sumę wartości laptopa i smartfona? Nie, bo 4000 jest mniejsze od 5000! Przepisujemy wartość z poprzedniego rzędu. A teraz ba-dum, ba-dum, ba-dum. Ostatnia komórka w tabeli. Pytanie: czy wartość konsoli do gier może wpłynąć na wynik? TAK! Suma wartości konsoli do gier i smartfona przewyższy sumę wartości laptopa i smartfona, zatem tamten podzbiór jest porzucany i na jego miejsce wkracza ten, do komórki wpisujemy 6000 i tak oto mamy rozwiązanie globalnie optymalne. Wynikiem ostatecznym jest w tym przypadku komórka w ostatnim rzędzie i kolumnie. Oto ostateczna postać tabeli:

Ufff...nareszcie meta, a to tylko trzy przedmioty ;). To nam dało 6x3 kombinacji, czyli iloczyn pojemności plecaka i mocy zbioru przedmiotów. Taka jest złożoność obliczeniowa tego podejścia!

O(|I|*C), gdzie I = zbiór przedmiotów, C = pojemność plecaka

Lepiej? No pewno!

KOD ŹRÓDŁOWY

Tak wygląda teoria moi drodzy, a teraz podsumujemy to sobie kodem praktycznym w Javie przedstawiającym dyskretny problem plecakowy rozwiązany przy pomocy programowania dynamicznego. Zachęcam do eksperymentowania z danymi:

KLASA "MAIN"

public class Main {
	public static void main(String[] args) {
		int knapsackCapacity = 6;
		Item[] items = new Item[]{
			new Item("Laptop", 3000, 3),
			new Item("Smartfon", 2000, 1),
			new Item("Konsola do gier", 4000, 5)
		};

		new DiscreteKnapsackProblem(knapsackCapacity, items);
	}
}

REKORD "ITEM"

public record Item(String name, int value, int weight) {
	@Override
	public String toString() {
		return "PRZEDMIOT: " + name + " o wartości: " + value + " i wadze: " + weight;
	}
}

KLASA "DISCRETEKNAPSACKPROBLEM"

public class DiscreteKnapsackProblem {
	public DiscreteKnapsackProblem(int capacity, Item[] items) {
		System.out.println("Największa wartość sumaryczna: " + highestValue(capacity, items));
	}

	private int highestValue(int capacity, Item[] items) {
		int amountOfItems = items.length;
		int[][] grid = new int[amountOfItems + 1][capacity + 1];

		for (int y = 0; y <= amountOfItems; ++y) {
			for (int x = 0; x <= capacity; ++x) {
				if(x == 0 || y == 0) {
					grid[y][x] = 0;
				} else {
					Item currentItem = items[y - 1];
					int itemWeight = currentItem.weight();
					int previousRow = grid[y - 1][x];
					boolean itemFitsInKnapsack = itemWeight <= x;
					int valueWithAddedItem = itemFitsInKnapsack ? currentItem.value() + grid[y - 1][x - itemWeight] : 0;

					grid[y][x] = Math.max(valueWithAddedItem, previousRow);
				}
			}
		}

		return grid[amountOfItems][capacity];
	}
}

A teraz wyjaśnienia od strony kodowej. W klasie "Main" (wyjątkowo) inicjujemy sobie dane wejściowe, które będą brane pod uwagę przez algorytm aproksymacyjny rozwiązujący dyskretny problem plecakowy. Jedna liczba całkowita i jedna tablica typu "przedmiot" (więcej już za momencik) w zupełności wystarczą. "int" określa pojemność naszego plecaka, a tablica stanowi zbiór przedmiotów dostępnych do zabrania. Na samym końcu tworzymy instancję klasy rozwiązującej problem, a z racji tego że instrukcje są zawarte w jej konstruktorze, jest sama w sobie "zapalnikiem".

Rekord "Item" przeznaczony jest dla instancji pojedynczego przedmiotu jaki będzie brał udział w eksperymencie. Posiada trzy dane składowe: łańcuch znaków dla nazwy, liczbę całkowitą określającą jego wartość oraz drugą liczbę całkowitą określającą tym razem wagę. Więcej do szczęścia nie potrzeba! Oprócz tego wstawiłem przesłonięcie metody "toString", żeby podczas wywoływania metody wypisującej dane obiektu na ekranie terminala ("System.out.println"), program wyrzucił informacje o tym przedmiocie, zamiast nic niemówiącego ciągu liter i cyfr.

Została najważniejsza klasa do wyjaśnienia. Skonfigurowałem odpowiednio konstruktor, żeby przyjmował parametr formalny w postaci pojemności plecaka oraz tablicy przedmiotów. W środku niego zostawiłem instrukcję, która ma zwrócić na wyjściu informację o najwyższej wartości sumarycznej (według aproksymacji). Dyskretny problem plecakowy jest rozwiązywany w metodzie "highestValue" i tam dzieje się najwięcej!

W pierwszym punkcie tworzy ona dwie zmienne lokalne dla przechowania liczby przedmiotów oraz tablicy dwuwymiarowej dla tej naszej siatki. Ze względu na notację indeksową (w której elementy liczy się od zera), o wiele lepiej jest przesunąć się ze wszystkimi wartościami o jeden rząd i kolumnę do przodu, stąd mamy "plus jeden" do rzędów i kolumn. Otwieramy pętlę "for", która będzie odpowiadać za przesuwanie się po wierszach (oś Y), a w niej otwieramy drugą pętlę "for" iterującą tym razem po kolumnach (oś X). W zagnieżdżeniu znajduje się instrukcja warunkowa sprawdzająca wartości zmiennych iteracyjnych. Ma to na celu zabezpieczyć program przed próbą operowania na indeksach wykraczających poza rozmiar tabelki, bo później są przeprowadzane przesunięcia. Komórka ma mieć wartość zero, jeśli algorytm "porusza się" po "zerowym" podzbiorze przedmiotów lub po "zerowym podplecaku" (pierwszy rząd lub kolumna wg implementacji w kodzie). Kiedy tak nie jest, wykonywane jest to, co najważniejsze.

Na sam początek definiowana jest następna seria zmiennych w postaci aktualnie rozpatrywanego przedmiotu ("currentItem"), jego wagi ("itemWeight"), wartości w poprzednim rzędzie ("previousRow", zaraz się dowiesz dlaczego to jest potrzebne), wartości boolowskiej czy dany przedmiot zmieści się w naszym "podplecaku" ("itemFitsInKnapsack") oraz wartości sumarycznej przedmiotów, gdyby przedmiot został uwzględniony ("valueWithAddedItem"). To chyba najbardziej skomplikowana instrukcja do zrozumienia. Operator trójargumentowy jaki tu został użyty definiuje dwa przypadki w zależności od tego, czy przedmiot może być włożony do plecaka, czy nie:

1. Jeżeli przedmiot da się wrzucić do plecaczka, liczba całkowita przyjmuje sumę jego wartości z wartością zapisaną w komórce w poprzednim wierszu o odpowiednim przesunięciu w kolumnach. Przesunięcie to występuje w jednostkach wagi przedmiotu i oznacza "powrót" do momentu sprzed wybrania przedmiotu w poprzednim rzędzie i "zamianę" na przedmiot o większej wartości, który zmieści się w aktualnym (większym) "podplecaku". Wybaczcie zagmatwanie, tylko jaśniej już nie mogę tego wytłumaczyć.
2. Jeżeli przedmiot nie może zostać uwzględniony, to przypisywana jest wartość zero.

Na samym końcu bloku instrukcji warunkowej w części "else", mamy przypisanie wartości danej komórce w osiach X i Y, a jest za nie odpowiedzialna metoda "Math.max" zwracająca największą wartość całkowitą spośród podanych. Dlatego w punkcie 2 mamy przypisywanie do zera, bo w razie nieuwzględnienia przedmiotu spowoduje to przepisanie wartości komórki z poprzedniego rzędu, co zostanie uznane za najwyższy możliwy wynik. Kiedy algorytm rozprawi się ze wszystkimi komórkami, pozostaje mu tylko zwrócić globalnie optymalne rozwiązanie, które znajduje się w ostatniej kratce tabeli, czyli mamy "return" i dyskretny problem plecakowy staje się przeszłością!

To wszystkie informacje jakie chciałem Wam przekazać na ten temat. Jest kilka ciekawych sposobów na wykorzystanie tego w praktyce. Na przykład możecie się spytać algorytmu za co się wziąć w pierwszej kolejności z zadań do wykonania i za pojemność plecaka podstawić liczbę dni, a "przedmiotami" będą zadania z określonym priorytetem (jako "wartość") oraz ile dni zajmie jego wykonanie (jako "waga"). No, pomyślcie o tym!

PODOBNE ARTYKUŁY

• Zachłanność w algorytmice. Jak działa algorytm zachłanny?
• Algorytm Dijkstry. Teoria i kod źródłowy
• Przeszukiwanie wszerz. Teoria i kod źródłowy