Przedmioty i ich wagi:

Maksymalna pojemność plecaka wynosi 5.

W algorytmie dynamicznym na początku tworzymy tablicę. Wiersze tablicy reprezentują pakowane przedmioty, a kolumny – obciążenie plecaka w przedziale od 1 do 5.

Początkowo tablica P (pakowania plecaka), której będziemy używać w algorytmie dynamicznym, wygląda następująco:

Wypełnimy ją

Przyjrzyjmy się kolejnym przedmiotom.

Pierwszy wiersz dotyczy aparatu, co oznacza, że próbujemy włożyć go do plecaka. Waga przedmiotu o indeksie 0 wynosi 1. Jego wartość również wynosi 1.

Zaczniemy od pojemności równej 1. Do plecaka o tej pojemności możemy spakować aparat. Zapisujemy zatem jego wartość (1) w pierwszej komórce tablicy.

Przechodzimy do pojemności równej 2. Ponownie możemy spakować aparat. Po jego spakowaniu pojemność plecaka wynosi 1. Sprawdzamy zatem (cofając się w tym samym wierszu do kolumny, która dotyczy pojemności plecaka równej 1), jaka jest maksymalna wartość przedmiotów spakowanych do plecaka o tej pojemności. To 1, zatem dodajemy ją do wartości spakowanego aparatu (również wynosi 1). W komórce wpisujemy wartość 2.

Przechodzimy do pojemności równej 3. Ponownie możemy spakować aparat. Po jego spakowaniu pojemność plecaka wynosi 2. Sprawdzamy zatem (cofając się w tym samym wierszu do kolumny, która dotyczy pojemności plecaka równej 2), jaka jest maksymalna wartość przedmiotów spakowanych do plecaka o tej pojemności. To 2, zatem dodajemy ją do wartości spakowanego właśnie aparatu (wynosi 1). W komórce wpisujemy wartość 3.

Przechodzimy do pojemności równej 4. Ponownie możemy spakować aparat. Po jego spakowaniu pojemność plecaka wynosi 3. Sprawdzamy zatem (cofając się w tym samym wierszu do kolumny, która dotyczy pojemności plecaka równej 3), jaka jest maksymalna wartość przedmiotów spakowanych do plecaka o tej pojemności. To 3, zatem dodajemy ją do wartości spakowanego właśnie aparatu (wynosi 1). W komórce wpisujemy wartość 4.

Przechodzimy do pojemności równej 5. Ponownie możemy spakować aparat. Po jego spakowaniu pojemność plecaka wynosi 4. Sprawdzamy zatem (cofając się w tym samym wierszu do kolumny, która dotyczy pojemności plecaka równej 4), jaka jest maksymalna wartość przedmiotów spakowanych do plecaka o tej pojemności. To 4, zatem dodajemy ją do wartości spakowanego właśnie aparatu (wynosi 1). W komórce wpisujemy wartość 5.

Uzupełniamy tablicę odpowiednimi wartościami.

Przechodzimy do kolejnego przedmiotu, czyli bukłaka.

Pamiętaj, że w każdym wierszu rozważamy możliwość spakowania przedmiotu z danego wiersza oraz wszystkich poprzednich. Waga bukłaka wynosi 2, a jego wartość wynosi 4.

Przyjrzyjmy się kolumnie o dla pojemności równej 1. W tym momencie maksymalna wartość, którą dotychczas do niej zapakowaliśmy, jest równa 1. Rozważany przedmiot (bukłak) ma wagę równą 2, zatem nie możemy go spakować.

Maksymalna wartość dalej wynosi 1, zatem ją przepisujemy.

Sprawdzamy, czy możemy spakować bukłak do plecaka o pojemności 2. Możemy – w plecaku nie zmieści się nic więcej. Zatem w kolejnym kroku porównujemy wartość bukłaka z maksymalną wartością przedmiotów spakowanych do plecaka o tej pojemności. Jest ona większa, zatem wpisujemy ją do komórki.

Przechodzimy do kolumny o indeksie 3 – taką pojemność plecaka rozważamy. Przedmiot o indeksie 1 (bukłak) może zmieścić się do plecaka. Po jego spakowaniu w plecaku zostaje miejsce na przedmiot o wadze 1. Sprawdzamy maksymalną wartość przedmiotów spakowanych do plecaka o tej pojemności. Wynosi ona 1. Sprawdźmy, czy wartość plecaka po jego spakowaniu będzie większa od dotychczasowej wartości.

Wartość jest większa, zatem w komórce zapisujemy wartość 5.

Do plecaka o pojemności równej 4 również możemy zapakować bukłak. Jednak po jego zapakowaniu pojemność wynosi 2 – w plecaku jest miejsce na inny przedmiot. Cofnijmy się (w tym samym wierszu) do kolumny przeznaczonej dla pojemności plecaka równej 2. Maksymalna wartość, jaką można spakować do plecaka o pojemności 2 wynosi 4. Sprawdzamy, czy suma tych przedmiotów jest większa od dotychczas ustalonej maksymalnej wartości. Jest, zatem wpisujemy nową wartość do komórki.

W przypadku plecaka o pojemności 5 ponownie możemy zapakować bukłak. Po jego spakowaniu pojemność plecaka wynosi 3. Sprawdzamy maksymalną wartość przedmiotów spakowanych do plecaka o tej pojemności. Wynosi ona 5. Suma wartości spakowanych plecaków jest większa od wcześniej osiągniętej wartości, zatem zapisujemy ją w komórce.

Przechodzimy do trzeciego przedmiotu – chlebaka o indeksie 2. Jego wartość wynosi 5, a waga – 2.

Ponownie przepisujemy wartości zapisane w komórkach, które dotyczą pojemności plecaka mniejszej od wagi przedmiotu – w tym przypadku jest to tylko pojemność równa 1.

Do plecaka o pojemności 2 możemy spakować 1 sztukę przedmiotu o indeksie 2 (chlebaka). Sprawdzamy, czy wartość plecaka po spakowaniu tego przedmiotu byłaby większa dla wcześniej ustalonej maksymalnej wartości dla plecaka o pojemności 2. Byłaby większa, zatem uzupełniamy komórkę wartością 5 (jest to wartość chlebaka). Przechodzimy do kolejnej komórki.

Do plecaka o pojemności 3 moglibyśmy spakować przedmiot o indeksie 2. W plecaku zostałoby miejsce na przedmiot o wadze 1. Cofamy się do odpowiedniej komórki i sprawdzamy, czy wartość spakowanych przedmiotów (6) byłaby większa od wcześniej ustalonej maksymalnej wartości spakowanego plecaka o pojemności 3 (5). Byłaby, zatem wpisujemy ją do komórki.

Powtarzamy działanie dla plecaka o pojemności 4. Możemy spakować do niego chlebak. Po spakowaniu chlebaka pojemność plecaka wynosi 2. Sprawdzamy, jaka jest największa możliwa wartość spakowanych przedmiotów dla plecaka o takiej pojemności. Ta wartość to 5. Sprawdzamy, czy wartość spakowanych w ten sposób przedmiotów (10) jest większa od wcześniej ustalonej maksymalnej wartości spakowanych przedmiotów dla tej pojemności plecaka (8). Jest, zatem umieszczamy ją w komórce.

Powtarzamy działanie dla pojemności równej 5. Możemy spakować do niego chlebak. Po spakowaniu chlebaka pojemność plecaka wynosi 3. Sprawdzamy, jaka jest największa możliwa wartość spakowanych przedmiotów dla plecaka o takiej pojemności. Ta wartość to 6. Sprawdzamy, czy wartość spakowanych w ten sposób przedmiotów (1) jest większa od wcześniej ustalonej maksymalnej wartości spakowanych przedmiotów dla tej pojemności plecaka (9). Jest, zatem zapisujemy ją w komórce.

Z tabeli możemy odczytać, że maksymalna wartość spakowanych przedmiotów dla plecaka o pojemności 5 wynosi zatem 11.

W jaki sposób odczytać z tabeli, jakie przedmioty spakowaliśmy?

Odpowiednie dane będziemy odczytywać z tabeli, w której zapisaliśmy maksymalne spakowane wartości dla plecaka o danej pojemności.

Zaczynamy od ostatniej komórki.

Sprawdzamy, czy wartość została uzyskana po spakowaniu przedmiotu o indeksie 2 (chlebaka), czy została przepisana z wiersza wyżej.

Została uzyskana po spakowaniu chlebaka do plecaka o pojemności 5. Jego waga wynosi 2. Odejmujemy ją od pojemności plecaka. Wynik to 3. Przechodzimy (w tym samym wierszu) do kolumny odpowiadającej pojemności plecaka równej 3.

Sprawdzamy, czy jej wartość została przepisana z komórki wyżej. Nie została, zatem do plecaka spakowaliśmy kolejną sztukę przedmiot o indeksie 2 (chlebaka). Jego waga to również 2, zatem odejmujemy ją od pozostałej pojemności plecaka. Wynik to 1. Przechodzimy (wciąż w tym samym wierszu) do kolumny odpowiadającej pojemności plecaka równej 1.

Wartość została przepisana z komórki wyżej, zatem do niej przechodzimy.

Ta wartość również została przepisana z komórki wyżej – przechodzimy do niej.

Nad tą komórką nie ma już innej, oznacza to, że przedmiot o indeksie 0 został spakowany do plecaka. Po jego spakoiwaniu pojemność plecaka wynosi 0. Zapełniliśmy zatem plecak przedmiotami.

Znajduje się w niej wartość, która również nie została przepisana z komórki wyżej.

W konsekwencji spakowano:

• przedmiot o indeksie 0: 1 sztuka;

• przedmiot o indeksie 1: 0 sztuk;

• przedmiot o indeksie 2: 2 sztuki.

zapamiętywanie wyników mniejszych podproblemów, aby później móc z nich skorzystać przy dalszych etapach rozwiązywania większych podproblemów

problem obliczeniowy, którego rozwiązanie polega na znalezieniu największej lub najmniejszej wartości pewnego parametru tego problemu, spełniającej określoną własność

Problem plecakowy, który jest tematem tej serii e‑materiałów, polega na takim wyborze przedmiotów z danego zbioru, by po spakowaniu wybrane przedmioty miały jak największą wartość, ale ich waga nie przekraczała pojemności plecaka. Istnieją różne metody jego rozwiązania, w tej serii prezentujemy jedną z nich – podejście zachłanne.