Matematické Fórum

brnopcman · 19. 04. 2013 14:09 — Editoval jelena (19. 04. 2013 14:51)

Ahoj, mám takový problém nevím jak vyřešit následující úkol :

Jsme v zemi, ve které se používají mince v hodnotě 1, 15, 18 a 49. Vytvořte program, který
dostane jako parametr (či v souboru) přirozené číslo a jako výstup dá číslo, kolik nejméně
potřebujeme mincí k zaplacení dané částky.
Pozor: uvědomte si, že hladový algoritmus fungující u nás (s mincemi 1,2,5,10,20,50) jdoucí
od nejvyšší hodnoty mince "dokud to jde", není v této zemi správný!
Například: částku 103 byste tímto algoritmem zaplatili jako 49+49+1+1+1+1+1 (7mincí), ale
správné řešení je 49+18+18+18 (4mince)
Více bodů dostanete, zobecníte-li program a hodnoty mincí v oné zemi budete načítat z
textového souboru.
Více bodů dostanete za efektivnější (rychleji počítající) algoritmus. Částka kterou chcete
rozdělit může být v řádech milionů.
Test pro hodnoty mincí 1,15,18,49:
Vstup (částka) Výstup (nejmenší počet mincí k zaplacení)
30 => 2
103 => 4
202 => 7
987 => 24
10000 => 208
14010 => 296
140103 => 2863
9531602 => 194526

Předem děkuji.

Jelena: upřesnění, že nejde o aktuální soutěž:

Autor skryl část textu. Zobrazit/skrýt!

JohnPeca18

↑ brnopcman:
Nevim co by byl efektivni algoritmus. Ale muj napad by byl nasledujici. Pokial $k$ je pocet druhov minci a $m_1, \dots, m_k$ su hodnoty roznych minci. Potom nech $H(n)=\sum_{i=1}^{k}H_i(n)$ je optimalna pocet minci pre cislo n. $H_i(n)$ oznacuje pocet minci $m_i$ v tejto kombinaci. A teda plati $\sum_{i=1}^{k}m_iH_i(n)=n$
Potom plati rekurzia $H(n)=1+\min_{i\in \{1,\dots, k\}}{H(n-m_i)}$ .
Teda cislo n vieme poskladat optimalne takym sposobom, ze pridame 1 mincu $m_i$ k nejakej optimalnej kombinacii $H(n-m_i)$ . Zakladom rekurzie bude $H(0)=0$ . Teraz ide o to ako najlepsie naprogramovat vypocet tejto rekurzie. Nenapada ma zatial lepsi sposob ako pocitat to od jednotky pre vsetky cisla az po n. Zaznamenavat si hodnoty a kombinacie pre vsetky cisla n. A postupne z nich vypocitavat najlepsiu kombinaciu az po n. Ked uz to mam, tak mam vsetky kombinacie pre hodnoty $\leq n$ takze dalsi vypocet nastane az ked natrafime na cislo ktore je ostre vacsie ako n.
Mozno je ale aj rychlejsi zposob ale nic ma nenapada.

Wrunx · 19. 04. 2013 20:04

Napadlo mě postupovat metodou podobnou Eratosthenovu sítu. Ale při zde uvedeném případu čísla "14010 => 296" jsem se zaseknul, protože mi program našel lepší řešení: 14010=>285*49+3*15, tj potřebuji jen 288 mincí. 8-O Asi za to může ta flaška vína tak mě prosím nekamenujte.... :-)))

Wrunx · 20. 04. 2013 21:30

Tak jsem premohl kocovinu ;-) a splodil (možná už pozdě) prográmek v Python co to řeší jinak než pomocí síta. Pokud je zájem, je ke stažení na
http://ulozto.cz/x87yX56z/uloha05-pro-matforum-py-zip
a potvrzuji že 14010 se da složit z 288 minci.

Matematické Fórum

#1 19. 04. 2013 14:09 — Editoval jelena (19. 04. 2013 14:51)

Mince

#2 19. 04. 2013 14:30 Příspěvek uživatele jelena byl skryt uživatelem jelena. Důvod: upřesnění, zda aktuální soutěž - v pořádku

#3 19. 04. 2013 14:35 — Editoval brnopcman (19. 04. 2013 14:45) Příspěvek uživatele brnopcman byl skryt uživatelem jelena. Důvod: upřesnění, zda aktuální soutěž - v pořádku

#4 19. 04. 2013 14:48 Příspěvek uživatele jelena byl skryt uživatelem jelena. Důvod: upřesnění, zda aktuální soutěž - v pořádku

#5 19. 04. 2013 15:17 — Editoval JohnPeca18 (19. 04. 2013 15:17)

Re: Mince

#6 19. 04. 2013 20:04

Re: Mince

#7 20. 04. 2013 21:30

Re: Mince

Zápatí