| tags | vaje, or, dinamicno programiranje |
|---|---|
| hackmd | https://hackmd.io/xwRNAIs4RwinQBLHR1TXjg |
| plugins | mathjax |
Lastnik verige
-
Z dinamičnim programiranjem reši problem za podatke
$m = 5$ ,$n = 3$ in${p_{ij}}$ iz sledeče tabele:${p_{ij}}$ 1 2 3 0 0 0 0 1 5 6 4 2 9 11 9 3 14 15 13 4 17 19 18 5 21 22 20 -
Napiši algoritem, ki reši opisani problem v splošnem.
-
-
${z_{ij}}$ ... največji zaslužek, če razdelimo$i$ zabojev v prvih$j$ trgovin -
${z_{i1}} = {p_{i1}}$ ($0 \le i \le m$ ) -
${z_{ij}} = \max \lbrace {z_{h,j-1}} + {p_{i-h,j}} \mid 0 \le h \le i \rbrace$ ($0 \le i \le m$ ,$2 \le j \le n$ ) - računamo v leksikografskem vrstnem redu po
$i, j$ - maksimalni zaslužek
$z^* = {z_{mn}}$
${z_{ij}}$ 1 2 3 0 0 0 0 1 5 6 (0) 6 (1) 2 9 11 (0,1) 11 (2) 3 14 16 (1) 16 (3) 4 17 20 (1,2,3) 20 (2,3,4) 5 21 25 (3) 25 (5,3) Optimalna razporeditev:
- trgovina: 3
- trgovina: 2
- trgovina: 0
Druga optimalna razporeditev:
- trgovina: 1
- trgovina: 2
- trgovina: 2
-
Podjetje ima na voljo
kjer so
-
${z_i}(x)$ ... največji donos, če investiramo$x \cdot 1000€$ v prvih$i$ investicij ${z_1}(x) = {r_1}(x)$ ${z_i}(x) = \max \lbrace {z_{i-1}}(y) + {r_i}(x-y) \mid 0 \le y \le x \rbrace$ $z^* = {z_3}(6)$
Največji zaslužek
- investicija: 4000 €
- investicija: 1000 €
- investicija: 1000 €
Nori profesor Boltežar stanuje v stolpnici z
Ker ima Boltežar doma
- Napiši rekurzivne enačbe za opisani problem.
- Napiši algoritem, ki reši opisani problem. Oceni tudi njegovo časovno zahtevnost v odvisnosti od
$n$ in$k$ .
-
${p_{ij}}$ ... največje število potrebnih metov, če imamo še$j$ lončkov in$i$ nadstropij za preveriti -
${p_{0j}} = 0$ ($j \ge 0$ ) -
${p_{i0}} = \infty$ ($i \ge 1$ ) ${p_{ij}} = 1 + \min \lbrace \max \lbrace {p_{h-1,j-1}}, {p_{i-h,j}} \rbrace \mid 1 \le h \le i \rbrace$ - računamo vrednosti
${p_{ij}}$ v leksikografskem vrstnem redu po$i, j$ $p^* = {p_{nk}}$
def loncki(n, k):
p = [[0] * (k+1), *([float('inf')] for _ in range(n))]
for i in range(1, n+1):
for j in range(1, k+1):
m = float('inf')
for h in range(1, i+1):
m = min(m, max(p[h-1][j-1], p[i-h][j]))
p[i].append(m+1)
return p[n][k]Časovna zahtevnost:
Podjetje bo kmalu uvedlo nov izdelek na zelo konkurenčen trg, zato trenutno pripravlja marketinško strategijo. Odločili so se, da bodo izdelek uvedli v treh fazah. V prvi fazi bodo pripravili posebno začetno ponudbo z močno znižano ceno, da bi privabili zgodnje kupce. Druga faza bo vključevala intenzivno oglaševalsko kampanjo, da bi zgodnje kupce prepričali, naj izdelek še vedno kupujejo po redni ceni. Znano je, da bo ob koncu druge faze konkurenčno podjetje predstavilo svoj izdelek. Zato bo v tretji fazi okrepljeno oglaševanje z namenom, da bi preprečili beg strank h konkurenci.
Podjetje ima za oglaševanje na voljo
-
Denimo, da želimo v vsaki fazi porabiti nek večkratnik milijona evrov, pri čemer bomo pri prvi fazi porabili vsaj milijon evrov. V spodnji tabeli so zbrani vplivi porabljenih količin na vrednosti
$m$ ,${f_2}$ in${f_3}$ .M€ $m$ ${f_2}$ ${f_3}$ 0 - 0.2 0.3 1 20 0.4 0.5 2 30 0.5 0.6 3 40 0.6 0.7 4 50 - - Kako naj razdelimo sredstva?
-
Denimo sedaj, da lahko v vsaki fazi porabimo poljubno pozitivno količino denarja (seveda glede na omejitev skupne porabe). Naj bodo torej
${x_1}$ ,${x_2}$ in${x_3}$ količine denarja v milijonih evrov, ki jih porabimo v prvi, drugi in tretji fazi. Vpliv na tržni delež je podan s formulami$$ m = x_1 (10 - x_1), \quad f_2 = 0.4 + 0.1 x_2, \quad \text{in} \quad f_3 = 0.6 + 0.07 x_3 . $$
Kako naj sedaj razdelimo sredstva?
Vodja prodaje pri založniku učbenikov za fakulteto ima na voljo
| 1 | 2 | 3 | |
|---|---|---|---|
| 1 | 35 | 21 | 28 |
| 2 | 48 | 42 | 41 |
| 3 | 70 | 56 | 63 |
| 4 | 89 | 70 | 75 |
Reši problem s pomočjo dinamičnega programiranja.
Dan je sledeči nelinearni program.
Reši ga s pomočjo dinamičnega programiranja.
Igralec na srečo bo odigral tri partije s svojimi prijatelji, pri čemer lahko vsakič stavi na svojo zmago. Stavi lahko katerokoli vsoto denarja, ki jo ima na voljo - če izgubi partijo, zastavljeno vsoto izgubi, sicer pa tako vsoto pridobi. Pri vsaki partiji sta verjetnosti zmage in poraza enaki
Z dinamičnim programiranjem poišči strategijo stavljenja, ki maksimizira verjetnost, da bo na koncu imel natanko