Rozwiązanie metodą tzw. programowania dynamicznego, problemu plecakowego

Programowanie dynamiczne - rozwiązywanie kolejnych pod-problemów i zapamiętywanie tych rozwiązań.

Problem plecakowy

Dane: n - liczba przedmiotów
P - pojemność plecaka
o₁, o₂, . . . , o_n - pojemności kolejnych przedmiotów
c₁, c₂, . . . , c_n - ceny kolejnych przedmiotów
Zadanie: zapakować plecak (nie przekraczając jego pojemności) dostępnymi przedmiotami
tak, by łączna cena zapakowanych przedmiotów była jak największa.


Rozwiązanie
Tablica częściowych rozwiązań:


a_ij = optymalna cena zapakowania pojemności j przedmiotami ze zbioru {1, . . . ,i}
- podproblem -

Pierwszy wiersz tej tablicy możemy łatwo wypełnić:
dla j=1,2, . . ., P jeżeli o₁ ≤ j to a_1j = c1 w przec. przyp. a_1j = 0







Załóżmy, że wytłuszczony rejon tablicy a jest już policzony. Chcemy teraz policzyć a_ij.
Mamy dwie opcje na możliwą wartość a_ij:

• wersja z przedmiotem nr. i
jeżeli j>o_i to opcja1 = a_i-1j-oi + c_i w przec przyp.
jeżeli j=o_i to opcja1 = c_i w przec. przyp.
jeżeli j<o_i to opcja1 = 0

• wersja bez przedmiotu nr. i
opcja2 = a_i-1j

Wybieramy lepszą z tych dwóch opcji:

a_ij = max( opcja1, opcja2 )

Algorytm:
// wypełniamy pierwszy wiersz tablicy a
dla j = 1, 2, . . . , P
jeżeli o1≤j to a1j = c1 w przec. przyp. a1j = 0
dla i = 2, 3, . . . , n // dla każdego wiersza
dla j = 1, 2, . . . , P // przebiegamy wszystkie pozycje w tym wierszu
{ jeżeli j > o_i to opcja1 = a_i-1j-oi + c_i w przec. przyp.
jeżeli j == o_i to opcja1 = c_i w przec.przyp. opcja1 = 0;
opcja2 = a_i-1j;
a_ij = max( opcja1, opcja2 );
};
wypisz wartość optymalnego zapakowania plecaka: a_nP .



koniec

12...i...n

1 2 . . . j . . . . P

a₁₁ . . . . . . a_1j . . . a_1P
a₂₁ . . . . . . a_2j . . . a_2P
. .
. .
. .
. .
a_i1 . . . . . . . a_ij. . . . .a_iP
. .
. .
. .
a_n1 . . . . . . a_nj . . . a_nP

Jednostki pojemności

Numery przedmiotów

12...i.
.n

1 2 . . . j . . . . P

a₁₁ . . . . . . a_1j . . . a_1P
a₂₁ . . . . . . a_2j . . . a_2P
. . .
. . .
. . .
. a_i-1j .
a_i1 . . . . . a_ij-1 a_ij. . . . .a_iP
. .
. .
. .
a_n1 . . . . . . a_nj . . . a_nP

Jednostki pojemności

Numery przedmiotów

---