Čia dinaminis programavimas?

Pridedu uždavinį. Reiktų idėjos kaip jį spręsti, nes stoviu vietoje :)

 

Lyg ir dinaminio programavimo uždavinys. Bet šitoje srityje neturiu pakankamai patirties. Gal kas užvesit ant kelio?

DP.pdf

Redagavo Sausio 1, 2010 mantasurnieza

Nieko aš ten dinamiško neįžvelgiu, paprastas rikiavimo uždavinys.

Nieko aš ten dinamiško neįžvelgiu, paprastas rikiavimo uždavinys.

 

Kad aš čia niekur to paprastumo nematau :) Godusis algoritmas netinka.

Prasuk rekursija su visais imanomais variantais ir viskas :) Gal ir veiks ilgiau nei naudojant koki tai algoritma, bet veiks ;)

Prasuk rekursija su visais imanomais variantais ir viskas :) Gal ir veiks ilgiau nei naudojant koki tai algoritma, bet veiks :)

Hm... Norint išrinkti 1000 slidžių iš 2000 galimų, reiks išbandyti 2000!/(1000!)^2 kombinacijų. Šį skaičių sudaro 600 skaitmenų, tad net galingiausias pasaulio kompiuteris šiam skaičiavimui užtruktų daugiau, nei kad gyvuoja mūsų visata. Per lėtai. ;)

 

Taip, čia dinaminio programavimo uždavinys. Reikia susirikiuoti slides pagal ilgius ir tada naudoti dvimatį masyvą, kurio vienas indeksas (tarkim stulpelio nr. - n) rodytų paskutinės (ne)panaudotos slidės numerį, kitas (eilutės nr. - p) - sudarytų porų skaičių, o reikšmė - minimalų ilgių skirtumą.

Pažymėkime tą skirtumą k(n, p), o n-tosios slidės ilgį l(n).

Tuomet jei 2n<p, k(n, p) = begalybė (t.y. neįmanoma sudaryti reikiamo kiekio porų).

Jei 2n = p, tai k(n, p) lygi l(1) - l(2) + l(3) - l(4) + ... +l(n-1) - l(n).

Jei 2n > p, tai k(n, p) = min(k(n-1, p), k(n-2, p-1) + l(n-1) - l(n)).

Lentelė pildoma "iš viršaus į apačią" metodu.

Jei supranti dinaminio programavimo principus, pasigilinęs turėtum suprasti iš kur atsiranda šitos formulės. Jei vis dėlto nesupranti - klausk, bandysiu aiškinti išsamiau. :)

 

Tikiuosi neprivėliau klaidų. Bet jei ką - nepykit. Visgi naktis, o iš telefono rašyti nepatogu...

Arba aš nesupratau arba suklydai tu. Aš sprendinio vertę apibrėžiau taip:

 

n - paskutinė nepanaudota slidė;

p - sudarytų porų skaičius;

 

k (n, p) = begalybe; , kai n < 2*p

k (n, p) = l[1] - l[2]....+ l[n - 1] - l[n]; , kai 2*p = n

k (n, p) = min (k(n-1, p), k(n-2, p-1) + l[n] - l[n-1]); , kitais atvejais.

 

sprendinio vertei rasti pasirašiau funkciją:

 

   function l (n, p : integer; arg : arr) : longint;
 var i : integer;
  begin
 if n < 2*p
   then l := maxint;
   else
	 if 2*p = n
	   then
		 begin
		   l := 0;
		   for i := 1 to n do
			 if i mod 2 = 0
			   then l += arg[i].ilgis
			   else l -= arg[i].ilgis;
		 end
   else l := min(l(n-1, p, arg), l(n-2, p-1, arg) + arg[n].ilgis - arg[n-1].ilgis);
  end;

 

Lyg ir veikia. Jei gali, paaiškink smulkiau apie tą masyvą kur aiškinai ir kaip aš iš jo atrinksiu sprendinį? Kaip jį susidaryti?

Arba aš nesupratau arba suklydai tu. Aš sprendinio vertę apibrėžiau taip:

 

n - paskutinė nepanaudota slidė;

p - sudarytų porų skaičius;

 

k (n, p) = begalybe; , kai n < 2*p

k (n, p) = l[1] - l[2]....+ l[n - 1] - l[n]; , kai 2*p = n

k (n, p) = min (k(n-1, p), k(n-2, p-1) + l[n] - l[n-1]); , kitais atvejais.

Taip, čia beveik viskas teisingai. :biggrin_xmas:

Tik su ženklais truputį painiavos įsivėlė turbūt. Prieš rašant sąlygas reiktų nuspręsti kokia tvarka išrikiuotos slidės.

Jei didėjimo, tai suklydai antroje eilutėje. Ji turėtų būti:

k (n, p) = - l[1] + l[2]....- l[n - 1] + l[n];

 

Jei mažėjimo, tai suklydai trečioje. Ji turėtų būti:

k (n, p) = min (k(n-1, p), k(n-2, p-1) + l[n-1] - l[n]);

 

Dabar belieka pastebėti, kad surasti k (n, p) reikšmę Tau tereikia žinoti daugiausiai dvi reikšmes - k(n-1, p) ir k(n-2, p-1).

 

Tai pradedam pildyti nuo pirmos eilutės:

k(0, 0) bus nulis, nes jei reikia sudaryti nulį porų, tai natūralu, kad ir ilgio skirtumo neturėsime.

Tas pats su k(1, 0), k(2, 0) ir t.t. iki k(n, 0).

 

Užpildę pirmąją eilutę einame prie antros:

k(0, 1) bus begalybė (n<2*p)

k(1, 1) bus begalybė (n<2*p)

k(2, 1) bus l[1]-l[2] (nes 2*p = n) (imu, kad slidės surikiuotos mažėjimo tvarka)

k(3, 1) bus min(k(2, 1), k(1, 0) + l[2] - l[3]); (visas šiam skaičiavimui reikalingas k reikšmes jau turime)

ir taip toliau pildome šią eilutę iki k(n, 1).

 

Ir taip toliau pildome stulpelius iki k(n, p). :)

 

T.y. Jei pataisysi minėtą smulkią klaidelę savo funkcijoje, tai turėtų veikti toks paprasčiausias dvigubas ciklas:

for i:=1 to p do
 for j:=1 to n do
k[j][i]:=l(j, i);

 

Grubiai skaičiuojant vienos eilutės reikšmei apskaičiuoti daugiausiai gali reikti padaryti M+N veiksmų (M - skaičiuojant tą atvejį, kai 2*p=n, o N - po vieną veiksmą visiems kitiems tos eilutės langeliams). Daugiausiai eilučių gali būti N, vadinasi maksimalus galimas veiksmų kiekis ~N*(N+M)~=3 000 000, ką kiekvienas kompiuteris spės atlikti per sekundę. :D

 

Jei dar kas neaišku - rašyk. Smagu, kad žmonės bando spręsti ir sudėtingesnius, olimpiadinius uždavinukus. :P

Viskas iki čia aišku :biggrin_xmas: O kaip man dabar tas slidžių poras gauti? Nes prašo ne tik sprendinio vertės, bet ir pačio sprendinio.

 

Smagu kad čia lankosi žmonių, galinčiu padėti ne tik su mokykliniais uždaviniais. Ačiū, Rimai. :)

O kaip man dabar tas slidžių poras gauti? Nes prašo ne tik sprendinio vertės, bet ir pačio sprendinio.

Hm... Nepastebėjau šito. Truputį komplikuoja čia viską. Reikia modifikuoti sprendimą.

 

Vienas iš galimų variantų - susikurti dar vieną tokio paties dydžio masyvą, tik šį kartą ne skaičiams, o boolean reikšmėms.

Tuomet atliekant langelių reikšmių skaičiavimus pirmame masyve, tame papildomame masyve (pažymėkime jį s(n, p)) žymimės, ėmėme tą slidę, ar ne. Tai galima nuspręsti iš to, kurią reikšmę pasirinkome skaičiuodami šią eilutę:

k (n, p) = min (k(n-1, p), k(n-2, p-1) + l[n-1] - l[n]);

Jei pasirinkome pirmą reikšmę, reiškia tos slidės neėmėme ir s(n, p) = false;

Jei pasirinkome antrą reikšmę, reiškia slidę ėmėme ir s(n, p) = true;

 

Turėdami pilnus abu masyvus, pradedame nuo reikiamo langelio, kuriame yra rezultatas (n, p) ir atsekinėjame sprendinį.

Jei s(n, p) = true, tai reiškia, jog ėmėme slide n ir n-1. Jas išvedame. Toliau taip pat nagrinėjame langelį s(n-2, p-1).

Jei s(n, p) = false, vadinasi šios slidės neėmėme, nieko neišvedame ir toliau nagrinėjame langelį s(n-1, p);

Priėję vietą, kai p = 0, busime išvedę visas panaudotas slides. :biggrin_xmas:

 

Yra ir kitokių variantų. Galima vietoje dviejų masyvų naudoti tik vieną su record tipo reikšme (galbūt geresnis programavimo stilius). Gal ir dar kitokių variantų sprendinio atsekimui būtų galima sugalvoti, bet principas turėtų būti panašus. :)

 

P.S. Vėl atsiprašau, jei kartais kokių žioplų klaidelių privėliau.

P.P.S. Jau išsprendei visus kitus 12-ka uždavinių? :D

Sunkus laikotarpis buvo, visai laisvo laiko nebeturėjau :D liko tik kelios dienos iki olimpiados, reiktų susiimti :D

Taip, visus uždavinius iki šito pasidariau. Dabar bandysiu tą optimalų sprendinį sukonstruoti :D

 

Edit: puiku, padariau. Dviejų testų nepraeina dėl per ilgo vykdymo laiko, bet čia jau ne taip svarbu, ką nors sugalvosiu. Reiki kibti į kitus uždavinius, matau ten su grafais yra neblogas :D

 

Rimai, dar kartą labai ačiū :D

Redagavo Vasario 3, 2010 mantasurnieza

Sveiki,

olimpiadose ir konkursuose susimoviau, tai nebebuvo nė didelio noro programuoti :devil:

 

Šiandien peržiūrėjau nepasisekusio Kazicko informatikų forumo užduotį ir supratau kodėl tik 4 taškelius už ją tegavau :devil:

Yra žinomos dviejų sveikųjų skaičių k ir s reikšmės (1 ≤ k ≤ 10, 1 ≤ s ≤ 100). Raskite didžiausią ir 
mažiausią skaičius, kurių kiekvienas būtų sudarytas iš skirtingų skaitmenų, kiekvienas turėtų k skaitmenų ir tų 
skaitmenų suma būtų lygi s.

 

Šitas irgi man atrodo dinaminio programavimo uždavinys :devil: gal gerbiamas Rimas ar kas kitas padės man su šituo uždaviniu. Neatrodo labai sudėtingas, maždaug įsivaizduoti, bet nuo kurio galo pradėti nežinau :devil:

 

Laukiu patarimų :blush:

Sveiki,

olimpiadose ir konkursuose susimoviau, tai nebebuvo nė didelio noro programuoti :devil:

 

Šiandien peržiūrėjau nepasisekusio Kazicko informatikų forumo užduotį ir supratau kodėl tik 4 taškelius už ją tegavau :devil:

 

Šitas irgi man atrodo dinaminio programavimo uždavinys :devil: gal gerbiamas Rimas ar kas kitas padės man su šituo uždaviniu. Neatrodo labai sudėtingas, maždaug įsivaizduoti, bet nuo kurio galo pradėti nežinau :devil:

 

Laukiu patarimų :blush:

Tai kad aš pats šį uždavinį sprendžiau pačiu paprasčiausiu būdu - perrinkimu.

Greitumo dėlei perrinkinėjau ne visus skaičius, o tik tuos, kuriuose visi skaitmenys skirtingi (labai pravertė C++ funkcija next_permutation()). Maksimalų kiekį maksimalių testų programa įveikia per porą sekundžių.

Olimpiadai gal reiktų galvoti kažką gudresnio, bet Kazicko konkursui visiškai pakako ir tokio sprendimo. :devil: