Dinaminis programavimas: Skirtumas tarp puslapio versijų

92 pridėti baitai ,  prieš 15 metų
čia nebūtinai reik TeX, be jo geriau skaitosi.
S (robot Adding: de, zh, he)
(čia nebūtinai reik TeX, be jo geriau skaitosi.)
*Iš šių dviejų atvejų, pasirenkme vertingesnį.
 
Taigi, problemą <math>J</math> daiktų atveju galime išspresti, jeigu žinome problemos <math>J-1</math> daiktų daiktų atveju sprendimą. Matematiškai tai atrodo taip: <math>F(j, \mbox{ } k) = max(F(j-1,\mbox{ } k), \mbox{ } F(j-1, \mbox{ } k-D_j) + V(j))</math>. Sprendimą galima rasti, ieškant nuo apačios, t.y. pirma apskaičiuojant <math>F</math> reikšmes su mažesnėmis <math>J</math> 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ų: <math>F(0, \mbox{ } k) = 0</math>.
 
Programos fragmentai:
 
<b>for</b> J := 1 <b>to</b> N <b>do</b>
<b>begin</b>
F[J, K] := F[J-1, K];
<b>if</b> D[J] <= K <b>then</b>
V[J, K] := Max(V[J, K], V[J-1, K-D[J]] + V[J]);
<b>end</b>;
 
[[Category:Programavimas]]
160

pakeitimų