Dinamicno programiranje.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "c5314ea0-a14c-4592-a15a-65b8da592d2a",
   "metadata": {},
   "source": [
    "# Dinamično programiranje\n",
    "\n",
    "Dinamično programiranje je algoritmičen pristop, ki je podoben pristopu deli in vladaj. Tudi pri uporabi dinamičnega programiranja bomo razbili problem na manjše podprobleme, poiskali optimalne rešitve podproblemov in si z njimi pomagali pri rešitvi začetnega problema. Pomembne lastnosti problema, pri katerem si lahko pomagamo z dinamičnim programiranjem so:\n",
    "\n",
    "- neodvisnost podproblemov: Posamezen podproblem lahko rešujemo neodvisno od drugih podproblemov.\n",
    "- optimalna podstruktura: Optimalna rešitev problema vsebuje optimalne rešitve podproblemov.\n",
    "- **prekrivanje/ponavljanje podproblemov**: To je glavna lastnost, ki jo bomo izkoristili za izboljšave in v čemer se pristop razlikuje od tehnike deli in vladaj.\n",
    "\n",
    "Tehniko lahko enostavno povzamemo z nasvetom \"ne računaj enakih stvari večkrat\", v praksi pa je kljub temu nekoliko bolj zapleteno - kako to doseči, katere stvari sploh so enake, ...\n",
    "\n",
    "Pristop nima nobene veze z dinamično alokacijo pomnilnika. Poimenoval ga je njen avtor Richard Bellman. \"Programiranje\" se nanaša na reševanje optimizacijskega problema, podobno kot matematično programiranje/optimizacija. Pridevnik \"dinamično\" pa se nanaša na različne podprobleme."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "c31adfd1-41e8-4746-87cb-6672ab3526a0",
   "metadata": {},
   "outputs": [],
   "source": [
    "#include <iostream>\n",
    "#include <string>\n",
    "#include <vector>\n",
    "#include <algorithm>\n",
    "using namespace std;"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5e3fdb61-a77a-43c2-9f85-ba3405282cef",
   "metadata": {},
   "source": [
    "## Fibonaccijevo zaporedje\n",
    "\n",
    "Osnovno idejo dinamičnega programiranja si oglejmo na trivialnem primeru Fibonacijevega zaporedja, ki je definirano rekurzivno kot: $F_0 = 0,\\quad F_1 = 1,\\quad F_n = F_{n-1}+F_{n-2}$. Zanima nas $n$-to število v zaporedju. Pri večjih $n$-jih bodo vrednosti zaporedja precej velike, vendar se s tem ne bomo ukvarjali in bomo zadovoljni z rezultatom, ki je posledica preliva (*overflow*)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "ba654d56-8afd-4b2e-ab4a-6f9fc8f1d749",
   "metadata": {},
   "outputs": [],
   "source": [
    "int fib(int n) {\n",
    "    if (n<=1) return n;\n",
    "    return fib(n-1)+fib(n-2);\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "f14494ab-ea80-4ac8-a1a2-0c282ef56066",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0: 0\n",
      "1: 1\n",
      "2: 1\n",
      "3: 2\n",
      "4: 3\n",
      "5: 5\n",
      "6: 8\n",
      "7: 13\n",
      "8: 21\n",
      "9: 34\n"
     ]
    }
   ],
   "source": [
    "for (int n=0;n<10;n++) {\n",
    "    cout << n << \": \" << fib(n) << endl;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8aceb5c9-4d47-4493-bb0f-c9afaf794c82",
   "metadata": {},
   "source": [
    "Vrednosti izgledajo pravilne. Hitro pa ugotovimo, da na ta način ne bomo mogli računati vrednosti že za malo večje $n$-je. Težava je v eksponentni velikosti drevesa rekurzivnih klicev. Listov tega drevesa, kjer je rezultat funkcije 1, je natanko $F_n$. Poleg tega pa imamo še liste z vrednostjo 0 in vsa notranja vozlišča. Skratka, ogromno število vozlišč oz. klicev funkcije."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "145d0047-71e8-47cb-8d31-23f85f0ba4d2",
   "metadata": {},
   "outputs": [],
   "source": [
    "//cout << fib(100) << endl;  // prepocasi"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bba46d3c-dd51-47d9-a578-250894e37904",
   "metadata": {},
   "source": [
    "Opazimo lahko, da se bo funkcija izvedla večkrat z istim argumentom $n$. Če se nismo kje zmotili, bi moral imeti vsak tak klic funkcije tudi enak rezultat. Rezultat si lahko ob prvem klicu funkcije shranimo, v kasnejših klicih pa ga samo vrnemo. To je pristop **od zgoraj navzdol** (*top-down*), ki je znan tudi pod imenom **memoizacija** (*memoization*, brez \"r\"). Funkcija se bo torej za vsak možen argument izvedla natanko enkrat, ob ostalih klicih pa bo takoj vrnila vrednost, česar niti ne bomo šteli kot klic funkcije. Število klicev funkcije bo torej $O(n)$, čas izvedbe posameznega klica funkcije pa $O(1)$. Rešitev ima časovno in prostorsko zahtevnost $O(n)$.\n",
    "\n",
    "Za ugotavljanje, ali je bil nek podproblem že rešen ali ne, lahko v tem primeru izkoristimo kar vrednost 0, saj bomo kot izračunane rezultate vpisovali samo večja števila. V splošnem pa bi lahko imeli eno tabelo, ki bi nam povedala, ali je bil nek podproblem že rešen, ter drugo tabelo, ki bi hranila dejanske rezultate. Zaradi enostavnosti bomo uporabili dovolj veliko fiksno tabelo. Namesto tega bi lahko uporabili katerokoli implementacijo slovarja, ki bi imel kot ključ argumente, ki predstavljajo opis podproblema, za pripadajočo vrednost pa njegovo rešitev."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "0061af59-6373-4917-b230-9dfcd6f806ac",
   "metadata": {},
   "outputs": [],
   "source": [
    "const int N=10000;\n",
    "int memo[N+1];  // memoizacijska tabela"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "6742a809-9765-44ed-92f2-6a493830fcba",
   "metadata": {},
   "outputs": [],
   "source": [
    "int fib2(int n) {\n",
    "    if (n<=1) return n;\n",
    "    if (memo[n]!=0) return memo[n];\n",
    "    memo[n]=fib2(n-1)+fib2(n-2);\n",
    "    return memo[n];\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "83ec48f0-5b75-4ba2-8fa7-cd0f61b16e62",
   "metadata": {},
   "source": [
    "Če smo malo bolj sistematični, lahko rešujemo podprobleme v takem vrstnem redu, da imamo rešitve manjših podproblemov vedno že rešene, ko jih potrebujemo. Podprobleme bomo torej reševali od manjših proti večjim, kar v tem primeru pomeni od manjših proti večjim $n$-jem. Takemu reševanju rečemo **od spodaj navzgor** (*bottom-up*). Časovna in prostorska zahtevnost sta enaki kot v prejšnjem primeru, le da sta še bolj očitni."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "d09bf1cf-44ab-45ea-83a2-193b5a594f72",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "-980107325\n",
      "55\n"
     ]
    }
   ],
   "source": [
    "int fib3[N+1];\n",
    "fib3[0]=0;\n",
    "fib3[1]=1;\n",
    "for (int n=2;n<=N;n++) fib3[n]=fib3[n-1]+fib3[n-2];\n",
    "cout << fib3[100] << endl;  // overflow\n",
    "cout << fib3[10] << endl;"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b23be1a8-d9c4-49cc-9af1-9a66c550411c",
   "metadata": {},
   "source": [
    "Zaradi sistematičnosti pa smo lahko malo bolj prostorsko učinkoviti. Vedno namreč potrebujemo rezultate samo zadnjih dveh izračunanih problemov. Tako lahko prostorsko zahtevnost zmanjšamo na $O(1)$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "41538e60-4dd0-4c1c-ac4a-fa13a21fdbb2",
   "metadata": {},
   "outputs": [],
   "source": [
    "int fib4(int n) {\n",
    "    int f2=0, f1=1;\n",
    "    for (int i=2;i<=n;i++) {\n",
    "        int fi=f1+f2;\n",
    "        f2=f1;\n",
    "        f1=fi;\n",
    "    }\n",
    "    return f1;\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "ecab7080-3b67-4a88-bb0d-18dd428e36f6",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "55\n"
     ]
    }
   ],
   "source": [
    "cout << fib4(10) << endl;"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4f09b376-72c0-4222-9bff-a5dc84024d14",
   "metadata": {},
   "source": [
    "## Žabji skoki\n",
    "\n",
    "Vzdolž potoka gleda iz vode $n$ skal na koordinatah $x_1 < x_2 < ... < x_n$. Žabec sedi na prvi skali in bi rad z zaporedjem skokov po skalah prispel do zadnje skale. V enem skoku lahko skoči najmanj $a$ in največ $b$ enot daleč v smeri proti cilju. Kakšno je najmanjše število skokov, ki jih potrebuje za to?\n",
    "\n",
    "Če je $a=0$, smo že v poglavju o požrešnih algoritmih na podobnem problemu ugotovili, da lahko z vsakim skokom skoči do najbolj oddaljene skale, ki jo še doseže, in bo s tem minimiziral število svojih skokov. Vpeljava spodnje meje dolžine skoka pa problem zakomplicira.\n",
    "\n",
    "Če razmišljamo rekurzivno, se bo žabec v prvem skoku premaknil na neko skalo $x_i$, ki je oddaljena med $a$ in $b$ od skale $x_1$. Če take skale sploh ni, pot do cilja ne obstaja. Za to je porabil en skok, nato pa se mora v čim manjšem številu skokov premakniti s skale $x_i$ do cilja. Definirajmo podproblem $f(i)$ kot najmanjše število skokov, ki ga žabec potrebuje, da pride na cilj z $i$-te skale:\n",
    "\n",
    "- $f(n) = 0$\n",
    "- $f(i) = \\min_{j>i:\\;a \\leq x_j-x_i \\leq b\\;} (1 + f(j))$\n",
    "\n",
    "Očitno bo prišlo do ponavljanja podproblemov. Do neke skale lahko žabec pride na več načinov, ampak za optimalno pot od tam do cilja je povsem nepomembno, kako je do tja prišel. Pomembno je samo, na kateri skali se nahaja. Zato si lahko rešitev shranimo in jo kasneje po potrebi uporabimo, ne da bi jo računali ponovno. Lahko pa bi probleme reševali tudi sistematično po principu od spodaj navzgor, kar v tem primeru pomeni od skal bližje cilju proti tistim bližje začetku.\n",
    "\n",
    "Rešiti moramo $O(n)$ podproblemov, za rešitev vsakega od njih pa moramo preveriti $O(n)$ možnosti za naslednji skok. Časovna zahtevnost je $O(n^2)$, prostorska pa $O(n)$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "19ef002d-a33d-4470-b278-64c3327ebe35",
   "metadata": {},
   "outputs": [],
   "source": [
    "const int inf=1e9;\n",
    "int a=3, b=4;\n",
    "int mem_jump[1000];"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "500b7550-f000-4127-b832-2596ba6c1b31",
   "metadata": {},
   "outputs": [],
   "source": [
    "int jump(int i, vector<int> &x) {\n",
    "    int n=x.size();\n",
    "    if (i==n-1) return 0;\n",
    "    if (mem_jump[i]!=0) return mem_jump[i];\n",
    "    int best=inf;\n",
    "    for (int j=i+1;j<n;j++) {\n",
    "        int d=x[j]-x[i];\n",
    "        if (a<=d && d<=b) best=min(best, 1+jump(j,x));\n",
    "    }\n",
    "    mem_jump[i]=best;\n",
    "    return best;\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "7d91ab8f-7b95-4844-89e0-3e21baacb581",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n"
     ]
    }
   ],
   "source": [
    "vector<int> x = {0,3,4,6,10};\n",
    "cout << jump(0,x) << endl;"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9b937449-e29c-4f5b-bafe-95aab8ddd4a2",
   "metadata": {},
   "source": [
    "Problem pa lahko rešimo še hitreje. Za rešitev posameznega podproblema nas namreč zanima minimum na nekem območju. Rešitve z relevantnega območja bomo hranili v primerni podatkovni strukturi. Ta mora omogočati iskanje minimuma ter vstavljanje in brisanje elementov, ko se območje spremeni. Uporabimo lahko dvojiško kopico ali uravnoteženo drevo. Ko rešujemo podprobleme za vedno manjši indeks $i$, se robova relevantnega območja premikata v levo oz. manjšata. Tako bo vsak element enkrat dodan in enkrat odstranjen iz območja. Število iskanj, vstavljanj in brisanj bo $O(n)$, vsako od teh operacij pa lahko izvedemo v $O(\\log n)$, ker velikost območja nikoli ne bo presegla $n$. Tako dobimo rešitev s časovno zahtevnostjo $O(n \\log n)$."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1ecd09d7-a3a3-4c03-9fed-e5dd3e0a5bf0",
   "metadata": {},
   "source": [
    "## Rezanje palice\n",
    "\n",
    "Pri problemu rezanja palice (*rod cutting*) imamo podano palico dolžine $n$, ki jo želimo razrezati na manjše kose in te kose prodati posamično za čim večjo skupno ceno. Dolžina palice in dolžine kosov morajo biti celoštevilske. Podano imamo tabelo cen $c$, v kateri nam $i$-to število $c_i$ pove, za kakšno ceno bomo lahko prodali palico dolžine $i$. Daljši kot je kos, za večjo ceno ga bomo lahko prodali: veljalo bo $c_i \\leq c_{i+1}$. Kakšen je največji možen izkupiček od prodaje razrezane palice?\n",
    "\n",
    "Oglejmo si primer s spodnjo tabelo cen:\n",
    "<table>\n",
    "<tr style=\"border: 1px solid\"><td>$i$</td><td>1</td><td>2</td><td>3</td><td>4</td><td>5</td><td>6</td><td>7</td><td>8</td></tr>\n",
    "<tr style=\"border: 1px solid\"><td>$c_i$</td><td>2</td><td>5</td><td>6</td><td>9</td><td>15</td><td>16</td><td>17</td><td>20</td></tr>\n",
    "</table>\n",
    "\n",
    "Naj bo dolžina palice $n=8$:\n",
    "\n",
    "- Če razrežemo palico na kose dolžine 1, bomo zanjo dobili $n \\cdot c_1 = 16$.\n",
    "- Če pustimo palico celo, dobimo zanjo $c_8 = 20$.\n",
    "- Če jo razrežemo na dva kosa dolžin 2 in 6, pa bomo dobili $c_2 + c_6 = 21$.\n",
    "- Če jo razrežemo na tri kose dolžin 1, 2 in 5, bomo dobili $c_1 + c_2 + c_5 = 22$.\n",
    "\n",
    "\n",
    "Brez škode za splošnost predpostavimo, da bomo izvajali reze od leve proti desni. Kakršen koli drugačen vrstni red rezanja nas pripelje do razreza palice, do katerega lahko pridemo tudi z rezanjem od leve proti desni. Rekurzivni razmislek o zaslužku $f(n)$ pri optimalnem rezanju palice dolžine $n$ nam pove, da bomo morali izbrati dolžino prvega reza. Če je palica dolžine $n$, si moramo izbrati enega od rezov dolžine $x \\leq n$ (s čimer zaslužimo $c_x$) ter optimalno zrezati preostanek palice dolžine $n-x$. Ker ne vemo, katera dolžina reza bo najboljša, rekurzivno preverimo vse. Uporabimo tokrat pristop od spodaj navzgor in izračunajmo zaslužke za vedno daljše palice: $f(n) = \\max_{x \\leq n} f(n-x)+c_x$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "b9ec3d64-3832-4dc5-8136-6b326f267307",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "22\n"
     ]
    }
   ],
   "source": [
    "vector<int> c = {0,2,5,6,9,15,16,17,20};\n",
    "int N=8;\n",
    "int f[1000];\n",
    "f[0]=0;\n",
    "for (int n=1;n<=N;n++) {\n",
    "    f[n]=0;\n",
    "    for (int x=1;x<=n;x++) {\n",
    "        f[n]=max(f[n], f[n-x]+c[x]);\n",
    "    }\n",
    "}\n",
    "cout << f[N] << endl;"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ced947f4-a8b7-4366-9586-43cbb13ada4a",
   "metadata": {},
   "source": [
    "Časovna zahtevnost algoritma je $O(n^2)$, prostorska pa $O(n)$.\n",
    "\n",
    "Razmislimo še o **rekonstrukciji** rešitve. Katere reze je treba narediti, da dosežemo optimalno ceno? Za vsak podproblem poiščemo potezo, ki je vodila do optimalnega rezultata. Druga možnost pa je, da si že ob reševanju podproblema shranimo optimalno potezo: npr. v dodatni tabeli $g(n)$ bi lahko hranili $x$, pri katerem funkcija $f(n)$ doseže svoj maksimum."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "a4fd47c6-45f2-4ac4-9d8d-599a399f2b63",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1: 2\n",
      "2: 5\n",
      "5: 15\n"
     ]
    }
   ],
   "source": [
    "int n=N;\n",
    "while (n>0) {\n",
    "    for (int x=1;x<=n;x++) {\n",
    "        if (f[n]==f[n-x]+c[x]) {\n",
    "            cout << x << \": \" << c[x] << endl;\n",
    "            n-=x;\n",
    "            break;\n",
    "        }\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5b5dd7eb-1b55-45af-842f-a0f5034cd552",
   "metadata": {},
   "source": [
    "## Utežena izbira aktivnosti\n",
    "\n",
    "S problemom izbire aktivnosti smo se že ukvarjali v poglavju o požrešnih algoritmih, tu pa se bomo posvetili splošnejši uteženi različici (*weighted activity selection / weighted interval scheduling*). V neuteženem problemu smo želeli poskati največje število nekonfliktnih aktivnosti. Pravilna požrešna strategija je vključevala izbiranje aktivnosti glede na najzgodnejši konec. Za učinkovito implementacijo smo aktivnosti uredili po koncih in po vrsti izbirali prvo aktivnost, ki ni bila konfliktna s predhodno izbrano.\n",
    "\n",
    "Utežena različica poleg začetkov in koncev aktivnost ($s_i$ in $e_i$) vključuje tudi uteži posameznih aktivnosti $w_i$. Cilj problema je poiskati nekonflikten izbor aktivnosti z največjo vsoto uteži. Če so vse uteži $w_i = 1$, je problem enakovreden neuteženi različici.\n",
    "\n",
    "Prva aktivnost ($i=1$) je lahko del rešitve ali pa ne. Če jo vključimo v rešitev, lahko od tam naprej uporabljamo samo še tiste aktivnosti, ki so nekonfliktne z njo. Tako bi opis našega podproblema vključeval neko podmnožico aktivnosti, kar ni najbolj prikladno. Reševanja se lahko lotimo bolj sistematično. Namesto odločanja, kaj storiti s prvo aktivnostjo ($i=1$), se lahko odločamo, katera aktivnost naj bo prva v rezultatu. V končni rešitvi bodo aktivnosti urejene po začetkih in po koncih. Poskusimo jih urediti po koncih, kar se je izkazalo za koristno v neuteženi različici. Prvo aktivnost v taki ureditvi lahko uporabimo ali pa ne. Če jo uporabimo, so izmed preostalih aktivnosti uporabne zgolj tiste, ki se začnejo kasneje, kot se je ravnokar izbrana končala. Opis podproblema bi torej poleg pripone seznama aktivnosti, o katerih se še odločamo, vseboval še mejo, kdaj se lahko aktivnosti začnejo.\n",
    "\n",
    "Bolje se obnese urejanje po začetkih. Če prvo aktivnost v tem vrstnem redu uporabimo, bo nekaj sledečih konfliktnih, ker se začnejo pred koncem izbrane, preostale pa lahko uporabimo. Naj bo $p(i)$ indeks prve aktivnosti, ki se začne po (ali ob) koncu $i$-te: $p(i) = \\min_{j>i:\\;s_j \\geq e_i\\;} j$. Te vrednosti lahko izračunamo vnaprej z bisekcijo. Podproblem $f(i)$ je tako definiran samo s pripono seznama aktivnosti urejenih po začetkih in predstavlja največjo vsoto uteži, ki jo lahko dosežemo z aktivnostmi $i, i+1, \\ldots, n$.\n",
    "\n",
    "$$f(i)=\\max \\begin{cases}\n",
    "f(i+1) & \\text{ne uporabimo i-te aktivnosti} \\\\\n",
    "f(p(i))+w_i & \\text{uporabimo i-to aktivnost} \\\\\n",
    "\\end{cases}\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "886d0f1f-d820-446c-93d2-ffa1780af813",
   "metadata": {},
   "outputs": [],
   "source": [
    "int aktivnostiW(vector<array<int,3>> a) {\n",
    "\tsort(a.begin(), a.end());\n",
    "\tint n = a.size();\n",
    "\tvector<int> p(n), f(n+1);\n",
    "\tfor (int i=0;i<n;i++) {\n",
    "\t\tauto [s,e,w] = a[i];\n",
    "\t\tp[i] = lower_bound(a.begin(), a.end(), array<int,3>{e,-1,-1}) - a.begin();\n",
    "\t}\n",
    "\tfor (int i=n-1;i>=0;i--) {\n",
    "\t\tauto [s,e,w] = a[i];\n",
    "\t\tf[i] = max(f[i+1], f[p[i]]+w);\n",
    "\t}\n",
    "\treturn f[0];\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4540a4c7-eb97-441a-8d69-80cfad0eec41",
   "metadata": {},
   "outputs": [],
   "source": [
    "vector<array<int,3>> a = {{1,3,2}, {2,4,5}, {2,5,11}, {4,5,7}, {4,7,19}, {6,7,3}, {6,8,1}, \n",
    "                          {7,12,3}, {8,12,2}, {9,10,14}, {9,11,12}, {11,12,8}, {12,13,6}};\n",
    "cout << aktivnostiW(a) << endl;"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e19a1d00-ad13-4a2c-a722-0a80f30310fb",
   "metadata": {},
   "source": [
    "Časovna zahtevnost algoritma je $O(n \\log n)$ zaradi urejanja in bisekcije za izračun preskakovanja konfliktnih aktivnosti $p(i)$, preostalo reševanje podproblemov $f(i)$ pa je linearno."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e4c5bf68-cad1-465c-9e62-6f3b48dfa22c",
   "metadata": {},
   "source": [
    "## Pot v mreži\n",
    "\n",
    "V labirintu višine $h$ in širine $w$ oz. tabeli znakov '.', ki predstavljajo prosto polje, in '#', ki predstavlajo blokirano polje, nas zanima, na koliko načinov lahko pridemo iz levega-zgornjega kota v desni-spodnji kot, pri čemer se lahko premikamo samo desno in navzdol. V spodnjem primeru obstajajo štiri take poti.\n",
    "\n",
    "```text\n",
    ".#....\n",
    "....#.\n",
    ".#..#.\n",
    "......\n",
    "```\n",
    "\n",
    "Rekurzivno bi problem reševali tako, da bi se s trenutne celice poskusili premakniti desno in navzdol (če sta oba premika sploh možna) in sešteli možne poti do cilja iz nove lokacije (sosednje celice). Dosedanji problemi so imeli eno-dimenzionalen opis podproblema, kjer smo podproblem opisali z eno spremenljivko. Tokrat pa podproblem opišemo z dvema dimenzijama - vrstico in stolpcem celice. Če je polje zasedeno ali se nahaja izven mreže, je število poti do cilja enako $0$, sicer pa velja $f(i,j) = f(i+1,j) + f(i,j+1)$. Robni pogoj v desnem-spodnjem kotu je $f(h-1, w-1)=0$.\n",
    "\n",
    "Podprobleme lahko rešujemo sistematično po vrsticah od spodaj navzgor in znotraj vrstice od desne proti levi. Tako imamo potrebne rešitve podproblemov vsakič že na voljo. Časovna in prostorska zahtevnost sta $O(hw)$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "5cb4e940-8d19-49b2-ad33-0c697c88dd80",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4\n"
     ]
    }
   ],
   "source": [
    "vector<string> lab = {\".#....\",\n",
    "                      \"....#.\",\n",
    "                      \".#..#.\",\n",
    "                      \"......\"};\n",
    "int h=lab.size(), w=lab[0].size();\n",
    "int f[10][10];\n",
    "memset(f,0,sizeof(f));\n",
    "for (int i=h-1;i>=0;i--) {\n",
    "    for (int j=w-1;j>=0;j--) {\n",
    "        if (i==h-1 && j==w-1) f[i][j]=1;\n",
    "        else if (lab[i][j]=='#') f[i][j]=0;\n",
    "        else f[i][j]=f[i+1][j]+f[i][j+1];\n",
    "    }\n",
    "}\n",
    "cout << f[0][0] << endl;"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a1c06bf5-616d-4ce8-b617-ff574a3094c4",
   "metadata": {},
   "source": [
    "Prostorsko zahtevnost bi lahko izboljšali na $O(w)$, ker pri računanju vrednosti $f(i,*)$ potrebujemo samo že izračunane rezultate desno v isti vrstici $f(i,*)$ in eno vrstico nižje $f(i+1,*)$."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bbb38840-492d-4d08-9469-7a6f5791c077",
   "metadata": {},
   "source": [
    "## Najdaljše skupno podzaporedje\n",
    "\n",
    "Pri problemu najdaljšega skupnega podzaporedja (*longest common subsequence, LCS*) nizov $S$ in $T$ (dolžine $n$ in $m$), iščemo najdaljši niz $\\text{LCS}(S,T)$, ki se pojavi kot podzaporedje (ne nujno podniz) v $S$ in v $T$. Oglejmo si primer $S=A\\bar{B}\\bar{C}\\bar{B}D\\bar{A}B$ in $T=\\bar{B}D\\bar{C}\\bar{B}B\\bar{A}$, kjer je eno izmed najdaljših skupnih podzaporedij $\\text{LCS}(S,T)=BCBA$ dolžine 4.\n",
    "\n",
    "Drugačen pogled na isti problem je poravnava obeh nizov, da se pri tem čim več znakov ujema.\n",
    "```\n",
    "AB CB DAB\n",
    " BDCBB A\n",
    "```\n",
    "Rekurzivni razmislek je sledeč:\n",
    "\n",
    "- Če se oba niza začneta z enakim znakom, je ta znak lahko začetek LCS-ja, preostanek pa je LCS za en znak krajših nizov.\n",
    "- Če se niza razlikujeta v prvem znaku, potem vsaj en od teh dveh znakov ne bo del LCS-ja. Preizkusimo obe možnosti in rešimo problem z nizoma, kjer je en malo krajši.\n",
    "\n",
    "Naj bo $\\text{LCS}(i,j)$ najdaljši skupni podniz nizov $S_i S_{i+1} \\ldots S_{n-1}$ in $T_j T_{j+1} \\ldots T_{m-1}$:\n",
    "$$\\text{LCS}(i,j)=\\max \\begin{cases}\n",
    "1+\\text{LCS}(i+1,j+1) & \\text{če } S_i = T_j \\\\\n",
    "\\text{LCS}(i+1,j) \\\\\n",
    "\\text{LCS}(i,j+1) \\\\\n",
    "\\end{cases}\\\\\n",
    "$$\n",
    "Robni primeri pa so $\\text{LCS}(n,*) = 0$ in $\\text{LCS}(*,m) = 0$.\n",
    "\n",
    "\n",
    "Problem lahko rešujemo sistematično od večjih proti manjšim $i$-jem in enako za $j$. Rešujemo torej probleme z vedno daljšimi priponami nizov $S$ in $T$. S tem pravzaprav izpolnjujemo 2D tabelo od desnega spodnjega kota proti levemu zgornjemu, tako da izberemo večjo od spodnje in desne celice. Če sta začetna znaka enaka, pa upoštevamo še diagonalen rezultat povečan za 1. Dokažemo lahko tudi, da bo ta diagonalna poteza vedno optimalna, če je na voljo."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "a43b135a-4aa5-408d-89e5-1ee5491f60c7",
   "metadata": {},
   "outputs": [],
   "source": [
    "string LCS(string s, string t) {\n",
    "    int n=s.size(), m=t.size();\n",
    "    int lcs[n+1][m+1];  // dodatna vrstica in stolpec nicel\n",
    "    memset(lcs,0,sizeof(lcs));\n",
    "    for (int i=n-1;i>=0;i--) {\n",
    "        for (int j=m-1;j>=0;j--) {\n",
    "            lcs[i][j]=max(lcs[i+1][j], lcs[i][j+1]);\n",
    "            if (s[i]==t[j]) lcs[i][j]=max(lcs[i][j], 1+lcs[i+1][j+1]);\n",
    "        }\n",
    "    }\n",
    "    // izpis izracunane tabele\n",
    "    for (int i=0;i<n;i++) {\n",
    "        for (int j=0;j<m;j++) {\n",
    "            cout << lcs[i][j] << '\\t';\n",
    "        }\n",
    "        cout << endl;\n",
    "    }\n",
    "    // rekonstrukcija\n",
    "    string l=\"\";\n",
    "    int i=0, j=0;\n",
    "    while (i<n && j<m) {\n",
    "        if (lcs[i][j]==lcs[i+1][j]) i++;\n",
    "        else if (lcs[i][j]==lcs[i][j+1]) j++;\n",
    "        else { l+=s[i]; i++; j++; }\n",
    "    }\n",
    "    return l;\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "8c8f150c-a83e-452c-b34d-acbbe1fa279b",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4\t3\t3\t3\t2\t1\t\n",
      "4\t3\t3\t3\t2\t1\t\n",
      "3\t3\t3\t2\t2\t1\t\n",
      "3\t2\t2\t2\t2\t1\t\n",
      "2\t2\t1\t1\t1\t1\t\n",
      "1\t1\t1\t1\t1\t1\t\n",
      "1\t1\t1\t1\t1\t0\t\n",
      "LCS = BCBA\n"
     ]
    }
   ],
   "source": [
    "string l = LCS(\"ABCBDAB\", \"BDCBBA\");\n",
    "cout << \"LCS = \" << l << endl;"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e9ff0188-b451-41a3-8249-f6d72763206a",
   "metadata": {},
   "source": [
    "Časovna in prostorska zahtevnost sta $O(nm)$. Problem lahko rešujemo tudi v obratni smeri od konca proti začetkom nizov, kjer se vprašamo, kaj se bo zgodilo z zadnjima znakoma obeh nizov (namesto prvima), kar boste pogosto videli v drugih virih.\n",
    "\n",
    "Kako pa bi problem rešili za tri nize? $\\text{LCS}(S,T,U)$ namreč ni enak $\\text{LCS}(\\text{LCS}(S,T),U)$! Stanje bi opisali s trojico indeksov $\\text{LCS}(i,j,k)$ in obravnavali primere podobno kot za dva niza. Če velja $S_i = T_j = U_k$, je ta znak lahko del LCS-ja, sicer pa vsaj en izmed njih ne bo in lahko enega od nizov skrajšamo.\n",
    "\n",
    "Soroden problem je iskanje najdaljšega skupnega podniza (ne podzaporedja; *longest common substring*), kjer mora biti pojavitev podniza strnjena v obeh nizih. Ta problem ima drugačne in bolj učinkovite rešitve."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "165f895e-6be5-4c10-8efc-3f1ffef9a266",
   "metadata": {},
   "source": [
    "## Nahrbtnik\n",
    "\n",
    "Problem nahrbtnika (*knapsack, backpack*) je še en klasičen primer uporabe dinamičnega programiranja. Podan imamo nabor $n$ predmetov, za katere poznamo njihove teže $t_i$ in vrednosti $v_i$ (oboje so cela števila). Izbrali bi radi neko podmnožico $S$ teh predmetov, ki bo imela čim večjo vrednost ($\\sum_{j \\in S} v_j$) in jih bomo lahko spravili v nahrbtnik z nosilnostjo $T$ ($\\sum_{j \\in S} t_j \\leq T$). Problemu se natančneje reče 0-1 nahrbtnik, ker vsak predmet vzamemo v celoti ali pa ga pustimo, ne moremo pa vzeti samo dela predmeta.\n",
    "\n",
    "V rekurzivni rešitvi bi se lahko za vsak predmet odločili, ali ga bomo vzeli ali ne. Če ga vzamemo, imamo za preostale predmeta na voljo nekoliko manjšo nosilnost. Podproblem torej opišemo z dvema atributoma.\n",
    "\n",
    "- Nabor predmetov, za katere se moramo še odločiti, kaj bomo z njimi. Če smo sistematični, se lahko o vključenosti predmetov odločamo po vrsti od prvega do zadnjega.\n",
    "- Nosilnost nahrbtnika, ki je na voljo za preostale predmete.\n",
    "\n",
    "Naj bo $f(i,x)$ največja vrednost, ki jo lahko dobimo v nahrbtniku z nosilnostjo $x$, če lahko vanj dodajamo predmete $i, i+1, \\ldots, n$. Obravnavamo dva primera, glede na (ne)uporabo $i$-tega predmeta. Robni primer je $f(n,*)=0$ (če nam zmanjka predmetov, lahko dobimo samo vrednost 0).\n",
    "\n",
    "$$f(i,x)=\\max \\begin{cases}\n",
    "f(i+1,x) & \\text{ne uporabimo i-tega predmeta} \\\\\n",
    "f(i+1,x-t_i)+v_i & \\text{če je } t_i \\leq x\\text{, lahko uporabimo i-ti predmet} \\\\\n",
    "\\end{cases}\n",
    "$$\n",
    "\n",
    "Časovna zahtevnost je $O(nT)$. Če nimamo meje za $T$, vemo, da teža predmetov ne bo presegla $\\sum t_i$. Ta rešitev z dinamičnim programiranjem izkorišča majhne celoštevilske teže predmetov in nosilnost nahrbtnika. Če bi bile teže in vrednosti neka realna števila, postane problem izrazito težji (NP-težek). V tem primeru imajo različne kombinacije predmetov različne teže in vrednosti, zato se nam podproblemi ne bi ponavljali. V primeru celih števil pa so bile te vrednosti samo z omejenega intervala celih števil. Čeprav obstaja $O(2^n)$ podmnožic, je na razpolago samo $O(T)$ različnih nosilnosti nahrbtnika."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "c1be073a-4b50-40f0-afa1-6782b579a760",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "60\n"
     ]
    }
   ],
   "source": [
    "const int n = 4;\n",
    "const int nosilnost = 40;\n",
    "vector<int> teza     = {30,10,40,20};\n",
    "vector<int> vrednost = {10,20,30,40};\n",
    "\n",
    "int f[n+1][nosilnost+1];\n",
    "memset(f,0,sizeof(f));\n",
    "for (int i=n-1;i>=0;i--) {\n",
    "    for (int x=0;x<=nosilnost;x++) {\n",
    "        f[i][x] = f[i+1][x];  // ne uporabimo i-tega predmeta\n",
    "        if (teza[i]<=x) {  // poskusimo uporabiti i-ti predmet\n",
    "            f[i][x] = max(f[i][x], vrednost[i]+f[i+1][x-teza[i]]);\n",
    "        }\n",
    "    }\n",
    "}\n",
    "cout << f[0][nosilnost] << endl;"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "C++17",
   "language": "C++17",
   "name": "xcpp17"
  },
  "language_info": {
   "codemirror_mode": "text/x-c++src",
   "file_extension": ".cpp",
   "mimetype": "text/x-c++src",
   "name": "c++",
   "version": "17"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}