Dynamicke programovanie - maximalizacia ceny

chcela by som požiadať o pomoc s algoritmom na dynamické programovanie. Poprade veľmi dynamickému programovaniu nerozumiem a v tom bude asi ten problém

Úloha znie takto : Mám loď a mám zadaný začiatok a cieľ plavby. A mam presne zadaný počet rôznych žiadostí o plavbu loďou. Pričom jedna žiadosť o plavbu tvori trojicu (odkiaľ, kam , cena). Odkiaľ a kam sú presne dané zastávky na ceste (sú dané napríklad číslami alebo slovami). Na danej zástavke môže nastúpiť na loď nejaká skupinka pasažierov (ich počet je irelevantný), pričom za to zaplatia nejakú cenu. Kým je na lodi jedna skupinka pasažierov nemôže tam nastúpiť iná. Úlohou je dosiahnuť čo najväčší zisk.

Príklad vstupu :
-plavba c.1 : od 1 do 4 , cena : 20
-plavba c.2 : od 2 do 5 , cena : 40
-plavba c.3 : od 4 do 6 , cena : 5
atď.

Príklad výsledku : 40 - maximálna cena , to aké požiadavky o plavbu som akceptovala ma nezaujíma.

Ja som sa snažila riešiť ako klasický problém batoha. Môj problém ale je že sa jazdy môžu navzájom prekrývať a to ja nedokážem zakomponovať do algoritmu.
Môj návrh algoritmu :
1. začnem na začiatku na 1. zástavke je moja maximálna dosiahnutá cena 0. Následne mam na 1. zástavke 2 možnosti
1. na zástavke nikto nie - moja maximálna cena zostane rovnaká a idem na ďalšiu zastávku v poradí.
2. niekto tam je , a chce nastúpiť to akceptujem a jeho cenu pripočítam k maximálnej , zároveň kým daný pasažieri nevystúpia nemôžem prijať na paluby nikoho ďalšieho , teda ďalších pasažierov zháňam až na zastávke kde momentálny pasažieri vystúpili.

A tu som sa zasekla. Na 1. zástavke totiž môže začínať viac jázd a ja neviem ktorú vybrať? Ak totiž vyberiem tu najdrahšiu (najlepšiu) nemusí to nutne viesť k najoptimálnejšiemu riešeniu. Rozmýšľala som že môžem vybrať všetky jazdy a spočítať cenu pre každú z nich ale to by sa mi vetvilo na každej zástavke , kde je viac požiadaviek.
Tiež neviem ako do algoritmu zakomponovať to ak na zástavke niekto je ale ja sa rozhodnem ho neakceptovať , pretože by to tak mohlo viesť k lepšiemu riešeniu. (o zástavku ďalej by boli pasažieri kt. by boli ochotný zaplatiť za jazdu obrovskú sumu)

chápem že toto by malo riešiť dynamické programovanie a ja som si dynamickom prečítala veľa teórie ale nejak to nedokážem aplikovať na algoritmus. Budem veľmi vďačná za akúkoľvek radu.

Zdravim, vyzera to ako zadanie zo skoly,

skus si pozrieť algoritmu cesty maximálnej priepustnosti

kedže to ma byt dynamicke programovanie tak by si mohla pozrieť Bellmanov princip optimality,

popripadne metoda vetiev a hranic (Kolesarov algoritmus), ale tymto si niesom celkom isty, ako by sa riešilo to že nemožeš zobrať nikoho kym je niekto na lodi.

A to ako si to riešila ty, by sa dalo spravit napr. tak že spraviš jednu cestu lodou (stale vyberieš bud najdrahšiu alebo prvu v poradi cestu) a potom backtrackingom by si sa vraciala o jeden krok zpet a skúšala novú kombináciu napr.

dostat sa z 1 do 8

1.krok (napr. najdrahšie cesty)
1 -> 3 -> 5 -> 8
2.krok (kedže 8 je cieľova tu musíš ponechať, ak by neexistovala ina cesta do 8 ako z 5 tak aj tu ponecháš)
1 -> 3 -> 7 -> 8
3.krok
1 -> 3 -> 6 -> 8
4.krok
1-> 4 -> 5 ->8

atd...

chapem spravne, ze lod sa plavi od najmensich zastavok k najvacsim, zastavky su celociselne (o tomto nikde v zadani nepises == pises iba ze je zadany start a ciel), a cielom je niekde po jej ceste zarobit na "stoparoch"?

jednoduchy pohlad na ulohu by bol: idem po zastavkach, ak na nejakej zastavke je nejaky stopar, mam 2 moznosti: zobrat ho, alebo nezobrat. Dynamicke programovanie je vhodne, ked si problem vies vyjadrit rekurentne (ako sadu problemov, ktore vies riesit jeden pomocou druheho, druhy pomocou tretieho, ..., posledny mas vyrieseny). Tento problem sa da vyjadrit takto: Ak si pre zastavku K oznacim V[K] ako najlepsi mozny zarobok od tej zastavky dalej, tak potom ak na zastavke je stopar, ktory je ochotny zaplatit C za prenos na zastavku L, tak potom V[K] = max(C + V[L], V[K+1])..., ked N je ciel mojej plavby, tak logicky V[N] = 0., toto uvedomenie staci na to, aby som zostrojil rekurzivny algoritmus na vyriesenie problemu... Ako riesit pripady, ze na jednej zastavke je viacero stoparov? jednoducho, proste mam viacero moznych cien a destinacii, V[K] = max(C1 + V[L1], C2 + V[L2]... , V[K+1])

ak to chcem bez rekurzie, tak mozem pole budovat "od konca": oznacim si V[N] = 0. Zoradim si moznych pasazierov podla zaciatocneho policka od konca po zaciatok a postupne upravujem pole V podla rovnic....

Precitat vela teorie je na nic, ked ju nevies aplikovat. Sposobi to akurat to, ze v takejto jednoduchej ulohe budes vidiet prilis komplikovane veci, lebo tie pojmy mas ulozene v hlave a nevies presne co znamenaju lebo si ich nikdy nevidela v praxi. Na riesenie takejto ulohy netreba poznat slova Bellmanov princip optimality (prvy krat to pocujem), Kolesarov algoritmus (co to je? ani google mi k tomu nevie nic povedat), problem batoha a podobne...,