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ívny 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.