Programowanie dynamiczne

Dyskretny problem plecakowy

Jest N przedmiotów. Każdy waży wi kilogramów i kosztuje kosztuje ci. Możemy unieść maksymaknie K kilkogramów. Które przedmioty wziąć, aby łączna wartość zabranych towarów była jak największa?

Rozwiązanie

Niech wynik[n, k] oznacza rozwiązanie dla pierwszych n przedmiotów i plecaka rozmiaru k. Znając wynik dla mniejszych danych możemy obliczyć go dla większych danych. Konkretnie jest tak:
wynik[n, k] = max(wynik[n-1, k], wynik[n-1, k-wi]+ci, wynik[n, k-1])
Możemy bowiem albo nie brać n-tego przedmiotu i zapełnić k kilogramów poprzednimi przedmiotami (wynik[n-1, k]), albo wziąć n-ty przedmiot i zapełnić k-wi kilogramów poprzednimi przedmiotami (wynik[n-1, k-wi]+ci), albo pozostawić ostatni kilogram plecaka pusty i popatrzeć co się mieści w k-1 kilogramach (wynik[n, k-1]). Rozwiązanie to działa w czasie O(NK).

Oto program, który to liczy:

{w tablicach w oraz c mamy dane przedmiotów}
for a := 0 to K do
    wynik[0, a] := 0;
for p := 1 to N do
    for a := 0 to K do begin
	wynik[p, a] := wynik[p-1, a];
	if (a>=1) and (wynik[p, a-1]>wynik[p, a]) then
	    wynik[p, a] := wynik[p, a-1];
	if (a>=w[p]) and (wynik[p-1, a-w[p]]+c[p]>wynik[p, a]) then
	    wynik[p, a] := wynik[p-1, a-w[p]]+c[p];
    end;
{w wynik[N, K] mamy rozwiązanie}

Najdłuższy wspólny podciąg

Mamy dwa ciągi: xi oraz yi. Chcemy znaleźć najdłuższy wspólny podciąg. Na przykład dla ABCBDAB i BDCABA może to być BCBA.

Rozwiązanie

W tab[i, j] pamiętamy długość najdłuższego wspólnego podciągu dla x1, x2, ... xi oraz y1, y2, ... yj. 
for i := 1 to dlug_x do tab[i, 0] := 0;
for j := 0 to dlug_y do tab[0, j] := 0;
for i := 1 to dlug_x do
    for j := 1 to dlug_y do
    	if x[i]=y[j] then
    	    tab[i, j] := tab[i-1, j-1]+1
    	else if tab[i-1, j]>=c[i, j-1] then
    	    tab[i, j] := tab[i-1, j]
        else
    	    tab[i, j] := tab[i, j-1];

A jak odzyskać ciąg?

for i := 1 to dlug_x do tab[i, 0] := 0;
for j := 0 to dlug_y do tab[0, j] := 0;
for i := 1 to dlug_x do
    for j := 1 to dlug_y do
    	if x[i]=y[j] then begin
    	    tab[i, j] := tab[i-1, j-1]+1;
    	    tab2[i, j] := OBIE;
    	end else if tab[i-1, j]>=c[i, j-1] then begin
    	    tab[i, j] := tab[i-1, j];
    	    tab2[i, j] := PIERWSZY;
        end else begin
    	    tab[i, j] := tab[i, j-1];
    	    tab2[i, j] := DRUGI;
    	end;
i := dlug_x; j := dlug_y;
while (i<>0) and (j<>0) do begin
    if tab2[i, j]=OBIE then begin
    	ciag[tab[i, j]] := x[i];
    	i := i-1; j:= j-1;
    end else
    if tab2[i, j]=PIERWSZY then
    	i := i-1;
    else
    	j := j-1;
end

Zadanie - Wydawanie reszty

Na ile sposobów można wydać X złotych reszty dysponując nieograniczoną ilością monet(banknotów) o K różnych nominałach N1..NK złotych ?

Przykład

Dysponując monetami o nominałach 1, 2 i 5 złotych, resztę 5 złotych możemy wydać na 4 sposoby:

1 + 1 + 1 + 1 + 1
1 + 1 + 1 + 2
1 + 2 + 2
5

Dane wejściowe

W kolejnych wierszach wejścia podane są:
Liczba naturalna X <= 10000
Liczba naturalna K <= 50
Ciąg liczb naturalnych (nominałów) N1 < N2 < ... < NK < 10000.

Dane wyjściowe

Liczba różnych sposobów wydania reszty. 







{ zakladamy, ze wynik miesci sie w longint }
Program Reszty;

Const
  Max_X = 10000;
  Max_K = 50;

Var
  X, K    : longint;
  Nom     : array[1..Max_K] of longint;  { nominaly }
  s       : array[0..Max_X] of longint;  { liczba sposobow }

  i, n    : longint;                     { zmienne pomocnicze }

begin
  readln(X);                         { wczytaj wielkosc reszty }
  readln(K);                         { wczytac liczbe nominalow }
  for i := 1 to K do read(Nom[i]);   { wczytaj wartosci nominalow }

  for i := 1 to X do s[i] := 0;      { wyzeruj tablice wynikow }

  s[0] := 1;                         { 0 zlotych mozna wydac na 1 sposob }

  for n := 1 to K do begin
    for i := Nom[n] to X do
        s[i] := s[i] + s[i - Nom[n]];
  end;

  writeln(s[X]);                     { wypisz wynik }
end.