Matematické Fórum

Peter_CSR · 03. 03. 2018 21:02

Ahoj,

riešim tu pôvodne programátorskú úlohu, ale najskôr musím pochopiť matematickému základu... chcel by som vás na začiatok poprosiť na popostrčenie na oblasti na ktoré sa mám zamerať (má problém nejaký názov?)

Pôvodná otázka znela: Si cashier v McDonald a napíš program, ktorý vráti výdavok podľa mincí, bankoviek, ktoré máš v kase a ich počtu. Čiže mám napríklad vrátiť 25 kč, v kase mám jednu 10 a dvadsať 5, vráti 10, 5,5,5. (inak, našiel som už hromadu programov, ktoré toto počítajú ale zatiaľ ani jeden čo bere ohľad na maximálny počet mincí a bankoviek...)

Moja otázka je:

Hľadám názov matematického problému, ktorý pojednáva o spôsobe rozdelenia prirodzeného čísla na sčítance, kde mám zadané ich typ a ich maximálne sa opakujúci počet. Napríklad, mám číslo $1000 = m$ a mám (napr.) čísla $S = [1,3,5,25,66,97,123]$ a podľa ich indexu príslušné maximálne koeficienty $K_{max} = [10,33,12,6,3,55,2]$ . Nájdi algoritmus ktorý nájde riešenie $m = \sum_{_{}}^{} k_{i}s_{i}$ , kde $s_{i} \in S$ a $k_{i} <= MAX(k_{i})$ (čiže len pre istotu: to, čo mám v množine K nie sú čísla, ktoré idem použiť ale maximálne čísla, ktoré podľa indexu môžem vziať).

Snáď takýto zmysel dáva zápis.

Nehľadám riešenie (aj keď sa iste neurazím, ak mi ho napíšete :D :D :D ) ale radu, kde by som mal začať hľadať....

Ďakujem :)

MichalAld · 03. 03. 2018 22:30

Není to náhodou PROBLÉM BATOHU ?

Peter_CSR · 04. 03. 2018 18:32

podobá sa to, ale nie je to asi ono. Ja hlavne potrebujem presnú hodnotu v baťôžku, to je pointa môjho problému...

ah, common, páni, sťažujete si že vám tu ľudia vypisujú otázky typu "mám tu základoškolský príklad, neviem s tým pohnúť. Vypočítajte mi", ale keď sa tu objaví skutočný a kreatívny problém, ticho na mýtine! :P

MichalAld · 04. 03. 2018 18:48

No to víš, když sám prohlásíš, že nejsložitější věc, co si dokážeš zapamatovat, má 3 znaky, a z toho jeden je rovnítko (a druhé dva asi ty mezery po jeho stranách), tak co se divíš ?

Pokud je to skutečně ekvivalent problému batohu, tak je to NP-úplný problém, a žádný (efektivní) algoritmus na to stejně nevymyslíš - jiný než vyzkoušet všechny varianty.

Pokud jde o vracení peněz, je to mnohem jednodušší, protože peníze mají pěkné kulaté hodnoty. Takže stačí, když začneš vracet ty největší bankovky (dokud to jde, nebo dokud je máš), pak přejdeš k nižší, pak zase k nižší atd...až skončíš u korun. U bankove se ti nestane, že by to "nevyšlo". U obecných čísel se ti to stát může.

Peter_CSR · 04. 03. 2018 18:57

Skutočne? a čo ak máš nekonečno vela 5 a 2 a máš vrátiť 8 kč. čo povieš počítaču? Alebo zostatok je 508 a ty máš 500-vky, 5-ky a 2-ky. čo teraz??

A čo keď máš päťky a desiatky a chceš vrátiť 12?

MichalAld

No pak se to asi začíná podobat tomu NP problému. Což je obecně vždycky nepříjemné.

Každopádně ten stav, kdy budu mít nekonečně vela pětikorun (nebo se tomu budu aspoň blížit) bych docela rád zažil...

Peter_CSR · 04. 03. 2018 19:22

dávaním nepremyslených odpovedí sa tak určite nestane :P

:D :D :D

Matematické Fórum

#1 03. 03. 2018 21:02

Vypočítavý cashier a rozdelenie prirodzeného čísla na súčet sčítancov

#2 03. 03. 2018 22:30

Re: Vypočítavý cashier a rozdelenie prirodzeného čísla na súčet sčítancov

#3 03. 03. 2018 22:44 — Editoval Peter_CSR (04. 03. 2018 02:24) Příspěvek uživatele Peter_CSR byl skryt uživatelem Peter_CSR.

#4 04. 03. 2018 18:32

Re: Vypočítavý cashier a rozdelenie prirodzeného čísla na súčet sčítancov

#5 04. 03. 2018 18:48

Re: Vypočítavý cashier a rozdelenie prirodzeného čísla na súčet sčítancov

#6 04. 03. 2018 18:57

Re: Vypočítavý cashier a rozdelenie prirodzeného čísla na súčet sčítancov

#7 04. 03. 2018 19:03 — Editoval MichalAld (04. 03. 2018 19:07)

Re: Vypočítavý cashier a rozdelenie prirodzeného čísla na súčet sčítancov

#8 04. 03. 2018 19:22

Re: Vypočítavý cashier a rozdelenie prirodzeného čísla na súčet sčítancov

Zápatí