---
tags: vaje, or, dinamicno programiranje
hackmd: https://hackmd.io/6sImSnqTSwiw_UnVJ2ls6A
plugins: mathjax, mermaid
---
# Operacijske raziskave - vaje 29.3.2021

---

## Dinamično programiranje

* Deli in vladaj

  graph TD
  
  A --- B
  A --- C
  B --- D
  B --- E
  C --- F
  C --- G

* Dinamično programiranje

  graph TD
  
  A --- E
  B --- E
  B --- F
  C --- F
  C --- G
  D --- G
  E --- H
  F --- H
  F --- I
  G --- I
  H --- J
  I --- J

---

### Naloga 1

Na avtocestni odsek dolžine $M$ kilometrov želimo postaviti oglasne plakate. Dovoljene lokacije plakatov določa urad za oglaševanje in so predstavljene s števili ${x_1}, {x_2}, \dots {x_n}$, kjer ${x_i}$ ($1 \le i \le n$) predstavlja oddaljenost od začetka odseka v kilometrih. Profitabilnost oglasa na lokaciji ${x_i}$ določa vrednost ${v_i}$ ($1 \le i \le n$). Urad za oglaševanje podaja tudi omejitev, da mora biti razdalja med oglasi vsaj $d$ kilometrov. Oglase želimo postaviti tako, da bodo čim bolj profitabilni.

1. Reši problem za parametre $M = 20$, $d = 5$, $n = 8$, <i>$(x_i)_{i=1}^n = (1, 2, 8, 10, 12, 14, 17, 20)$</i> in <i>$(v_i)_{i=1}^n = (8, 8, 12, 10, 7, 5, 6, 10)$</i>.
2. Napiši rekurzivne enačbe za opisani problem.
3. Napiši algoritem, ki poišče najbolj profitabilno postavitev oglasov za dane parametre. Kakšna je njegova časovna zahtevnost?

----

1. * ${p_i}$ ... maksimalna profitabilnost, če uporabimo prvih $i$ plakatnih mest

| $i$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| ------- | - | - | -- | -- | -- | -- | -- | -- |
| ${x_i}$ | 1 | 2 | 8 | 10 | 12 | 14 | 17 | 20 |
| ${v_i}$ | 8 | 8 | 12 | 10 | 7 | 5 | 6 | 10 |
| ${p_i}$ | 8 | 8 | 20 | 20 | 20 | 25 | 26 | 35 |

Rešitev:
* ${p_8} > {p_7}$: postavimo na 8. mesto
* ${p_6} > {p_5}$: postavimo na 6. mesto
* ${p_3} > {p_2}$: postavimo na 3. mesto
* ${p_2} = {p_1}$: ne postavimo na 2. mesto
* ${p_1} > 0$: postavimo na 1. mesto

2. * ${p_0} = 0$, ${x_0} = -\infty$
* ${p_i} = \max \lbrace {p_{i-1}, {p_j} + {v_i} \mid {x_j} \le {x_i} - d} \rbrace$ ($1 \le i \le n$)
* vrednosti ${p_i}$ računamo naraščajoče po indeksu $i$
* optimalna vrednost: $p^* = {p_n}$

3. ```python
def plakati(x, v, d): # predpostavimo, da je x urejen
n = len(x)
assert n == len(v) # preveri, da velja zapisani pogoj
x = [-float('inf'), *x]
v = [0, *v]
p = [0]
j = 0
for i in range(1, n+1):
while x[j+1] <= x[i] - d:
j += 1
p.append(max(p[i-1], p[j] + v[i]))
m = []
i = n
while i > 0:
if p[i] > p[i-1]:
m.append(i)
y = x[i]
while x[i] > y - d:
i -= 1
else:
i -= 1
return (p[n], list(reversed(m)))

   Časovna zahtevnost: $O(n)$

---

### Naloga 2

Imamo nahrbtnik nosilnosti $M$ kilogramov. Danih je $n$ objektov z vrednostmi ${v_i}$ in težami ${t_i}$ ($1 \le i \le n$). Problem nahrbtnika sprašuje po izbiri predmetov $I \subseteq \{1, 2, \dots, n\}$, ki maksimizira njihovo skupno vrednost pri omejitvi $\sum_{i \in I} t_i \le M$.

1. Napiši rekurzivne enačbe za opisani problem.
2. Z uporabo rekurzivnih enačb reši problem za parametre $M = 8$, $n = 8$, <i>$(v_i)_{i=1}^n = (9, 9, 8, 11, 10, 15, 3, 12)$</i> in <i>$(t_i)_{i=1}^n = (3, 5, 1, 4, 3, 8, 2, 7)$</i>.

----

1. * ${p_j}$ ... največja vrednost pri nosilnosti $j$ kilogramov
   * ${I_j}$ ... množica predmetov teže največ $j$ kilogramov, s katero dosežemo vrednost ${p_j}$
   * ${p_0} = 0$, ${I_0} = \emptyset$
   * $({p_j}, {I_j}) = \max \lbrace ({p_{j-1}}, {I_{j-1}}), ({p_{j-{t_i}}} + {v_i}, {I_{j-{t_i}}} \cup \lbrace i \rbrace) \mid 1 \le i \le n, j \ge {t_i}, i \notin {I_{j-{t_i}}} \rbrace$ ($1 \le i \le M$)
   * vrednosti ${p_j}$ in ${I_j}$ računamo naraščajoče po indeksu $j$
   * optimalna rešitev $I^* = {I_M}$ z vrednostjo $p^* = {p_M}$
   * časovna zahtevnost: $O(Mn)$ - psevdopolinomski algoritem!

2. * ${p_0} = 0$, ${I_0} = \emptyset$
   * ${p_1} = 8$, ${I_1} = \lbrace 3 \rbrace$
   * ${p_2} = 8$, ${I_2} = \lbrace 3 \rbrace$
   * ${p_3} = 11$, ${I_3} = \lbrace 3, 7 \rbrace$
   * ${p_4} = 18$, ${I_4} = \lbrace 3, 5 \rbrace$
   * ${p_5} = 19$, ${I_5} = \lbrace 3, 4 \rbrace$
   * ${p_6} = 21$, ${I_6} = \lbrace 3, 5, 7 \rbrace$
   * ${p_7} = 27$, ${I_7} = \lbrace 1, 3, 5 \rbrace$
   * ${p_8} = 29$, ${I_8} = \lbrace 3, 4, 5 \rbrace$

---

### Naloga 3

Dana je matrika <i>$A = (a_{ij})_{i,j=1}^{m,n}$</i>. Poiskati želimo pot minimalne vsote, ki se začne v levem zgornjem kotu (pri <i>$a_{11}$</i>) in konča v desnem spodnjem kotu (pri <i>$a_{mn}$</i>). Dovoljeni so zgolj premiki v desno in navzdol.

1. Reši problem za matriko

   $$
   A = \begin{pmatrix}
   131 & 673 & 234 & 103 &  18 \\
   201 &  96 & 342 & 965 & 150 \\
   630 & 803 & 746 & 422 & 111 \\
   537 & 699 & 497 & 121 & 956 \\
   805 & 732 & 524 &  37 & 332
   \end{pmatrix} .
   $$

2. Napiši rekurzivne enačbe za opisani problem.

3. Na osnovi rekurzivnih enačb napiši algoritem, ki reši opisani problem. Oceni tudi njegovo časovno zahtevnost v odvisnosti od $m$ in $n$.

----

* ${p_{ij}}$ ... najmanjša vsota elementov na poti od ${a_{11}}$ do ${a_{ij}}$
* ${p_{11}} = {a_{11}}$
* ${p_{1j}} = {a_{1j}} + {p_{1, j-1}}$ ($2 \le j \le n$)
* ${p_{i1}} = {a_{i1}} + {p_{i-1, 1}}$ ($2 \le i \le m$)
* ${p_{ij}} = {a_{ij}} + \min \lbrace {p_{i-1, j}}, {p_{i, j-1}} \rbrace$ ($2 \le i \le m$, $2 \le j \le n$)
* vrednosti ${p_{ij}}$ računamo leksikografsko po $(i, j)$
* optimalna vrednost $p^* = {p_{mn}}$
* časovna zahtevnost: $O(mn)$