Dinaminis programavimas

Dinaminis programavimas – programavimo metodas, paremtas uždavinio skaidymu į mažesnes susijusias problemas, bei tų problemų sprendimų įsiminimu. Taigi laiko sąnaudos pakeičiamos atminties sąnaudomis. Jis naudojamas, kuomet „Skaldyk ir valdyk“ nėra pakankamai efektyvus. Gali būti pritaikomas įvairaus tipo uždaviniams, tačiau šio metodo taikymo galimybę pastebėti ne visuomet lengva.

Fibonačio skaičiai 
Apibrėžimas: , , . Reikia apskaičiuoti -tąjį sekos narį. Rekursyvus sprendimas būtų toks:

  int Fibonacci(int n) {
    if (n < 2) {
      return 1;
    } else {
      return Fibonacci(n-1) + Fibonacci(n-2);
    }
  }

Dinamiškai galime parašyti taip:

  int Fibonacci[N];
  
  Fibonacci[0] = Fibonacci[1] = 1;
  for (int i = 2; i < N; i++) {
    Fibonacci[i] = Fibonacci[i-1] + Fibonacci[i-2];
  }

Taip gauname visas reikšmes nuo  iki .

Taip pat yra algoritmas surasti tam tikrą Fibonačio skaičių:
  
  Fibonacci[0] := 1;
  Fibonacci[1] := 1;
  for i := 2 to n do
    begin
      tmp := Fibonacci[0];
      Fibonacci[0] := Fibonacci[1];
      Fibonacci[1] := Fibonacci[0] + tmp;
    end;

„Kuprinės“ uždavinys 
Šio tipo uždaviniai gana dažni. Bendrai jie formuluojami taip: turime  daiktų, bei žinome jų dydžius  bei vertes . Kuprinės dydis yra , taigi galima paimti tik tiek daiktų, kad jų dydis neviršytų . Reikia surasti tokį daiktų rinkinį, kurio vertė būtų didžiausia.

Dinaminio sprendimo idėja:
 Tarkime, nagrinėjame -tąjį daiktą, o kuprinėje dar yra  talpos vienetų
 Jeigu daiktą imame, tuomet galime iš  daiktų paimti tiek, kad neviršytų 
 Jeigu neimame, tuomet galime iš  daiktų paimti tiek, kad neviršytų 
 Iš šių dviejų atvejų, pasirenkame vertingesnį.

Taigi, problemą  daiktų atveju galime išspręsti, jeigu žinome problemos  daiktų daiktų atveju sprendimą. Matematiškai tai atrodo taip: . Sprendimą galima rasti, ieškant nuo apačios, t. y. pirma apskaičiuojant  reikšmes su mažesnėmis  reikšmėmis. Taip pat, būtina atkreipti dėmesį, kad būtina turėti tam tikras „ribines“ reikšmes. Šiuo atveju tai būtų: .

Programos fragmentai:

  for ik := 0 to K do
     F[0, ik] := 0;
  for J := 1 to N do
  begin
    for ik := 0 to K do
    begin
      F[J, ik] := F[J-1, ik];
      if D[J] <= ik then
        F[J, ik] := Max(F[J, ik], F[J-1, ik-D[J]] + V[J]);
    end;
  end;

Programavimas