Zadatak: Money Systems

Zadatak: Money Systems 15.07.2005. u 15:44 · pre 259 meseci #1

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

Potpis

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

Re: Zadatak: Money Systems 15.07.2005. u 16:00 · pre 259 meseci #2

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...

Potpis

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

Re: Zadatak: Money Systems 17.07.2005. u 10:06 · pre 258 meseci #3

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?

Potpis

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

Re: Zadatak: Money Systems 17.07.2005. u 18:33 · pre 258 meseci #4

Našao sam na internetu algoritam za rešavanje ovog zadatka. Rešenje zahteva veoma malo koda. Zaista je DP mnogo moćan algoritam!.

Potpis

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

Srodne teme