Matematické Fórum

Zda se mi to docela slozite, take tomu nerozumim :-) nevim, jestli ma cenu podrobne rozepisovat kazdy prikaz, pro zacatek zkusim popsat co me k tomu napada, ale nevim, jestli to dokazu popsat srozumitelne:

Jsou tam ty vektory weights (w1, w2, w3, ...) a values (v1, v2, v3, ...) ktere maji stejny pocet slozek, pak je tam jeste ta matice A - ta je ze zacatku nulova (to je to A = zeros(length(weights)+1,W+1);), ma o jeden radek vic nez maji ty vektory slozek. j je tam pouzite pro radek v te matici A, Y je jako sloupec (vetsinou), napriklad: A(j+1,Y+1). Ty cykly by se daly zobrazit nejak tak:

     Y:1 2 3 ... 20  weights  values
   j A
   1   0 0 0      0    w1       v1
   2   0 0 0      0    w2       v2
   3   0 0 0      0    w3       v3
  ...
   ?   0 0 0      0    w?       w?

Prvni je cyklus pro j, cili nejdriv se provadi pro ten prvni radek (j=1), pak pro druhy (j=2) atd. pak je cyklus pro Y, cili pro kazdy radek (stejne j) se ty prikazy uvnitr cyklu provedou nejdriv pro prvni sloupec (Y=1), pak pro druhy (Y=2) atd.

Ted uz k tomu, co se provadi tam vevnitr cyklu, cili v tom
            if weights(j) > Y
                A(j+1,Y+1) = A(j,Y+1);
            else
                A(j+1,Y+1) = ...
                    max( A(j,Y+1), values(j) + A(j,Y-weights(j)+1));
            end

Nejdriv je tam podminka - kdyz je weights(j) vetsi nez Y, tak se provede ten prvni prikaz, cili kdyz napriklad weights(2) bude 4, tak pro druhy radek to znamena, ze podminka bude splnena pro Y rovne 1, 2 nebo 3. Ten prvni prikaz je A(j+1,Y+1) = A(j,Y+1); - cili hodnota z j-teho radku ve sloupci Y+1 se nakopiruje do dalsiho, cili j+1-ho radku. Takze by se pod tim dalo predstavit to, ze hodnoty ve sloupci s mensim indexem nez weights(j) se kopiruji do dalsiho radku. Pro ten priklad jak jsem psal by to znamenalo, ze hodnoty ve 2., 3. a 4. sloupci ve druhe radce se nakopiruji do treti radky. Pro ty dalsi sloupce kopiruje vetsi ze dvou hodnot - bud ta hodnota z matice (stejne jako pri splnene podmince), anebo - soucet slozky toho vektoru values a hodnoty ze sloupce, ktera je posunuta o sloupcu weights(j) doleva. Nakonec to vezme nejaky vysledek z posledniho radku a sloupce te matice.
Co presne to ma pocitat, to nevim :-) mozna nad tim jeste budu premyslet anebo se podivam, jestli k tomu neco nenajdu. Odkud to vlastne mas? Vis, co to ma delat?