Cvičenia: 7. týždeň

Ciele cvičení:

• rozumieť princípu techniky "dynamické programovanie" na príklade niektorých úloh využívajúcich túto techniku
  • vedieť charakterizovať problém
  • vedieť skonštruovať riešenie problému z riešení "menších" problémov
  • vedieť ako aplikovaním prístupu zdola-nahor (ako náhrada memoizácie) vypočítať požadované riešenie
  • vedieť nájsť a interpretovať riešenie

Krátka sumarizácia

"Objavenie" dynamického programovania (od rozdeľuj a panuj, cez rekurzívnu implementáciu s memoizáciou, po dynamické programovanie):

• nájdenie rekurzívneho vzorca, ktoré charakterizuje optimálne riešenie pomocou optimálnych riešení menších problémov (pre každú úlohu jedinečný problém)
• priamy prepis rekurzívneho vzorca do rekurzívneho algoritmu vedie k neefektívnemu riešeniu
  • Nakreslite strom výpočtu pre Fibonacciho číslo Fib(5). Všimnite si, že strom výpočtu Fib(3) sa nachádza v strome aj ako podproblém pre Fib(5), aj ako podproblém pre Fib(4).
  • Riešenie: neopakovať výpočet rovnakej hodnoty
    • Pri každom výpočte si každý výsledok uložíme v poli výsledkov
    • Ak vznikne volanie metódy na výpočet, pozrieme sa najprv do poľa výsledkov, či už náhodou výsledok nemáme vypočítaný a uložený
• namiesto ukladania medzivýsledkov sa rovno systematicky vypočíta pole s medzivýsledkami
  • Pri nerekurzívnom výpočte Fibonacciho čísla sa systematicky vyplní pole - vždy ako súčet 2 predchádzajúcich prvkov poľa

Nájdite riešenia nasledujúcich úloh využijúc techniku "dynamické programovanie", riešenia implementujte.

Najdlhšia vybraná rastúca podpostupnosť

Daná je postupnosť N čísel: P[0], P[1], ..., P[N-1]. Nájdite takú podpostupnosť (nemusí byť súvislá), aby všetky hodnoty vybranej podpostupnosti tvorili rastúcu postupnosť hodnôt a vybraná postupnosť bola najdlhšia možná.

• môžete využiť "bonusové" slajdy k 7. prednáške

Problém zaplatenia nákupu

V peňaženke máme celkom N platidiel (mincí resp. bankoviek) s hodnotami P[0], P[1], ..., P[N-1]. Predpokladajme, že hodnoty platidiel sú celé čísla (pre náročnejších: ako by sme riešili úlohu, keby sme pripustili aj halierové, resp. centové mince?). Cena nákupu je C (opäť celé číslo).

Otázka: vieme platidlami v peňaženke zaplatiť za nákup tak, aby nám nebol vrátený žiaden výdavok, t.j. vieme z platidiel v peňaženke presne vyskladať sumu C? V prípade kladnej odpovede vypíšte, aké platidlá treba použiť.

Aplikácia: Vedeli by ste podobným prístupom riešiť úlohu o spravodlivom rozdelení lupu medzi dvoch zlodejov?

Záhradkárska úloha

Záhrada, ktorá má tvar obdĺžnika, sa skladá z M x N políčok. Na každom políčku je jabloň s hojnou úrodou jabĺk. Nech na políčku [x, y] je úroda jablone U[x, y]. Vstup do záhrady je na políčku [0, 0] a výstup na políčku [M-1, N-1]. Aby návštevníci záhradu okamžite nevyplienili, rozhodol sa správca zaviesť nasledovné pravidlá pre pohyb návštevníkov:

• Návštevník môže z políčka [x, y] prejsť len na políčko [x, y+1] a [x+1, y]:
  • Zaujímavé pozorovanie, ktoré ale nesúvisí s riešením úlohy: vďaka týmto pravidlám každý návštevník prejde vždy tou najkratšou možnou cestou a tým strávi v záhrade minimálny možný čas (prechody po uhlopriečke neuvažujeme)
• Návštevník si môže zobrať jablká z jabloní na tých políčkach, ktorými prejde počas svojej cesty záhradou

Nájdite takú cestu záhradou, pri ktorej vyzbierate maximálny možný počet jabĺk.

Nápoveda:

• Najprv skúsme vypočítať, koľko najviac jabĺk vieme nazbierať.
• Označme si výrazom Z[x, y] maximálny možný počet jabĺk, ktoré vieme vyzbierať pri ceste z políčka [0, 0] do políčka [x, y].
• Zrejme maximálny počet jabĺk, ktoré vieme celkovo pri prechode záhradou nazbierať je rovný Z[M-1, N-1].
• Dôležité pozorovanie: do políčka [x, y] vieme povolenými cestami prísť len z 2 možných susedných políčok

Najdlhšia spoločná podpostupnosť

Dané sú 2 reťazce. Nájdite najdlhšiu podpostupnosť, ktorá je vybranou podpostupnosťou oboch reťazcov.

• môžete využiť "bonusové" slajdy k 7. prednáške

Problém batoha (pre pokročilých)

• Navrhnite a implementujte algoritmus využivajúci dynamické programovanie pre problém batoha, ktorý bol odprednášaný na prednáške o backtracku.

Na trati Bratislava Košice a späť

Nie každý má vlaky zadarmo. Vtedy tu mame alternatívy, ktoré poskytuje moderná zdieľaná ekonomika ako "shareovane auta". Ľudia, ktorí majú v aute miesto pre ďalšieho pasažiera a idú autom medzi dvojicou miest zadajú túto informáciu na stránku spolu s cenou. Takto vieme ušetriť napríklad na trase Košice - Bratislava. Ale ak túto trasu poskladáme z kratších trás tak možno ušetrime ešte viac. Zoberme trasu Košice - Bratislava zapísanú ako postupnosť okresných miest: KE-PO-LE-PP-LM-ZA-TN-NM-PH-TT-BA.V okresných mestách máme cenové ponuky na prepravu medzi nimi:

Za akú najnižšiu cenu sa vieme dopraviť do Bratislavy?

• Navrhnite a implementujte algoritmus využívajúci dynamické programovanie, ktorý nájde cenu najlacnejšej cesty.
• Upravte algoritmus nech vypíše túto cestu.
• Upravte algoritmus aby ak má viacero ciest rovnakú cenu aby vybral tú, kde je menej prestupov.

https://www.youtube.com/watch?v=zInm6RvxAoU

Poznámky spracované Matejom Perejdom (verifikoval Marián Opiela):

• Najdlhšia vybraná rastúca podpostupnosť
• Problém zaplatenia nákupu