Wprowadzenie do programowania dynamicznego

Czym jest programowanie dynamiczne?

W kontekście algorytmiki programowanie dynamiczne nie jest rozumiane jako pisanie programów komputerowych, lecz jako metodę rozwiązywania problemów za pomocą rozbicia go na mniejsze podproblemy (rozwiązania podproblemów umieszczane są w tablicy, stąd nazwa "programowanie").

Programowanie dynamiczne stosuje się najczęściej do rozwiązywania tzw. problemów optymalizacyjnych. W takich zagadnieniach istnieje zazwyczaj więcej, niż jedno rozwiązanie. Dzięki zastosowaniu tytułowego algorytmu, można szybko wyznaczyć maksymalny bądź minimalny koszt, dzięki rozwiązywaniu mniejszych podproblemów i wykorzystywaniu tych rezultatów przy dochodzeniu do wyników coraz większych podproblemów (tzw. metoda wstępująca).

Ogólny problem plecakowy

Na początek warto przedstawić chyba najpopularniejszy problem z zakresu programowania dynamicznego. Jest to ogólny problem plecakowy, którego rozwiązanie polega na podaniu maksymalnej wartości przedmiotów zapakowanych do plecaka, przy ograniczonej jego pojemności oraz określonej wartości i ilości zajmowanego miejsca poszczególnych przedmiotów.

Dla przykładu posłużę się następującymi danymi:

Pojemność plecaka: 10
Przedmioty:
1) wartość: 3; objętość: 2
2) wartość: 5; objętość: 3
3) wartość: 1; objętość: 1

Do zapisywania danych najlepiej użyć tablicy jednowymiarowej od 1 do 10. Kolejne komórki w takiej tablicy będą oznaczały pojemności plecaka, a wartościami tych komórek będą maksymalne wartości plecaków o danej pojemności (na początku wszystkie przyjmują wartość zero, gdyż nie został jeszcze rozpatrzony żaden przedmiot). Programowanie dynamiczne polega na stopniowym rozwiązywaniu problemu - tak więc najpierw uzyskujemy wynik optymalnego wypełnienia plecaka o pojemności 1, potem 2, itd.

Tablicę wypełniamy, biorąc pod uwagę kolejne przedmioty. Tak więc rozpoczynamy od pierwszej rzeczy. Zajmuje ona dwie jednostki. Wiadomo, że nie zmieści się do plecaka o pojemności 1 - komórka numer jeden pozostaje bez zmian. Natomiast do plecaka dwujednostkowego zmieścimy jeden taki przedmiot - do trzyjednostkowego podobnie, a do torby o pojemności cztery upchniemy już dwie sztuki, itd.

Teraz nieco trudniejszy etap - bierzemy pod uwagę drugi przedmiot. Wypełnianie rozpoczynamy od trzeciej komórki (gdyż do mniejszych plecaków przedmiot się nie zmieści, a to nie przyniesie żadnych zmian). Mamy w tym przypadku do wyboru upakowanie za pomocą przedmiotu nr 1 (wartość: 3) lub nr 2 (wartość: 5). Optymalniejszym wyborem jest druga możliwość, więc wartość trzeciej komórki należy ustawić na 5. Jeśli istniałaby możliwość optymalnego wypakowania przedmiotami więcej, niż jednego rodzaju, należy taki sposób zastosować (stanie się tak w piątej komórce - jeden przedmiot nr 1 i jeden nr 2). Konkretnie: do wypełnienia komórki wybieramy jedną z dwóch wartości: aktualna wartość komórki (

t[i]

) lub wartość komórki o numerze pomniejszonym o objętość przedmiotu plus wartość tegoż przedmiotu (t[i-obj[j]] + wart[j]

). Dalej tablicę wypełniamy analogicznie. Wynikiem działania algorytmu będzie tablica, której to wartościami komórek o poszczególnych indeksach będą maksymalne wartości przedmiotów, jakie można zmieścić do plecaka o pojemności równej indeksowi tablicy. Więc dla naszych danych poprawny wynik zapisany jest w dziesiątej komórce.

Poniżej kod źródłowy w Pascalu (zastosowano tutaj tablicę od 0, gdyż powstawałyby błędy dla przedmiotu o objętości takiej samej, jak numer komórki - 
```delphi
t[i - i]

-> t[0]

):

```delphi
program ogolnyproblemplecakowy;

var obj,wart:array[1..10] of Byte;
    t:array[0..65535] of Longint;
    n,j:Byte;
    m,i:Word;

begin
  Readln(m);  //podaj pojemność plecaka
  Readln(n);  //podaj liczbę przedmiotów
  for i:=1 to n do
    Readln(obj[i],wart[i]); //podawaj kolejne objętości i wartości

  for j:=1 to n do
    for i:=obj[j] to m do
      if t[i]<t[i-obj[j]]+wart[j] then
        t[i]:=t[i-obj[j]]+wart[j];

  Writeln(t[m]);
end.