Toto je úloha kde máme sestrojit BVS, pro který známe pravděpodobnosti dotazů na jednotlivé klíče. Chceme minimalizovat očekávaný počet operací, kdy nalezení klíče $k$ v hloubce $h_k$ vyžaduje $h_k+1$ operací. Pokud je pravděpodobnost dotazu na klíč $k$ rovna $p_k$, celková cena umístění klíče $k$ do hloubky $h_k$ bude $p_k(h_k + 1)$. Minimalizujeme součet přes všech $n$ klíčů.

Podobně jako při závorkování, optimální strom o $n$ uzlech lze vidět jako kořen a 2 optimální podstromy v levé a pravé větvi. Toto je naše “optimal substructure”. Když budeme hledat optimální strom o $n$ uzlech tak, že budeme zkoušet každý z $n$ uzlů jako kořen, budeme využívat stejné podstromy vícekrát - “overlapping subproblems”. Cenu stromu vypočteme vždy jako součet pravděpodobností výskytu všech uzlů + ceny obou podstromů.

Složitost bude také $\Theta(n^3)$, výpočet je podobný výpočtu závorkování.

V této úloze máme 2 řetězce $A,B$ délek $m$ a $n$, a hledáme nejdelší podposloupnost (opět ne nutně navazující) která se vyskytuje zároveň v obou řetězcích.

Když známe nejdelší společnou podposloupnost pro kratší řetězce, můžeme toho využít pro optimální řešení pro řetězce se znakem navíc. Celé se to provádí tak, že vyplňujeme 2D pole $m \times n$, kde na doplňujeme čísla podle předpisu:

$l[i, j] = \begin{cases} 0 & \mathrm{pokud} \ i = 0 \lor j = 0 \\ l[i-1, j-1] + 1 & \mathrm{pokud} \ i > 0 \land j > 0 \land A[i] = B[j] \\ \max(l[i-1, j], l[i, j-1])& \mathrm{pokud} \ i > 0 \land j > 0 \land A[i] \ne B[j] \\ \end{cases}$

Toto je pak problém s tabelací, podobný těm, co jsme řešili na minulých cvičeních.

Podobný proces je používaný pro výpočet Hammingovy, či Levenshteinovy vzdálenosti dvou řetězců.

Složitost bude $\Theta(m \cdot n)$, protože vyplňujeme tabulku o dimenzích $m \times n$.

Problém batohy (knapsack problem) je klasický NP-těžký problém. Máme batoh s kapacitou $C$ a $n$ předmětů, kde každý předmět $i$ má váhu/velikost $c_i$ a cenu/hodnotu (value) $v_i$. Chceme maximalizovat hodnotu předmětů tak, aby předměty které zvolíme nepřeplnily batoh, tedy součet jejich vah byl menší než kapacita $C$.

Uvažují se 2 varianty, 0/1 knapsack znamená, že každý předmět máme jen jeden a rozhodujeme zda ho vzít, či nevzít (0/1). Neomezená varianta pak znamená, že každý předmět můžeme vzít kolikrát chceme. Obě varianty řešíme tak, že uvažujeme optimální řešení pro batoh s menší kapacitou a do nich zkoušíme přidat další předměty.

Pro 0/1 knapsack pak vyplňujeme tabulku kde řádky znamenají přidání konkrétního předmětu a sloupce jsou změny v kapacitě. Do tabulky pak zapisujeme maximální hodnotu kterou můžeme dostat s batohem dané kapacity a s danými předměty.

$h(i, j) = \begin{cases} 0 & \mathrm{pokud} \ i = 0 \lor j = 0 \\ \max(h(i-1, j), h(i-1, j-c_i) + v_i) & \mathrm{jinak} \end{cases}$

Knapsack je tedy převoditelný na problém nejdelší cesty v DAGu či tabelaci, což jsme již řešili na minulých cvičeních.

Řešení neomezeného i 0/1 knapsacku má složitost $\Theta(C \cdot n)$, protože vyplňujeme tabulku o dimenzích $C \times n$, či procházíme DAG s $\Theta(C \cdot n)$ hranami.

Řešená úloha 1: Určete, jak bude vypadat optimální BVS, když jej vybudujeme pro 7 klíčů s frekvencemi:

Řešená úloha 2: Najděte nejdelší společnou podposloupnost dvojice řetězců:

Řešená úloha 3: Řešte neomezenou variantu úlohy batohu pro kapacitu 10 a tři předměty, jejichž váhy jsou postupně 1, 3, 6 a ceny jsou ve stejném pořadí předmětů 11, 33, 65.

Jaká bude maximální cena předmětů v batohu?

Jaké bude řešení pro 0/1 knapsack pro stejné předměty a kapacitu 7?

⭐ Úloha 4: Pravděpodobnost dotazu na jednotlivé klíče v obou daných BVS je tato:

A: 0.10 B: 0.20 C: 0.25 D: 0.05 E: 0.10 F: 0.25 G: 0.05

Vypočtěte, který strom je výhodnější pro operaci FIND.

Úloha 5: Určete, jak bude vypadat optimální BVS, když jej vybudujeme pro 7 klíčů s frekvencemi:

E: 0.04 F: 0.05 G: 0.22 H: 0.04 I: 0.06 J: 0.05 K: 0.15

⭐ Úloha 6: Najděte nejdelší společnou podposloupnost dvojice řetězců

Úloha 7: Najděte nejdelší společnou podposloupnost dvojice řetězců

⭐ Úloha 8: Řešte 0/1 variantu úlohy batohu pro kapacitu 130 a pět předmětů, jejichž váhy jsou postupně 20, 30, 40, 50, 60 a ceny jsou ve stejném pořadí předmětů 11, 33, 45, 58, 65.

Jaká bude maximální cena předmětů v batohu?

Uvažte, jak se vyhnout tabulce se cca 130 sloupci a upravte postup řešení tak, aby stačilo řádově méně sloupců.

⚡ Úloha 9: Každá zásilka ve skladu má určenou váhu a je nutno všechy zásilky naložit na dvě přistavené dodávky tak, aby se váhy nákladů na obou dodávkách lišily co nejméně.

Zdůvodněte, zda lze či nelze metodu DP pro řešení úlohy batohu využít i v této situaci.

Úloha 10: Kryštof staví malé sportovní lodě. Vyrábí jich několik typů a vždy se věnuje stavbě jen jedné lodě, dokud není hotová. Pro každý typ lodě zná počet dní potřebný ke stavbě lodě a zná svůj zisk z jejího prodeje. Ví, kolik dní bude letos v sezóně věnovat své práci.

Navrhněte metodu dynamického programování, která bude maximalizovat Kryštofův výdělek za letošní sezónu.