Dinaminis programavimas: Skirtumas tarp puslapio versijų

3 pridėti baitai ,  prieš 11 metų
S
wiki sintakse 3
S (wiki sintakse 2)
S (wiki sintakse 3)
Šio tipo uždaviniai gana dažni. Bendrai jie formuluojami taip: turime <math>N</math> daiktų, bei žinome jų dydžius <math>D_i</math> bei vertes <math>V_i</math>. Kuprinės dydis yra <math>K</math>, taigi galima paimti tik tiek daiktų, kad jų dydis neviršytų <math>K</math>. Reikia surasti tokį daiktų rinkinį, kurio vertė būtų didžiausia.
 
Dinaminio sprendimo idėja:
* Tarkime, nagrinėjame <math>J</math>-tąjį daiktą, o kuprinėje dar yra <math>K</math> talpos vienetų
:* Jeigu daiktą imame, tuomet galime iš <math>J-1</math> daiktų paimti tiek, kad neviršytų <math>K-D_j</math>
:* Jeigu neimame, tuomet galime iš <math>J-1</math> daiktų paimti tiek, kad neviršytų <math>K</math>
* 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>.
427 096

pakeitimai