Mars

Imam problem oko zadatka Mars. Znam da treba da se resi dinamicki, ali ja to ne znam. Citao sam clanak na TC ali i dalje ne razumem, tako da ne mogu da resim zadatak sve dok ne pocne skola i dok mi profesor ne objasni DP. Jel moze neko da pogleda moj kod i da me uputi kako da resim dinamicki. http://pastebin.com/f1a3432cf

Ja sam prvo sortirao velicine novcica, pa sam krenuo od najvecjeg i dodavao na neku sumu sve dok je ona manja od zadate. Ako novcic moze da se doda na sumu onda pamtim njegov znak, i na kraju ispisem koje sam novcice dodao.

Ako učiš dinamičko, najbolje ti je da prvo rješiš zadatak z-bankar ;)
Ako za njega trebaš pomoć lako ću ti pojasniti...

Pogledao sam Z-Bankar ali mi se javlja isti problem. Ne mogu nikako da dobijem ideju kako da resim dinamicki. Meni se javlja problem ako treba da preskoci neki sabirak koji moze da iskoristi. Jel mozes da mi pojasnis taj osnovni primer DP-a? :)

Evo sad cu.

Imaš niz dp[ ] .
U njega ćemo pamtiti sa koliko najmanje
novčanica možemo platiti iznos od i novaca.

Pogledajmo test primjer uz zadatak.

0 novaca možemo platiti u 0 novčanica. dp[0] = 0

1 možemo platiti sa novčanicom od 1 ( dp[1] = 1 )
Ne možemo platiti sa novčanicom od 3 jer je > 1 .

2 možemo platiti sa onliko koliko smo platili dp[1] + još 1 novčanica od 1.
dp[2] = dp[1] + 1
Ne možemo platiti sa novčanicom od 3 jer je > 2 .

3 možemo platiti na 2 načina.
1. Možemo platiti sa 1 novčanicom od 3 ( dp[3] = dp[3-3] + 1 )
2. Možemo platiti sa 3 novčanice od 1 ( dp[3] = dp[3-1] + 1 )

4:

dp[4] = dp[4-3]+1
dp[4] = dp[4-1]+1

5:
dp[5] = dp[5-3]+1
dp[5] = dp[5-1]+1

...

20:

dp[20] = dp[20-3]+1
dp[20] = dp[20-1]+1

I sad samo tako nastaviš i to možeš rješiti u O ( n*k ).
To se zove dinamičko programiranje jer rješavamo manje
potprobleme da bismo rješili glavni ( dp[20] )

Ako ti što nije jasno, pitaj.

Ok, hvala na objašnjenju. Sad ću da probam da napišem kod pa ću da javim dal sam uspeo. :)

Koliko sam razumeo, trebam da napišem rekurzivnu funkciju. Da li sam u pravu?

, ili treba bez funkcije?

Ja sam napisao kod ali ne radi. Izbacuje EXITCODE 201. Gde sam pogresio. Mislim da sam lepo implementirao tvoju ideju.

Program ZBankar;
Var i, j, n, k, t, min:LongInt;
dp, dpp, x:Array [0..100] Of LongInt;
Begin
Read(n,k);
For i:=1 To n Do Read(x[i]);
For i:=1 To k Do
Begin
t:=0;
j:=1;
While ( x[j] <= i ) Do
Begin
t:=t + 1;
dpp[t]:=dp[i-x[j]] + 1;
j:=j + 1;
End;
min:=dpp[1];
For j:=1 To t Do If ( dpp[j] < min ) Then min:=dpp[j];
dp[i]:=min;
End;
Writeln(dp[k]);
End.

Zašto ne bi napravio petlju u petlji i provjerio
za svaku novčanicu j , nešto tipa:

if ( novcanica[j]<= i ) then
dp[i] = min ( dp[ i-novcanica[j] ]+1, dp[i] )

To sam uradio ali sada izbacuje EXIT CODE 202. Pustio sam dve for petlje, i ide od 1 to k , a j ide o 1 do n. Onda pitam ako je novcanica[j] <= i onda je dp[i] = min ( dp [ i - novcanica[j] ] + 1 , dp[ i ] ), i na kraju ispišem dp[k].

Daj stavi kod negdje. :)

Program ZBankar;
Var i, j, n, k:LongInt;
dp, x:Array [0..100] Of LongInt;
Procedure QSort (l, d:Integer);
Var pivot, i, j, Tmp:LongInt;
Begin
pivot:=x[ ( l + d ) div 2 ];
i:=l;
j:=d;
While ( i <= j ) Do
Begin
While ( x[i] > pivot ) Do i:=i + 1;
While ( x[i] < pivot ) Do j:=j - 1;
If ( i <= j ) Then
Begin
Tmp:=x[i]; x[i]:=x[j]; x[j]:=Tmp;
i:=i + 1;
j:=j - 1;
End;
End;
QSort ( l, j );
QSort ( i, d );
End;
Begin
ReadLn(n,k);
For i:=1 To n Do
Begin
ReadLn(x[i]);
dp[i]:=maxint;
End;
QSort(1,n);
For i:=1 To k Do
For j:=1 To n Do
If ( x[j] <= i ) Then
If ( dp[i - x[j]] + 1 <= dp[i] ) Then dp[i]:=dp[i - x[j]] + 1;
WriteLn(dp[k]);
End.

// Stavio sam da je dp[i] = maxint da bi mogao da nadjem minimum.

Ispravka -> Umesto For i:=1 To n Do dp[i]:=MaxInt stavio sam For i:=1 To k Do dp[i]:=MaxInt

Uspeo sam konacno! :) Hvala puno na pomocji, nije bio problem u dp-u nego u QSort-u, pa sam ga izbacio. http://www.z-trening.com/new/www/html/submit.php?submit=7100012533&subm_code=1