ALGORYTMICZNA PRZYGODA

Kaliny

Programowanie dynamiczne to niezwykle ważna technika w dziedzinie programowania i algorytmiki. Przydaje się zarówno w przypadku olimpiady, jak i rozwiązywania codziennych problemów, na przykład pakowania plecaka.
W tym poście postaram się Wam bardziej przybliżyć temat właśnie programowania dynamicznego.

Zacznę od przedstawienia chyba najpopularniejszego problemu do rozwiązania za pomocą programowania dynamicznego: problemu plecakowego.
Mamy plecak o pojemności k (może pomieścić przedmioty o maksymalnej sumarycznej wadze k). Chcemy do niego spakować n przedmiotów o różnej wadze i wartości.
Jak najoptymalniej spakować plecak (czyli jak uzyskać największą wartość przedmiotów, nie przekraczając tym samym największej możliwej wagi plecaka)?
Można by było podejść do tego problemu zachłannie, tzn. wybierać przedmioty o największej możliwej wartości, i jeśli się zmieszczą do plecaka, to je zapakować.

Zobaczmy na przykładzie:

4 10 //n oraz k
4 2 //wartość oraz waga pierwszego przemiotu
2 1 //wartość oraz waga drugiego przedmiotu
3 3 //wartość oraz waga trzeciego przemiotu
4 8 //wartość oraz waga czwartego przemiotu

Teraz posortujmy te przedmioty malejąco po wartości, a jeśli jest taka sama, to rosnąco po wadze (można do tego napisać funkcję i wstawić ją do funkcji sort).

4 2
4 8
3 3
2 1


Tak więc wybieramy pierwszy przedmiot. Zmieści się nam do plecaka, ponieważ ma wagę 2. Aktualna wartość przemiotów w plecaku to 4.
Wybieramy też drugi przedmiot, ponieważ do plecaka możemy go zapakować (w plecaku zostało nam 8). Po włożeniu tego przemiotu do plecaka nie możemy już nic zapakować.
Wartość wszystkich przemiotów w plecaku to 8. Czy można uzyskać większą? Okazuje się, że tak. Spróbujmy rozwiązać ten problem za pomocą programowania dynamicznego.

0 1 2 3 4 5 6 7 8 9 10
{0, 0}
{4, 2}
{2, 1}
{3, 3}
{4, 8}

W tej tabelce wypisałam kolejne przedmioty i możliwe pojemności plecaka. Spróbujmy ją uzupełnić.

Mając tylko przedmiot {0, 0} (użyłam go jako "brak przedmiotu"), maksymalna wartość jaką możemy uzyskać,
niezależnie od pojemności plecaka, to 0.

0 1 2 3 4 5 6 7 8 9 10
{0, 0} 0 0 0 0 0 0 0 0 0 0 0
{4, 2}
{2, 1}
{3, 3}
{4, 8}


Teraz mamy pierwszy przedmiot. Kiedy pojemność plecaka to 0, nie możemy go włożyć, dlatego wynik wynosi 0. Podobnie dla pojemności 1.
Ale kiedy mamy pojemność 2, to ten przedmiot już się zmieści (bo ma wagę 2). Dlatego od momentu, kiedy pojemność wynosi 2 maksymalny wynik to 4.

0 1 2 3 4 5 6 7 8 9 10
{0, 0} 0 0 0 0 0 0 0 0 0 0 0
{4, 2} 0 0 4 4 4 4 4 4 4 4 4
{2, 1}
{3, 3}
{4, 8}


Przejdźmy do drugiego przedmiotu. Przy pojemności 0 nie możemy go włożyć, a więc wynik wynosi 0. Ale od pojemności 1 już się zmieści, dlatego wynik wynosi 2.

0 1 2 3 4 5 6 7 8 9 10
{0, 0} 0 0 0 0 0 0 0 0 0 0 0
{4, 2} 0 0 4 4 4 4 4 4 4 4 4
{2, 1} 0 2 2 2 2 2 2 2 2 2 2
{3, 3}
{4, 8}

Hmmm... ale czy nie możemy dołożyć jeszcze poprzedniego przedmiotu przy pojemności 3? Przecież do plecaka zmieszą się oba.
Poza tym, w tabeli przechowujemy maksymalne wyniki, to przy pojemności 2 powinno być 4 (ponieważ jest większe od 1).

0 1 2 3 4 5 6 7 8 9 10
{0, 0} 0 0 0 0 0 0 0 0 0 0 0
{4, 2} 0 0 4 4 4 4 4 4 4 4 4
{2, 1} 0 2 4 6 6 6 6 6 6 6 6
{3, 3}
{4, 8}

Wiemy już, że dla dwóch pierwszych przedmiotów i k = 10 maksymalna wartość do uzyskania wynosi 6.
Ale jak to obliczać dalej? Przecież sprawdzanie za każdym razem, który przedmiot dodać, a który nie, czy się zmieści, która wartość jest większa i tak dalej jest trochę kłopotliwe...

Sposób na szybsze rozwiązanie tego problemu przedstawię Wam w następnym poście :)