aktualizacja: przeczytaj o optymalizacji złożoności przestrzennej rozwiązania do programowania dynamicznego w moim kolejnym artykule tutaj.,
problem plecaka jest naprawdę interesującym problemem w kombinatoryce — aby zacytować Wikipedię,
„biorąc pod uwagę zbiór elementów, każdy z wagą i wartością, określ liczbę każdego elementu do włączenia do zbioru, tak aby całkowita waga była mniejsza lub równa danemu limitowi, a całkowita wartość była jak największa.”
z Wikipedii wynika, że istnieje kilka odmian problemu plecaka: 0-1 plecak, Ograniczony plecak i nieograniczony plecak., Dzisiaj skupimy się na najczęstszej (i najprostszej) odmianie: problem plecaka 0-1.
nieco ciekawszym i bardziej relatywnym sformułowaniem problemu plecaka 0-1 jest:
weź pod uwagę, że złodziej wchodzi do domu, aby okraść i nosi plecak. Istnieje stała liczba przedmiotów w domu-każdy z własną wagą i wartością-Biżuteria, z mniejszą wagą i najwyższą wartością vs tabele, z mniejszą wartością, ale dużo ciężkie. Aby dodać paliwo do ognia, złodziej ma Stary plecak, który ma ograniczoną pojemność., Oczywiście, nie może podzielić stołu na pół lub biżuterię na 3/4. Albo go bierze, albo zostawia. Źródło
Niestety, miałem pewne trudności ze zrozumieniem niektórych części artykułu Hackerearth, dlatego postanowiłem napisać własny artykuł. Ten artykuł będzie w dużej mierze oparty na artykule Hackerearth, a fragmenty kodu są napisane w Javie. Będę zajmował się dodatkowymi wyjaśnieniami i opracowaniami tam, gdzie uważam, że są one konieczne.
rozwiążemy ten problem przy pomocy programowania dynamicznego., Programowanie dynamiczne wymaga optymalnej podbudowy i nakładających się pod-problemów, z których oba są obecne w problemie 0-1 knapsack, jak zobaczymy.
to dobrze, jeśli nie rozumiesz, czym są „optymalna podbudowa” i „nakładające się podbudowy” (to artykuł na inny dzień). Zasadniczo oznacza to po prostu szczególny smak problemów, które pozwalają nam ponownie wykorzystać poprzednie rozwiązania mniejszych problemów w celu obliczenia rozwiązania obecnego problemu. Zaraz zobaczysz, co mam na myśli.,
szczegóły problemu
ponieważ jest to problem z plecakiem 0-1, możemy albo dołączyć element do naszego plecaka, albo go wykluczyć, ale nie dołączyć jego ułamka, albo dołączyć go wiele razy.
rozwiązanie
najpierw tworzymy 2-wymiarową tablicę (tj. tabelę)n + 1 wiersze iw + 1 kolumny.
numer wiersza i przedstawia zbiór wszystkich pozycji z wierszy 1— i. na przykład wartości w wierszu 3 zakładają, że mamy tylko pozycje 1, 2 i 3.
numer kolumny j reprezentuje nośność naszego plecaka., Dlatego wartości w kolumnie 5 zakładają na przykład, że nasz plecak może pomieścić 5 jednostek wagi.
składając wszystko razem, wpis w wierszu i, kolumnie j reprezentuje maksymalną wartość, jaką można uzyskać z pozycji 1, 2, 3 … i, w plecaku, który może pomieścić jednostki wagi j.
wywołajmy naszą tabelęmat dla macierzy. Dlatego int mat = new int.
Krok 2:
możemy natychmiast rozpocząć wypełnianie niektórych wpisów w naszej tabeli: przypadków bazowych, dla których rozwiązanie jest trywialne., Na przykład w wierszu 0, gdy nie mamy elementów do wybrania, maksymalna wartość, która może być przechowywana w dowolnym plecaku musi wynosić 0. Podobnie w kolumnie 0, dla plecaka, który może pomieścić 0 jednostek masy, maksymalna wartość, która może być w nim przechowywana, wynosi 0. (Zakładamy, że nie ma masowych, wartościowych przedmiotów.)
możemy to zrobić za pomocą 2 dla pętli:
Krok 3 (sedno problemu):
teraz chcemy zacząć wypełniać naszą tabelę., Podobnie jak w przypadku wszystkich dynamicznych rozwiązań programistycznych, na każdym etapie będziemy wykorzystywać nasze rozwiązania do poprzednich pod-problemów.
najpierw opiszę logikę, zanim pokażę konkretny przykład.
relacja między wartością w wierszu i, kolumnie j a wartościami do poprzednich pod-problemów jest następująca:
Przypomnijmy, że w wierszu i i kolumnie j rozwiązujemy pod-problem składający się z pozycji 1, 2, 3 … i z plecakiem o pojemności J. W tym momencie są 2 opcje: możemy albo dołączyć i, albo nie., Dlatego musimy porównać maksymalną wartość, jaką możemy uzyskać z item I i bez niego.
maksymalną wartość, jaką możemy uzyskać bez item i można znaleźć w wierszu i-1, kolumnie j. ta część jest łatwa. Rozumowanie jest proste: niezależnie od maksymalnej wartości, jaką możemy uzyskać z pozycjami 1, 2, 3 … i musi być oczywiście tą samą maksymalną wartością, jaką możemy uzyskać z pozycjami 1, 2, 3 … i – 1, Jeśli zdecydujemy się nie uwzględniać pozycji i.
aby obliczyć maksymalną wartość, jaką możemy uzyskać z pozycją i, najpierw musimy porównać wagę pozycji i z pojemnością wagową plecaka., Oczywiście, jeśli przedmiot i waży więcej niż to, co plecak może pomieścić, nie możemy go uwzględnić, więc nie ma sensu wykonywać obliczeń. W takim przypadku rozwiązaniem tego problemu jest po prostu maksymalna wartość, jaką możemy uzyskać bez elementu i (tj. wartość w wierszu powyżej, w tej samej kolumnie).
Załóżmy jednak, że przedmiot waży mniej niż pojemność plecaka. Mamy zatem możliwość włączenia go, jeśli potencjalnie zwiększy maksymalną możliwą wartość., Maksymalna osiągalna wartość przez włączenie elementu i wynosi zatem = wartość samego elementu i + maksymalna wartość, którą można uzyskać z pozostałą pojemnością plecaka. Oczywiście chcemy w pełni wykorzystać pojemność naszego plecaka i nie pozwolić, aby pozostała pojemność poszła na marne.
dlatego w wierszu i i kolumnie j (która reprezentuje maksymalną wartość, którą możemy tam uzyskać) wybieramy albo maksymalną wartość, którą możemy uzyskać bez elementu i, albo maksymalną wartość, którą możemy uzyskać z elementu i, w zależności od tego, która z tych wartości jest większa.
oto konkretny przykład tego, co mam na myśli.,
w wierszu 3 (pozycja 2) i kolumnie 5 (pojemność plecaka 4) możemy wybrać pozycję 2 (która waży 4 jednostki) lub nie. Jeśli zdecydujemy się jej nie włączać, maksymalna wartość jaką możemy uzyskać jest taka sama jak wtedy, gdy mamy tylko pozycję 1 do wyboru (która znajduje się w powyższym wierszu, tj. 0)., Jeśli chcemy uwzględnić pozycję 2, maksymalną wartością, jaką możemy uzyskać z pozycją 2, jest wartość pozycji 2 (40) + maksymalną wartość, jaką możemy uzyskać z pozostałą pojemnością (która wynosi 0, ponieważ plecak jest już całkowicie pełny).
w wierszu 3 (Pozycja 2) i kolumnie 10 (pojemność plecaka 9) ponownie możemy wybrać pozycję 2 lub nie. Jeśli zdecydujemy się nie, maksymalna wartość jaką możemy uzyskać jest taka sama jak w wierszu powyżej w tej samej kolumnie, tj. 10 (włączając tylko pozycję 1, która ma wartość 10). Jeśli uwzględnimy pozycję 2, mamy pozostałą pojemność plecaka 9-4 = 5., Możemy dowiedzieć się maksymalnej wartości, która może być uzyskana z pojemności 5 patrząc na wiersz powyżej, w kolumnie 5. Tak więc maksymalna wartość, jaką możemy uzyskać przez włączenie pozycji 2, wynosi 40 (wartość pozycji 2) + 10 = 50.
wybieramy większy z 50 vs 10, a więc maksymalna wartość, jaką możemy uzyskać z pozycji 1 i 2, o pojemności plecaka 9, wynosi 50.,
algorytm można wyrazić w Javie w następujący sposób:
Krok 4 (ostateczne rozwiązanie):
Po wypełnieniu tabeli ostateczne rozwiązanie można znaleźć w ostatnim wierszu ostatniej kolumny.reprezentuje maksymalną wartość dostępną dla wszystkich przedmiotów i pełną pojemność plecaka.
return mat;
Kod roboczy:
Uwaga: tutaj wydrukowałem ostateczną odpowiedź zamiast zwracać ją, ponieważ wszystko jest umieszczone w publicznym static void main.,
Thanks for reading!