Sem si tak v CADu měřil rozměry obdélníčku, a pěkně vyšla přepona 60 + sqrt(25) :)
V praxi jsou v zasade tri typy problemu.
1. Daji se resit hladovym algoritmem. Ty se poznaji tak, ze maji v sobe ukryty matroid
2. Hladovy algoristmus je resi docela dobre (treba s presnosti 10 %), ty se pak resi backtrackingem s prorezavanim s tim, ze mame od zacatku dost dobre reseni a vetsinu vetvi brzy zahodime.
3. Hladovy algoritmus je neresi ani priblizne.
Nejcastejsi je 2 s tim, ze obcas je dobre BT casove omezit (nebo zvolit jinou heuristiku zastavovani)
Jj, ta lakota je dobrá, ale jen jako heuristika. Ona vlastně přirozeně vyplyne z toho ořezání, když si sčítance řadim od největšího. Plus bych přidal ještě tu memoizaci podpřípadů a víc bych toho asi bez dalšího studia nevymyslel.
Jen tak od boku bych zkusil lakotu s backtrackingem. Worst case complexity bude prohibitive ofc, ale většina reálných zadání se tomu - tipuji - vyhne.
Hele, co jsem vyhrabal ze svejch pokusů, když jsem se začal učit Lisp:
(define (part n)
(define (part-max n m)
(cond
((<= n 0) 1)
((<= m 0) 0)
((< n m) (part-max n n))
(else (+ (part-max (- n m) m) (part-max n (- m 1))))))
(part-max n n))
Tady hledam počet všech
particí, tj. kolika způsoby můžu rozměnit, pokud bych měl mince všech celočíselnejch hodnot.
Ty partice jsou mimochodem dost důležitý v rozkladech tenzorů na "typy", potažmo v geometrii. Třeba symetrický matice odpovídaj partici 2 = 2 a antisymetrický partici 2 = 1+1.
Ale přecijen hladová úvaha k něčemu dobrá je. Stačí možnosti procházet tak, že postupně bereš jen stejný nebo čím dál menší mince, než si bral předtím. To je dost brutální ořezání. Vlastně využívám, že sčítání je komutativní, tak si můžu sčítance seřadit.
Hladově to obecně neprojde. Když budu chtít zaplatit 200 korun a budu mít jen jednu pětikorunu a mrak dvoukorun, tak tu pětikorunu nesmim použít. Fakt se to musí zkoušet.
Ano, je.
- Oproti lineární difantický rovnici je tu navíc omezení nerovnostma, kolik mincí jakýho druhu mam a samozřejmě můžu od každý použít jen nezápornej počet.
- Dynamickym programováním to jde rychle za cenu paměti. Musíš si alokovat aspoň jeden bit na každej nejmenší možnej dílek na škále od 0 do požadovaný částky. Takže kdybys měl hodně malý dílky (v extrému všechny racionální nebo reálný čísla), tak se nevejdeš. A pokud bys měl mince, jejichž násobky a součty se málo potkávaj, tak si vlastně nepomůžeš a redukuje se to na zkoušení možností, akorát s obrovskym bitovym polem navíc.
- Určitě to bude NP. Obecně musíš prostě zkoušet možnosti, umění pak spočívá v nějaký heuristice a ořezání backtracku. Mužeš si třeba pomoct memoizací podpřípadů, který už jsi prošel, např. když se podruhý jinou cestou dostaneš do situace "zbývá mi doplatit ještě 14 Kč".
Uvažuju, jak by to vypadalo, kdybych měl i určitý počet bankovek a mincí na vracení.
(Což obecně rozhodně neplatí. Např. u nás v 60 letech, pokud mne paměť nešálí, obíhaly dvoukoruny, tříkoruny i pětikoruny.)
Hladový algoritmus, bereš největší minci hodnoty menší nebo rovnou částce, která ti zbývá, dokud nemáš zaplaceno.
Funguje, pokud u mincí platí, že jejich nominální hodnoty jsou tak odstupňované, že každná vyšší hodnota je aspoň 2x vyšší než nejbližší nižší hodnota.
V programování známo jako "coin change problem" a řeší se dynamickým programováním:
https://www.codesdope.com/course/algorithms-coin-change/V nejhorším případě, jak píše arnost, můžete projít všechny kombinace, nedá se tomu dopředu vyhnout (typicky pokud budete mít mince pěkných prvočíselných hodnot :)
Jmenuje se to diofantiacka rovnice (linearni). Resi se to pomoci Euklidova algoritmu.
https://www.math.uwaterloo.ca/~wgilbert/Research/GilbertPathria.pdfjedna z metod, jak podobnym prikladum pristupovat je celocislne programovani
https://www.math.uwaterloo.ca/~wgilbert/Research/GilbertPathria.pdfO nem je dokazano, ze je NP-uplne, takze se casto clovek nevyhne prochazieni vsech kombinaci.
Já mám nejistý dojem, že jsem někde viděl důkaz, proč je to NP, ale taky je možné, že si to jen s něčím pletu :)
Co myslíš postupným dělením? Zní mi to jako projití všech permutací.
To si neuděláš klasickým postupným dělením a porovnáním s počtem mincí? (BMW tady z toho 103 nedáš ;-))
Dotaz. Mám zadání, spočívající v zadané částce a daných počtech mincí. Třeba mám zaplatit přesně 103 Kč a k dispozici mám 3x50 Kč, 2x10 Kč a 2x1 Kč. Mám zjistit, jestli tu danou částku dokážu zaplatit. Není na to nějaký známý a rychlý algoritmus?
