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