or
or
By clicking below, you agree to our terms of service.
New to HackMD? Sign up
Syntax | Example | Reference | |
---|---|---|---|
# Header | Header | 基本排版 | |
- Unordered List |
|
||
1. Ordered List |
|
||
- [ ] Todo List |
|
||
> Blockquote | Blockquote |
||
**Bold font** | Bold font | ||
*Italics font* | Italics font | ||
~~Strikethrough~~ | |||
19^th^ | 19th | ||
H~2~O | H2O | ||
++Inserted text++ | Inserted text | ||
==Marked text== | Marked text | ||
[link text](https:// "title") | Link | ||
 | Image | ||
`Code` | Code |
在筆記中貼入程式碼 | |
```javascript var i = 0; ``` |
|
||
:smile: | ![]() |
Emoji list | |
{%youtube youtube_id %} | Externals | ||
$L^aT_eX$ | LaTeX | ||
:::info This is a alert area. ::: |
This is a alert area. |
On a scale of 0-10, how likely is it that you would recommend HackMD to your friends, family or business associates?
Please give us some advice and help us improve HackMD.
Syncing
xxxxxxxxxx
Operacijske raziskave - vaje 30.3.2020
Dinamično programiranje
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.
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} \]
Č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\).
\[ \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} \]
\(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.
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\).
\[ \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)\)