2020-03-30.md

tags	vaje, or, dinamicno programiranje
hackmd	https://hackmd.io/lg1h-7IvR6Gq_qxARZVQng
plugins	mathjax, mermaid

Operacijske raziskave - vaje 30.3.2020

---

Dinamično programiranje

• Deli in vladaj

graph TD 

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

Loading

• Dinamično programiranje

graph TD
A --- F
B --- F
B --- G
C --- G
C --- H
D --- H
D --- I
E --- I
F --- J
G --- J
G --- K
H --- K
H --- L
I --- L
J --- M
K --- M
K --- N
L --- N
N --- O
M --- O

Loading

---

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$, $(x_i){i=1}^n = (1, 2, 8, 10, 12, 14, 17, 20)$ in $(v_i){i=1}^n = (8, 8, 12, 10, 7, 5, 6, 10)$.
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?

---

$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
$y_i$	0		2			3	5	6

Kam postavimo plakate: $x_8 = 20, x_6 = 14, x_3 = 8, x_1 = 1$.

$$ \begin{aligned} y_0 &= 0 \\ p_0 &= 0 \\ y_i &= \max{j \mid y_{i-1} \le j \le i-1, x_j \le x_i - d} & (i > 0) \\ p_i &= \max{p_{i-1}, v_i + p_{y_i}} & (i > 0) \\ p^* &= p_n \end{aligned} $$

---

def plakati(x, v, d):
    n = len(x)
    j = 0
    s = []
    for i, xi in enumerate(x):
        while xi - x[j] >= d:
            j += 1
        if j == 0:
            p = 0
            y = None
        else:
            y = j - 1
            p = s[y][0]
        p += v[i]
        if i > 0 and p < s[i-1][0]:
            y = i - 1
            p = s[y][0]
            b = False
        else:
            b = True
        s.append((p, y, b))
    p, y, b = s[-1]
    pozicije = []
    if b:
        pozicije.append(n - 1)
    while y is not None:
        z = y
        _, y, b = s[y]
        if b:
            pozicije.append(z)
    return (p, list(reversed(pozicije)))

Č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$, $(v_i){i=1}^n = (9, 9, 8, 11, 10, 15, 3, 12)$ in $(t_i){i=1}^n = (3, 5, 1, 4, 3, 8, 2, 7)$.

---

$$ \begin{aligned} (p_0, I_0) &= (0, \emptyset) \\ (p_j, I_j) &= \max({(p_{j-t_i} + v_i, I_{j-t_i} \cup {i}) \mid 1 \le i \le n, t_i \le j, i \not\in I_{j-t_i}} \cup {(p_{j-1}, I_{j-1})}) & (j > 0) \\ (p^_, I^_) &= (p_M, I_M) \end{aligned} $$

$j$	$p_j$	$I_j$
0	0	$\emptyset$
1	8	${3}$
2	8	${3}$
3	11	${3, 7}$
4	18	${3, 5}$
5	19	${3, 4}$
6	21	${3, 5, 7}$
7	27	${1, 3, 5}$
8	29	${3, 4, 5}$

$p^* = 29$, $I^* = {3, 4, 5}$

Časovna zahtevnost: $O(Mn)$ - psevdopolinomska!

---

Naloga 3

Dana je matrika $A = (a_{ij}){i,j=1}^{m,n}$. Poiskati želimo pot minimalne vsote, ki se začne v levem zgornjem kotu (pri $a{11}$) in konča v desnem spodnjem kotu (pri $a_{mn}$). 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$.

---

$$ \begin{aligned} p_{11} &= a_{11} \\ p_{1j} &= a_{1j} + p_{1, j-1} & (j > 1) \\ p_{i1} &= a_{i1} + p_{i-1, 1} & (i > 1) \\ p_{ij} &= a_{ij} + \min{p_{i-1, j}, p_{i, j-1}} & (i, j > 1) \\ p^* &= p_{mn} \end{aligned} $$

$$ \newcommand{\l}{\leftarrow} \newcommand{\g}{\uparrow} P = \begin{pmatrix} 131 & \l 804 & \l 1038 & \l 1141 & \l 1159 \\ \g 332 & \l 428 & \l 770 & \l 1735 & \g 1309 \\ \g 962 & \g 1231 & \g 1516 & \l 1938 & \g 1420 \\ \g 1499 & \g 1930 & \g 2013 & \g 2059 & \g 2376 \\ \g 2304 & \g 2662 & \g 2537 & \g 2096 & \l 2428 \end{pmatrix} . $$

Časovna zahtevnost: $O(mn)$