Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

Zadatak: Money Systems

[es] :: Art of Programming :: Zadatak: Money Systems

[ Pregleda: 3070 | Odgovora: 3 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

stf

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



Profil

icon Zadatak: Money Systems15.07.2005. u 15:44 - pre 227 meseci
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.
 
Odgovor na temu

cassey
Andreja Ilic
Nis

Član broj: 57788
Poruke: 188
212.200.10.*



+1 Profil

icon Re: Zadatak: Money Systems15.07.2005. u 16:00 - pre 227 meseci
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.
 
Odgovor na temu

stf

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



Profil

icon Re: Zadatak: Money Systems17.07.2005. u 10:06 - pre 227 meseci
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.
 
Odgovor na temu

stf

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



Profil

icon Re: Zadatak: Money Systems17.07.2005. u 18:33 - pre 227 meseci
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.
 
Odgovor na temu

[es] :: Art of Programming :: Zadatak: Money Systems

[ Pregleda: 3070 | Odgovora: 3 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.