Tutaj plecak przypomina pojemnik lub torbę. Załóżmy, że daliśmy pewne przedmioty, które mają pewne wagi lub zyski. Musimy tak ułożyć niektóre przedmioty w plecaku, aby łączna wartość przyniosła maksymalny zysk.

Przykładowo waga pojemnika wynosi 20 kg. Musimy tak dobierać przedmioty, aby suma wag przedmiotów była albo mniejsza, albo równa wadze kontenera, a zysk powinien być maksymalny.

Istnieją dwa rodzaje problemów plecakowych:

• Problem z plecakiem 0/1
• Ułamkowy problem plecakowy

Omówimy oba problemy jeden po drugim. Najpierw poznamy problem plecakowy 0/1.

Na czym polega problem plecakowy 0/1?

Problem plecaka 0/1 oznacza, że ​​w plecaku znajdują się wszystkie przedmioty lub nie ma ich w ogóle. Na przykład mamy dwa przedmioty o wadze odpowiednio 2 kg i 3 kg. Jeśli wybierzemy przedmiot 2kg to nie możemy wybrać przedmiotu 1kg z przedmiotu 2kg (przedmiot nie jest podzielny); musimy całkowicie wybrać przedmiot o wadze 2 kg. Jest to problem plecakowy 0/1, w którym albo wybieramy przedmiot w całości, albo wybieramy ten przedmiot. Problem plecakowy 0/1 rozwiązuje się poprzez programowanie dynamiczne.

Na czym polega problem ułamkowego plecaka?

Ułamkowy problem plecakowy oznacza, że ​​możemy podzielić dany przedmiot. Przykładowo, mamy przedmiot o wadze 3 kg, możemy wybrać przedmiot o wadze 2 kg i zostawić przedmiot o wadze 1 kg. Problem ułamkowego plecaka rozwiązuje się metodą zachłannego podejścia.

Przykład problemu plecakowego 0/1.

Rozważmy problem polegający na tym, że wagi i zyski to:

Wagi: {3, 4, 6, 5}

Zyski: {2, 3, 1, 4}

Waga plecaka to 8 kg

Liczba elementów wynosi 4

Powyższy problem można rozwiązać stosując następującą metodę:

X_I= {1, 0, 0, 1}

= {0, 0, 0, 1}

uruchom ponownie mysql ubuntu

= {0, 1, 0, 1}

Powyższe kombinacje są możliwe. 1 oznacza, że ​​przedmiot został całkowicie wybrany, a 0 oznacza, że ​​żaden przedmiot nie został wybrany. Ponieważ są 4 elementy, możliwe kombinacje będą następujące:

2⁴= 16; Więc. Istnieje 16 możliwych kombinacji, które można utworzyć, korzystając z powyższego problemu. Po wykonaniu wszystkich kombinacji musimy wybrać kombinację, która zapewni maksymalny zysk.

Innym podejściem do rozwiązania tego problemu jest podejście do programowania dynamicznego. W podejściu do programowania dynamicznego skomplikowany problem dzieli się na podproblemy, następnie znajdujemy rozwiązanie podproblemu, a rozwiązanie podproblemu zostanie wykorzystane do znalezienia rozwiązania złożonego problemu.

Jak można rozwiązać ten problem, stosując podejście programowania dynamicznego?

Pierwszy,

tworzymy macierz pokazaną poniżej:

W powyższej macierzy kolumny reprezentują wagę, tj. 8. Wiersze reprezentują zyski i wagi przedmiotów. Tutaj nie przyjęliśmy bezpośrednio wagi 8, problem jest podzielony na podproblemy, tj. 0, 1, 2, 3, 4, 5, 6, 7, 8. Rozwiązanie podproblemów zostałoby zapisane w komórki, a odpowiedź na problem zostanie zapisana w ostatniej komórce. Najpierw zapisujemy wagi w kolejności rosnącej, a zyski według ich wag, jak pokazano poniżej:

w_I= {3, 4, 5, 6}

P_I= {2, 3, 4, 1}

Pierwszy wiersz i pierwsza kolumna będą miały wartość 0, ponieważ nie ma elementu dla w=0

Gdy i=1, W=1

w₁= 3; Ponieważ w zestawie mamy tylko jeden przedmiot o wadze 3, a pojemność plecaka wynosi 1. Nie możemy załadować przedmiotu o wadze 3 kg do plecaka o wadze 1 kg, więc dodaj 0 w M[1][1] pokazanym poniżej :

Gdy i = 1, W = 2

w₁= 3; Ponieważ w zestawie mamy tylko jeden przedmiot o wadze 3, a pojemność plecaka wynosi 2. Nie możemy załadować przedmiotu o wadze 3 kg do plecaka o wadze 2 kg, więc dodaj 0 w M[1] [2] pokazanym poniżej :

Gdy i=1, W=3

w₁= 3; Ponieważ w zestawie mamy tylko jeden przedmiot o wadze równej 3, a waga plecaka również wynosi 3; zatem możemy zapełnić plecak przedmiotem o wadze równej 3. Zysk odpowiadający wadze 3, czyli 2, wpisujemy w M[1][3] pokazany poniżej:

Gdy i=1, W = 4

_W1= 3; Ponieważ w zestawie mamy tylko jeden przedmiot o wadze równej 3, a waga plecaka wynosi 4; zatem możemy zapełnić plecak przedmiotem o wadze równej 3. Zysk odpowiadający wadze 3, czyli 2, wpisujemy w M[1][4] pokazany poniżej:

Gdy i=1, W = 5

_W1= 3; Ponieważ w zestawie mamy tylko jeden przedmiot o wadze równej 3, a waga plecaka wynosi 5; zatem możemy zapełnić plecak przedmiotem o wadze równej 3. Zysk odpowiadający wadze 3, czyli 2, wpisujemy w M[1][5] jak poniżej:

Gdy i =1, W=6

_W1= 3; Ponieważ w zestawie mamy tylko jeden przedmiot o wadze równej 3, a waga plecaka wynosi 6; zatem możemy zapełnić plecak przedmiotem o wadze równej 3. Zysk odpowiadający wadze 3, czyli 2, wpisujemy w M[1][6] pokazany poniżej:

Gdy i=1, W = 7

_W1= 3; Ponieważ w zestawie mamy tylko jeden przedmiot o wadze 3, a waga plecaka wynosi 7; zatem możemy zapełnić plecak przedmiotem o wadze równej 3. Zysk odpowiadający wadze 3, czyli 2, wpisujemy w M[1][7] pokazany poniżej:

Gdy i =1, W =8

_W1= 3; Ponieważ w zestawie mamy tylko jeden przedmiot o wadze równej 3, a waga plecaka wynosi 8; zatem możemy zapełnić plecak przedmiotem o wadze równej 3. Zysk odpowiadający wadze 3, czyli 2, wpisujemy w M[1][8] pokazanym poniżej:

Teraz wartość „i” zostanie zwiększona i osiągnie wartość 2.

Gdy i =2, W = 1

Waga odpowiadająca wartości 2 wynosi 4, tj. w₂= 4. Ponieważ w zestawie mamy tylko jeden przedmiot o wadze 4, a waga plecaka wynosi 1. Nie możemy włożyć do plecaka przedmiotu o wadze 4, więc dodajemy 0 w M[2][1 ] pokazano poniżej:

Gdy i =2, W = 2

Waga odpowiadająca wartości 2 wynosi 4, tj. w₂= 4. Ponieważ w zestawie mamy tylko jeden przedmiot o wadze 4, a waga plecaka wynosi 2. Nie możemy włożyć do plecaka przedmiotu o wadze 4, więc dodajemy 0 w M[2][2 ] pokazano poniżej:

Gdy i =2, W = 3

Waga odpowiadająca wartości 2 wynosi 4, tj. w₂= 4. Ponieważ w zestawie mamy dwa przedmioty o wadze 3 i 4, a waga plecaka wynosi 3. Możemy umieścić przedmiot o wadze 3 w plecaku, więc dodajemy 2 w M[2][3] pokazano jak poniżej:

Gdy i =2, W = 4

Waga odpowiadająca wartości 2 wynosi 4, tj. w₂= 4. Ponieważ w zestawie mamy dwa przedmioty o wadze 3 i 4, a waga plecaka wynosi 4. Możemy umieścić w plecaku przedmiot o wadze 4, gdyż zysk odpowiadający wadze 4 jest większy niż przedmiot o wadze 3, więc dodajemy 3 w M[2] [4] jak pokazano poniżej:

Gdy i = 2, W = 5

Waga odpowiadająca wartości 2 wynosi 4, tj. w₂= 4. Ponieważ mamy w zestawie dwa przedmioty o wagach 3 i 4, a waga plecaka wynosi 5. Możemy włożyć do plecaka przedmiot o wadze 4 i zysk odpowiadający wadze wynosi 3, więc dodajemy 3 przy M[2] [5] pokazane poniżej:

Gdy i = 2, W = 6

Waga odpowiadająca wartości 2 wynosi 4, tj. w₂= 4. Ponieważ w zestawie mamy dwa przedmioty o wagach 3 i 4, a waga plecaka wynosi 6. Możemy włożyć do plecaka przedmiot o wadze 4 i zysk odpowiadający wadze wynosi 3, więc dodajemy 3 przy M[2] [6] pokazane poniżej:

Gdy i = 2, W = 7

Waga odpowiadająca wartości 2 wynosi 4, tj. w₂= 4. Ponieważ w zestawie mamy dwa przedmioty o wagach 3 i 4, a waga plecaka wynosi 7. Możemy włożyć do plecaka przedmiot o wadze 4 i 3, a zyski odpowiadające wagom wynoszą 2 i 3; dlatego całkowity zysk wynosi 5, więc dodajemy 5 w M [2] [7] pokazanym poniżej:

Gdy i = 2, W = 8

Waga odpowiadająca wartości 2 wynosi 4, tj. w₂= 4. Ponieważ w zestawie mamy dwa przedmioty o wagach 3 i 4, a waga plecaka wynosi 7. Możemy włożyć do plecaka przedmiot o wadze 4 i 3, a zyski odpowiadające wagom wynoszą 2 i 3; dlatego całkowity zysk wynosi 5, więc dodajemy 5 w M [2] [7] pokazanym poniżej:

Teraz wartość „i” zostanie zwiększona i osiągnie wartość 3.

Gdy i = 3, W = 1

10 procent z 60

Waga odpowiadająca wartości 3 wynosi 5, tj. w₃= 5. Ponieważ w zestawie mamy trzy przedmioty o wagach 3, 4 i 5, a waga plecaka wynosi 1. Nie możemy włożyć żadnego z przedmiotów do plecaka, więc dodajemy 0 w M[3][ 1] pokazano poniżej:

Gdy i = 3, W = 2

Waga odpowiadająca wartości 3 wynosi 5, tj. w₃= 5. Ponieważ w zestawie mamy trzy przedmioty o wadze 3, 4 i 5, a waga plecaka wynosi 1. Nie możemy włożyć żadnego z przedmiotów do plecaka, więc dodajemy 0 w M[3][ 2] pokazano poniżej:

Gdy i = 3, W = 3

Waga odpowiadająca wartości 3 wynosi 5, tj. w₃= 5. Ponieważ w zestawie mamy trzy przedmioty o wadze odpowiednio 3, 4 i 5, a waga plecaka wynosi 3. Przedmiot o wadze 3 można włożyć do plecaka, a zysk odpowiadający temu przedmiotowi wynosi 2, więc dodajemy 2 w M[3] [3] jak pokazano poniżej:

Gdy i = 3, W = 4

Waga odpowiadająca wartości 3 wynosi 5, tj. w₃= 5. Ponieważ w zestawie mamy trzy przedmioty o wadze odpowiednio 3, 4 i 5, a waga plecaka wynosi 4. Możemy zatrzymać przedmiot o wadze 3 lub 4; zysk (3) odpowiadający wadze 4 jest większy niż zysk odpowiadający wadze 3, więc dodajemy 3 w M[3] [4] pokazanym poniżej:

Gdy i = 3, W = 5

Waga odpowiadająca wartości 3 wynosi 5, tj. w₃= 5. Ponieważ w zestawie mamy trzy przedmioty o wadze odpowiednio 3, 4 i 5, a waga plecaka wynosi 5. Możemy zatrzymać przedmiot o wadze 3, 4 lub 5; zysk (3) odpowiadający wadze 4 jest większy niż zysk odpowiadający wadze 3 i 5, więc dodajemy 3 w M[3] [5] pokazanym poniżej:

Gdy i =3, W = 6

Waga odpowiadająca wartości 3 wynosi 5, tj. w₃= 5. Ponieważ w zestawie mamy trzy przedmioty o wadze odpowiednio 3, 4 i 5, a waga plecaka wynosi 6. Możemy zatrzymać przedmiot o wadze 3, 4 lub 5; zysk (3) odpowiadający wadze 4 jest większy niż zysk odpowiadający wadze 3 i 5, więc dodajemy 3 w M[3] [6] pokazanym poniżej:

Gdy i =3, W = 7

Waga odpowiadająca wartości 3 wynosi 5, tj. w₃= 5. Ponieważ w zestawie mamy trzy przedmioty o wadze odpowiednio 3, 4 i 5, a waga plecaka wynosi 7. W tym przypadku możemy zatrzymać oba przedmioty o wadze 3 i 4, czyli sumę zysku będzie równe (2 + 3), tj. 5, więc dodajemy 5 w M[3] [7] pokazanym poniżej:

Gdy i = 3, W = 8

Waga odpowiadająca wartości 3 wynosi 5, tj. w₃= 5. Ponieważ w zbiorze mamy trzy przedmioty o wadze odpowiednio 3, 4 i 5, a waga plecaka wynosi 8. W tym przypadku możemy zatrzymać oba przedmioty o wadze 3 i 4, czyli suma zysk byłby równy (2 + 3), tj. 5, więc dodajemy 5 w M[3] [8] pokazanym poniżej:

Teraz wartość „i” zostanie zwiększona i osiągnie 4.

Gdy i = 4, W = 1

Waga odpowiadająca wartości 4 wynosi 6, tj. w₄= 6. Ponieważ mamy cztery przedmioty w zestawie o wagach odpowiednio 3, 4, 5 i 6, a waga plecaka wynosi 1. Waga wszystkich przedmiotów jest większa niż waga plecaka, więc nie możemy dodaj dowolny przedmiot do plecaka; Dlatego dodajemy 0 w M[4] [1] pokazanym poniżej:

Gdy i = 4, W = 2

Waga odpowiadająca wartości 4 wynosi 6, tj. w₄= 6. Ponieważ mamy cztery przedmioty w zestawie o wagach odpowiednio 3, 4, 5 i 6, a waga plecaka wynosi 2. Waga wszystkich przedmiotów jest większa niż waga plecaka, więc nie możemy dodaj dowolny przedmiot do plecaka; Dlatego dodajemy 0 w M[4] [2] jak pokazano poniżej:

Gdy i = 4, W = 3

Waga odpowiadająca wartości 4 wynosi 6, tj. w₄= 6. Ponieważ mamy cztery przedmioty w zestawie odpowiednio o wagach 3, 4, 5 i 6, a waga plecaka wynosi 3. Przedmiot o wadze 3 można włożyć do plecaka i zysk odpowiadający waga 4 to 2, więc dodamy 2 w M[4] [3] jak pokazano poniżej:

Gdy i = 4, W = 4

Waga odpowiadająca wartości 4 wynosi 6, tj. w₄= 6. Ponieważ mamy cztery przedmioty w zestawie o wagach odpowiednio 3, 4, 5 i 6, a waga plecaka wynosi 4. Przedmiot o wadze 4 można włożyć do plecaka i zysk odpowiadający waga 4 to 3, więc dodamy 3 w M[4] [4] jak pokazano poniżej:

Gdy i = 4, W = 5

Waga odpowiadająca wartości 4 wynosi 6, tj. w₄= 6. Ponieważ mamy cztery przedmioty w zestawie o wagach odpowiednio 3, 4, 5 i 6, a waga plecaka wynosi 5. Przedmiot o wadze 4 można włożyć do plecaka i zysk odpowiadający waga 4 to 3, więc dodamy 3 w M[4] [5] jak pokazano poniżej:

Gdy i = 4, W = 6

Waga odpowiadająca wartości 4 wynosi 6, tj. w₄= 6. Ponieważ mamy cztery przedmioty w zestawie odpowiednio o wagach 3, 4, 5 i 6, a waga plecaka wynosi 6. W tym przypadku możemy włożyć do plecaka przedmioty o wadze 3, 4 , 5 lub 6, ale zysk, tj. 4 odpowiadający wadze 6, jest najwyższy spośród wszystkich pozycji; dlatego dodajemy 4 w M[4] [6] jak pokazano poniżej:

Gdy i = 4, W = 7

Waga odpowiadająca wartości 4 wynosi 6, tj. w₄= 6. Ponieważ mamy cztery przedmioty w zestawie odpowiednio o wagach 3, 4, 5 i 6, a waga plecaka wynosi 7. Tutaj, jeśli dodamy dwa przedmioty o wagach 3 i 4, to otrzymamy maksimum zysk, tj. (2 + 3) równa się 5, więc dodajemy 5 w M[4] [7] pokazanym poniżej:

tostrowanie Java

Gdy i = 4, W = 8

Waga odpowiadająca wartości 4 wynosi 6, tj. w₄= 6. Ponieważ mamy cztery przedmioty w zestawie odpowiednio o wagach 3, 4, 5 i 6, a waga plecaka wynosi 8. Tutaj, jeśli dodamy dwa przedmioty o wagach 3 i 4, to otrzymamy maksimum zysk, tj. (2 + 3) równa się 5, więc dodajemy 5 w M[4] [8] pokazanym poniżej:

Jak możemy zaobserwować w powyższej tabeli, 5 to maksymalny zysk spośród wszystkich wpisów. Wskaźnik wskazuje ostatni wiersz i ostatnią kolumnę zawierającą 5 wartości. Teraz porównamy 5 wartości z poprzednim wierszem; jeśli poprzedni wiersz, tj. i = 3, zawiera tę samą wartość 5, wówczas wskaźnik przesunie się w górę. Ponieważ poprzedni wiersz zawiera wartość 5, wskaźnik zostanie przesunięty w górę, jak pokazano w poniższej tabeli:

Ponownie porównamy wartość 5 z powyższego wiersza, tj. i = 2. Ponieważ powyższy wiersz zawiera wartość 5, więc wskaźnik ponownie zostanie przesunięty w górę, jak pokazano w poniższej tabeli:

Ponownie porównamy wartość 5 z powyższego wiersza, tj. i = 1. Ponieważ powyższy wiersz nie zawiera tej samej wartości, więc rozważymy wiersz i=1, a waga odpowiadająca temu wierszowi wynosi 4. Zatem , wybraliśmy wagę 4 i odrzuciliśmy wagi 5 i 6 pokazane poniżej:

x = { 1, 0, 0}

Zysk odpowiadający wadze wynosi 3. Zatem pozostały zysk wynosi (5 - 3) jest równy 2. Teraz porównamy tę wartość 2 z wierszem i = 2. Ponieważ wiersz (i = 1) zawiera wartość 2 ; dlatego wskaźnik przesunął się w górę, jak pokazano poniżej:

Ponownie porównujemy wartość 2 z powyższym wierszem, tj. i = 1. Ponieważ wiersz i = 0 nie zawiera wartości 2, więc zostanie wybrany wiersz i = 1 i pokazana zostanie waga odpowiadająca i = 1 wynosząca 3 poniżej:

X = {1, 1, 0, 0}

Zysk odpowiadający wadze wynosi 2. Zatem pozostały zysk wynosi 0. Wartość 0 porównujemy z powyższym wierszem. Ponieważ powyższy wiersz zawiera wartość 0, ale zysk odpowiadający temu wierszowi wynosi 0. W tym zadaniu wybierane są dwie wagi, tj. 3 i 4, aby maksymalizować zysk.