[ stf @ 15.07.2005. 15:44 ] @
Ovo je zadatak za koji sam siguran da se, zbog vremenskog ograničenja, mora raditi dinamičkim programiranjem. Dosad nijedan zadatak sa USACO-a (ovaj je sa USACO-a) ili bilo koji drugi nisam rešavao primenom DP-a (doduše možda jesam, a da nisam toga ni svestan). Dakle, zna li neko algoritam za rešavanje ovoga:

Zadatak: Money Systems

Data je određena novčana vrednost M. Date su novčanice datog novčanog sistema (prirodni brojevi). Na koliko načina se novčana vrednost M, može dobiti korišćenjem tih novčanica?

Ulaz:
U prvom redu ulaza su brojevi N i M, gde je N broj novčanica (1 <= N <= 25), a M novčana vrednost koju treba dobiti (1 <= M <= 10000). U drugom redu se nalazi N prirodnih brojeva odvojrnih razmakom.

Izlaz:
U jednom redu treba odštampati traženi broj kombinacija.

Primer:

Ulaz:
3 10
1 2 5

Izlaz:
10
[ cassey @ 15.07.2005. 16:00 ] @
Da, zadatak se radi dinamickim programiranjem i ovo je bas primer problema ranca. O njegovom resavanju pogledaju u TOP TEMI. Znaci stim sto ces ovde da uzmes da je njihova zapremina jednaka njihovoj vrednosti i da punis ranac zapremine M iu nekom nizu d pamtis broj nacina...
[ stf @ 17.07.2005. 10:06 ] @
Znači, za problem ranca kod je ovakav:

Code:

for j:=1 to n do begin
  for i:=1 to m do
    if i-size(j)>=0 then 
     if cost(i)<(cost(i-size(j)+val(j)) then begin
      cost(i):=cost(i-size(j))+val(j);
      best(i):=j;
     end;
end;


To je bar lako razumljivo. Kako sad na osnovu ovoga glasi glavni ciklus za rešenje ovog zadatka?
[ stf @ 17.07.2005. 18:33 ] @
Našao sam na internetu algoritam za rešavanje ovog zadatka. Rešenje zahteva veoma malo koda. Zaista je DP mnogo moćan algoritam!.