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 06. 04. 2011 23:58
dynamicke programovani
ahoj mam za ukol si promyslet jak by vypadal algoritmus na tuto ulohu:
mame 62 dni, ve kterych muzu pronajimat lod...a mam nabidky ze od 1. do 7.3. mi za to daji 5000, od 5. do 18.7 6000, od 25.7. do 8.8. treba 3000 atd...a ja chci mit za tech 62 dni co nejvic penez..
z toho co sme probrali o tomhle typu programovani to mam tedy rozlozit na nejyk podukoly a zapisovat si to nejak do tabulky...jenze ja vubec nemuzu najit to spravny rozdeleni ukolu na ty jednoduche...nevim jak do ty tabulky bude zapadat to ve kterym je to case kdyz se nejake prekryvaji...muzte mi to prosim nekdo vysvetlit?dekuju moc
Offline
#2 07. 04. 2011 22:07
- Lumikodlak
- Místo: Praha
- Příspěvky: 212
- Pozice: Programator nebo tak neco :-)
- Reputace: 19
Re: dynamicke programovani
Napada me akorat, ze je tim mysleno to, ze budes postupovat po dnech. Zacnes prvnim dnem, coz bude prvni policko tabulky, a zjistis, jestli se tam vejde nejaka nabidka. Jestli ano, vyberes tu nejvyssi. Pak pujdes na druhy den, podivas se, jestli jsou nabidky, co konci druhy den a spocitas, ktera moznost da nejvic penez. U nabidek, co jsou jen na druhy den, budes pricitat maximum pro ten jeden den, co jsi spocital uz predtim. U nabidek, co zabiraji i prvni den, budes pocitat samotnou.
Obecne - (to bych povazoval ze ten podukol) pro n-ty den projdes vsechny nabidky (vcetne zadne nabidky), co konci n-ty den. K penezum te nabidky prictes penize z tabulky pro den, ktery je hned pred zacatkem nabidky (to uz mas spocitane v predchozich krocich), protoze ty dalsi dny jsou zabrane touto nabidkou. Vyberes nabidku s nejvyssim souctem (coz muze byt i zadna nabidka) a vysledek uloziz na n-te misto do tabulky.
Takhle postupne az do tech 62.
(nejsem si ale jisty, jestli tohle je zadanim te ulohy mysleno)
Kdyztak dej vedet, jestli to pomohlo, nebo se muzes dal ptat jestli neco neni jasne :-)
Offline
#4 12. 04. 2011 23:23
Re: dynamicke programovani
jo a treba u prikladu co jsem delali tak zadani bylo najit nejdelsi spolecny retezec znaku ze dvou pusloupnoszi ta prvni napr ADFRT a druha GDTRS a vysledek je DR a do ty tabulky se to dela tak ze je axb za a se daji pismena z prvni a za b z druhe...kdyz jsou stejne a zapisuje se do prislusnych poli pod ne...jde se po radcich, kdyz se sobe rovnaji tak se zapise jedna, kdyz ne tak 0 a proste se to co uz je vlevo...nebo tak nejak se to delalo...a pak se z te tabulky nejak vycetl vysledek a presne to mame delat i v tomhle prikladu...tak porad nechapu jak udelam tu tabulku a jak vyctu vysledek..
dekuju moc
Offline
#5 13. 04. 2011 20:33
- Lumikodlak
- Místo: Praha
- Příspěvky: 212
- Pozice: Programator nebo tak neco :-)
- Reputace: 19
Re: dynamicke programovani
Napriklad mas tyhle nabidky pro 10 dni:
dny penize
a) 2-6 5000
b) 5-8 4000
c) 2-4 4500
d) 7-8 2500
e) 6-9 3000
Vysledna tabulka bude vypadat tak:
Code:
den: 1 2 3 4 5 6 7 8 9 10 max: 0 0 0 4500 4500 5000 5000 8500 8500 8500 nabidka: - - - c c a a b b b
Ziska se tak:
Nejdriv 1. den - tam se nevejde zadna nabidka, takze nic, to same pro 2. a 3.
Pak 4. den - tady muzes pouzit nabidku c), vezmes cenu nabidky, a prictes cislo max v tabulce pro den 1, protoze nabidka zacina az od 2. dne, takze dostanes 4500. To je vetsi nez predchozi (coz byla 0), takze ulozis 4500 a a nabidku c) ke dni 4.
5. den zadna nova nabidka, takze akorat kopirujes predchozi (maximum zustava stejne).
6. den muzes pouzit a), takze 5000+0 (za 1. den) je 5000, coz je vetsi nez minule maximum, takze ulozis nove maximum (a nabidku).
7. den zase nic noveho - zustava to same maximum.
8. den muzes pouzit b) a d). Pro b) vezmes 4000 a prictes 4. den, coz je 4500 takze celkem 8500. Pro d) vezmes 2500 a prictes 6.den (5000), takze celkem 7500. Minule maximum bylo 5000, takze nejvetsi je s nabidkou b) - ulozis 8500 a b).
9. den muzes pouzit e). 3000+4500 (za 5. den) je 7500, coz je ale mensi, nez minule maximum, takze zustava maximum z minuleho dne.
10. den kopiruje se devaty.
Nakonec - Vezmes 10. den, cili vysledne penize budou 8500. V tom dni je nabidka b), ta zacina 5. den, takze dal pujdes na 4. den - tam je nabidka c) - ta zacina 2. den takze pujdes na 1. den a tam uz neni zadna nabidka, takze vysledek je nabidka b) a c).
Nevim ale, jestli to mate mit zrovna takhle. Kldine se treba jeste ptej, mozna odpovim :-)
Ten druhy co jsi tu uvadel si dovedu predstavit, jak by se delal, ale nevim zas, jestli jsem spravne pochopil, zda se mi to podobne tomu prvnimu no :-)
Offline