Dinaminis programavimas: Skirtumas tarp puslapio versijų

139 pridėti baitai ,  prieš 7 metus
S (Bot: Migrating 28 interwiki links, now provided by Wikidata on d:q380679 (translate me))
end;
 
== "Kuprinės"„Kuprinės“ uždavinys ==
Š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.
 
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, Kik] := F[J-1, Kik];
'''if''' D[J] <= Kik '''then'''
F[J, Kik] := Max(F[J, Kik], F[J-1, Kik-D[J]] + V[J]);
'''end''';
'''end''';
 
[[Kategorija:Programavimas]]
67

pakeitimai