problem z plecakiem
problem z plecakiem okazał się jednocześnie trudny i interesujący. Jestem pewien, że jeśli odwiedzasz tę stronę, znasz już instrukcję problemu, ale tylko ze względu na zakończenie:
Problem:
biorąc pod uwagę plecak o maksymalnej pojemności w I N elementów, każdy z własną wartością i wagą, Wrzuć przedmioty wewnątrz plecaka tak, że ostateczna zawartość ma maksymalną wartość. Rany !!,
oto ogólny sposób wyjaśnienia problemu – weź pod uwagę, że złodziej wchodzi do domu, aby okraść i nosi plecak. W domu jest stała liczba przedmiotów-każdy z własną wagą i wartością-Biżuteria, o mniejszej wadze i najwyższej wartości vs tabele, o mniejszej wartości, ale dużo ciężka. 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 opuszcza
przykład :
Knapsack Max weight : W = 10 (units)Total items : N = 4Values of items : v = {10, 40, 30, 50}Weight of items : w = {5, 4, 6, 3}
pobieżne spojrzenie na przykładowe dane mówi nam, że maksymalna wartość, którą możemy pomieścić z limitem maksymalnej wagi 10, wynosi 50 + 40 = 90 z wagą 7.
podejście:
sposób, w jaki jest to optymalnie rozwiązywane, polega na wykorzystaniu programowania dynamicznego – rozwiązywanie dla mniejszych zestawów problemów plecakowych, a następnie rozszerzanie ich dla większego problemu.,
zbudujmy tablicę wagi elementu X o nazwie V (tablica wartości):
V = 4 rows * 10 columnskażda z wartości w tej macierzy reprezentuje mniejszy problem plecaka.
przypadek podstawowy 1 : weźmy przypadek 0.kolumny. Oznacza to tylko, że plecak ma 0 pojemności. Co możesz w nich trzymać? Nic. Tak więc, wypełnimy je wszystkie z 0s.
przypadek podstawowy 2: weźmy przypadek rzędu 0. Oznacza to tylko, że w domu nie ma żadnych przedmiotów. Co trzymasz w plecaku, jeśli nie ma przedmiotów. Znowu nic !!! Wszystkie zera.,
rozwiązanie:
1) teraz zacznijmy wypełniać wiersz tablicy. Co oznaczają wiersze 1 i Kolumna 1? Że biorąc pod uwagę pierwszy element (wiersz), można go pomieścić w plecaku o pojemności 1 (kolumna). Nie. Waga pierwszej pozycji to 5. Więc, wypełnimy 0. W rzeczywistości nie bylibyśmy w stanie wypełnić niczego, dopóki nie osiągniemy kolumny 5(Waga 5).
2) gdy osiągniemy kolumnę 5 (która reprezentuje wagę 5) w pierwszym rzędzie, oznacza to, że możemy pomieścić pozycję 1., Wypełnimy tam 10 (pamiętaj, że jest to tablica wartości):
3) przechodząc dalej, dla wagi 6 (kolumna 6), możemy pomieścić cokolwiek innego z pozostałą wagą 1 (Waga – Waga tego elementu => 6 – 5). Hej, pamiętaj, jesteśmy na pierwszym miejscu. Tak więc jest to trochę intuicyjne, że reszta wiersza będzie po prostu taka sama wartość, ponieważ nie jesteśmy w stanie dodać żadnego innego elementu dla tej dodatkowej wagi, którą mamy.,
4) tak więc następna interesująca rzecz dzieje się, gdy dotrzemy do kolumny 4 w trzecim rzędzie. Aktualna Masa eksploatacyjna wynosi 4.
powinniśmy sprawdzić następujące przypadki.
1) Czy możemy pomieścić punkt 2 – Tak, możemy. Waga punktu 2 wynosi 4.
2) czy wartość aktualnej wagi jest wyższa bez pozycji 2? – Sprawdź poprzedni wiersz dla tej samej wagi. Nie. poprzedni wiersz * ma w sobie 0, ponieważ nie byliśmy w stanie pomieścić pozycji 1 w wadze 4.
3) Czy możemy pomieścić dwa przedmioty o tej samej wadze, abyśmy mogli zmaksymalizować wartość? – Nie., Pozostała waga po odjęciu wagi Item2 wynosi 0.
Dlaczego poprzedni wiersz?
Po prostu dlatego, że poprzedni wiersz przy wadze 4 sam jest mniejszym rozwiązaniem knapsack, który daje maksymalną wartość, która może być zgromadzona dla tej wagi do tego punktu (przechodząc przez przedmioty).,
1) wartość bieżącej pozycji = 40
2) Waga bieżącej pozycji = 4
3) waga, która pozostała = 4 – 4 = 0
4) Sprawdź wiersz powyżej (pozycja powyżej w przypadku pozycji 1 lub skumulowana maksymalna wartość w przypadku reszty wierszy). Dla pozostałej wagi 0, czy jesteśmy w stanie pomieścić pozycję 1? Mówiąc najprościej, czy w powyższym wierszu jest jakaś wartość dla danej wagi?,
obliczenie wygląda tak:
1) Weź maksymalną wartość dla tej samej wagi bez tego elementu:
previous row, same weight = 0=> V2) Weź wartość bieżącego elementu + wartość, którą możemy pomieścić z pozostałą wagą:
Max wśród tych dwóch wynosi 40 (0 i 40).
3) następne i najważniejsze zdarzenie ma miejsce w kolumnie 9 i wierszu 2. Czyli mamy wagę 9 i mamy dwie rzeczy. Patrząc na przykładowe dane możemy pomieścić dwie pierwsze pozycje., Tutaj rozważamy kilka rzeczy:
- wartość bieżącej pozycji = 40
- waga bieżącej pozycji = 4
- waga, która pozostała = 9 – 4 = 5
- Sprawdź wiersz powyżej. Przy pozostałej wadze 5, jesteśmy w stanie pomieścić punkt 1.
tak więc obliczenia są następujące :
1) Weź maksymalną wartość dla tej samej wagi bez tego elementu:
previous row, same weight = 102) Weź wartość bieżącego elementu + wartość, którą możemy zgromadzić z pozostałą wagą:
Value of current item (40)+ value in previous row with weight 5 (total weight until now (9) - weight of the current item (4))= 1010 vs 50 = 50.,
pod koniec rozwiązywania tych wszystkich mniejszych problemów, wystarczy zwrócić wartość w V – Item 4 przy wadze 10:
złożoność
Analiza złożoności rozwiązania jest dość prosta. Po prostu mamy pętlę dla W W pętli N = > O (NW)
implementacja:
nadchodzi obowiązkowy kod implementacji w Javie: