Matematické Fórum
Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.
Nástěnka
❗22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
❗04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
❗23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.
Nejste přihlášen(a). Přihlásit
#1 20. 04. 2011 23:55
lodicky-pascal
ahoj,
mame si rozmyslet ulohu s lodickama:
mame 2 lodicky a N dni na jejich pujcovani a nabidky jsou od, do a za kolik...my chceme vydleat co nejvic takze to pomoci dynamickyho programovani mame vyresit...ma to bejt pomoci dvourozmerneho pole coz nechapu...potrebuju jen vysvetlit ten algoritmus
kdyz mam 1 lodicku tak je algoritmus jasny:
napisu si dny od 1 az do N a kouknu ktere nabudky konci dany den a zapisu si je, kdyz se nabidky prekryvaji, podivam se ktera mi da vic a zapisu si ji atd...kdyz tam mam tu druhou tak tenhle postup nefunguje muzete mi nekdo vysvetlit ten algoritmus u dvou lodicek prosim?
dekuju moc
Offline
#2 21. 04. 2011 18:30
Re: lodicky-pascal
no mozna je to blbost... ale prijde mi, ze ac urcite ne nejrychlejsi, tak by mohlo stacit urcit ty, kde se prekryvaji MAX. dve nabidky a ty vyradit ze seznamu. Ty jsou jasne a tim padem je muzeme lodickam vcelku nahodne priradit.
Problemem jsou ty, kde se nabidky vcelku ruzne prekryvaji a tam by se mohla dat zvolit metoda vsech permutaci... tzn. vytvoris KAZDOU moznou kombinaci pro dve lodicky (tzn. vlastne dve kombinace) Vzdy si budes pamatovat jen tu nejlepsi (ve chvili, kdy najdes lepsi, nejlepsi prepises na ni) timto se urcite dostanes k nejlepsi moznosti... ale rychlost tohoto algoritmu neni zrovna velka :(
Offline
#4 11. 05. 2011 20:16
- OiBobik
- Moderátor
- Místo: Brno/Praha
- Příspěvky: 1013
- Škola: MFF UK Mat. struktury
- Pozice: student
- Reputace: 82
Re: lodicky-pascal
↑ hessyk:
Pro jednu loďku ti tedy stačí jednorozměrné pole. Zkus pro 2 loďky udělat dvojrozměrnou analogii (a čemu by pak mohlo odpovídat číslo v matici Sij, když Si v jednorozměrném poli u jedné loďky odpovídalo optimu pro jednu loďku do i-tého dne?)
"The first rule of Tautology Club is the first rule of Tautology Club." [xkcd]
Offline