Pomoc s blbým programem – C / C++ – Fórum – Programujte.com

26. Je dáno přirozené číslo N,N<=100. Vypište všechny možné výplaty N korun pomocí platidel s hodnotami 1,2,5,10,20, a 50 korun. Prosím o rady a tak jak to řešit děkuji

Myslím, že to bude něco na ten způsob, že zkusím všechny kombinace těch mincí a budu koukat, jestli jejich součet dá N. Tedy pro každou hodnotu první mince zkusím každou hodnotu druhé mince a pro každou kombinaci těhle dvou zkusím každou hodnotu třetí mince a tak dál:

1 1 1
1 1 2
1 1 5
1 1 10
1 1 20
1 1 50
1 2 1
1 2 2
1 2 5
1 2 10
1 2 20
1 2 50
2 1 1
2 1 2
...

samozřejmě těch mincí bude potřeba víc než jen 3.

Asi by to šlo udělat i optimálněji, možná dokonce v polynomiálním čase s dynamickým programováním, ale tím se asi nemusíš zatěžovat :)

To Quiark : ahoj a mohl bys teda prosím sem dát zdroják??? děkuji

dal ti navrh jak by to resil... zdrojak si muzes laskave udelat sam..

jinak ja bych to asi resil trochu opacne... nejdriv bych zjistil jaky mince tam jdou nasazet nejvetsi...
a pak jednotlive mince rozkladal... na mensi a mensi... stacilo by pak menit jen pocty jednotlivejch minci...
mohlo by to mit i reseni v "umernem" case :D tj necekat 10000let na vysledek :D

Pokud jde jen o počet těch kombinací, pak to lze převést na násobení spousty polynomů.

P1 = 1 + x^1 + x^2 + x^3 + ... + x^N
P2 = 1 + x^2 + x^4 + x^6 + x^8 + ... + x^N
P5 = 1 + x^5 + x^10 + x^15 + x^20 + ... + x^N
P10 = 1 + x^10 + x^20 + x^30 + ... + x^N
P20 = 1 + x^20 + x^40 + x^60 + x^80 + x^N
P50 = 1 + x^50 + x^N

PT = P1*P2*P5*P10*P20*P50

Tyhlety polynomy vynásobíš, a podíváš se na KOEFICIENT u x^N a tento koeficient je počet kombinací.
Pokud máš konstantní počet těch hodnot, pak to lze řešit v čase O(n log n), protože polynomy dokážeš násobit v čase O(n log n) pomocí FFT.

Jinak polynomiální algoritmus na VÝPIS jednoduše existovat nemůže, protože těch kombinací je exponenciálně mnoho.

ahojte neviem naco spekulujete s nejakymi polynomami. Najlepsie najrychlejsie a najjednoduchsie riesenie je to co navrhol KIIV.
a to spocitavat najvacsie mince az pokial nebude hodnota vacsia alebo rovna pozadovanemu vysledku ak je uz vacsia tak odcitat najvaciu a zasa tym istym sposobom pricitavat mensiu mincu a dokola az po najmensiu pokial sa to nebude rovnat:)

To scd : problem bude ze to mozna nenajde uplne vsechny moznosti... teda aspon letmou uvahou si to myslim... muselo by si to pamatovat predchozi kroky a rozkladat to ruzne

ups sory to som prehliadol ale jednu aspon najde:D

To KIIV : Proč?
50 50
50 20 20 10
50 20 20 5 5
50 20 20 5 2 2 1
50 20 20 5 2 1 1 1

ale treba:
50 20
20 20 20 10
ale to co by se uz neobjevilo 50 10 10 a obdobne dalsi a dalsi kombinace

ten postup rozkladania nenajde riesenie 2 2 2 2 2 2 2 ... myslim :)
a ak ho najde tak nenajde tych 50 10 10 ...

tusim by som na to isiel rekurzivne, spustit vypis pre kazde platidlo pricom by sa v kazdej rekurzii spustili dalsie s kazdym a skoncili by az by bol sucet viac ako N.

To mephi : no mozna by to slo nejakym zasobnikem...

To scd : Pokud jsi můj komentář nepochopil, tak ho nekomentuj.

no kdyz nad tim premejslim tak by se to dalo udelat jako DFS nebo BFS... jen by se jelo az do uplneho konce :)