[es] - Zadatak: Money Systems

stf
Stefan Mišković
Čačak

Član broj: 51276
Poruke: 65
*.181.EUnet.yu.

Profil

^{15.07.2005. u 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

If you don't live for something, you will die for nothing.

^{15.07.2005. u 15:44}

cassey
Andreja Ilic
Nis

Član broj: 57788
Poruke: 187
212.200.10.*

Profil

Re: Zadatak: Money Systems

^{15.07.2005. u 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...

Math is like love. A simple idea but it can get complicated.

^{15.07.2005. u 16:00}

stf
Stefan Mišković
Čačak

Član broj: 51276
Poruke: 65
*.157.EUnet.yu.

Profil

Re: Zadatak: Money Systems

^{17.07.2005. u 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?

If you don't live for something, you will die for nothing.

^{17.07.2005. u 10:06}

stf
Stefan Mišković
Čačak

Član broj: 51276
Poruke: 65
*.168.EUnet.yu.

Profil

Re: Zadatak: Money Systems

^{17.07.2005. u 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!.

If you don't live for something, you will die for nothing.

^{17.07.2005. u 18:33}