Algorytmy

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 -
t[i - i]
->
t[0]
):

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.

2 komentarze

Thomashek 2005-12-11 16:46

Nie nazwałem artykułu w stylu \"Kompendium [...]\", tylko \"Wprowadzenie...\". Owszem, tekst może być podobny do innych publikacji (np. pana Sysły), gdyż między innymi na tym się wzorowałem. Artykuł miał na celu bardzo ogólne zarysowanie problemu, bez wprowadzania w szczegóły, które nadają się na osobne artykuły. Pozdrawiam

lmmilewski 2005-12-02 23:11

Ogolnie nie ocenialbym tego artu (ze wzgledu na date), ale poswiecilem czas na przeczytanie (jest 23:13) i sie troche zawiodlem :( Nie ma nic o optymalnej podstrukturze, wspolnych podproblemach. Tak wlasciwie to art powinien nazywac sie \"rozwiazywanie problemu plecakowego\". I jeszcze jedna rzecz - wstep gdzies juz czytalem :(