graph TD
A --- B
A --- C
B --- D
B --- E
C --- F
C --- G
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
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.
| $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)$
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$.
| $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!
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.
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} .\]Napiši rekurzivne enačbe za opisani problem.
Na osnovi rekurzivnih enačb napiši algoritem, ki reši opisani problem. Oceni tudi njegovo časovno zahtevnost v odvisnosti od $m$ in $n$.
Časovna zahtevnost: $O(mn)$