<filename>naloge/prodajalec.tex
\begin{naloga}{<NAME>}{Izpit OR 5.2.2010}
\begin{vprasanje}
Na znanem TV kanalu HOP.tv bodo ob sredah ob 17h
predvajali humanitarno igro Prodajalec\texttrademark,
pri kateri igralec prodaja predmete tipa $X$ in predmete tipa $Y$
v določenem zaporedju $P$,
v studio pa po vrsti prihajajo potencialni kupci.
Organizatorji vnaprej določijo zaporedje kupcev
in $i$-temu kupcu določijo tudi tip predmeta $T_i$.
Kupec $i$ lahko sam poda le ceno $c_i$,
ki jo je pripravljen plačati za predmet.
Organizatorji na podlagi tega določijo zaporedje $P$ tako,
da je izvedljiva prodaja vseh predmetov v zaporedju $P$.
Podatkov $P$, $T$ in $c$ igralec seveda ne pozna vnaprej.
Kupci prihajajo v studio in igralec se odloča,
ali jim za ponujeno ceno trenutni predmet proda ali ne.
Pri tem mu svetuje in vpliva na njegov humanitarni čut
znani voditelj Joras Š.
Če igralec trenutnega predmeta ne proda $i$-temu kupcu,
pride naslednji kupec, če pa ga proda,
pa prisluži za humanitarne namene $c_i$ enot denarja
in naslednjemu kupcu poskusi prodati naslednji predmet v zaporedju $P$.
V sezoni zmaga igralec,
katerega prodaja je procentualno največja glede na optimalno prodajo.
Na HOP.tv so na žalost kupili
le okrnjeno licenco za igro Prodajalec\texttrademark,
ki ne vključuje programske opreme za preračun optimalnih rešitev,
tako da te prosijo za pomoč.
Za primer: če so podatki $T = XYXXY$, $c = (2, 2, 7, 1, 1)$ in $P = XY$,
je optimalna rešitev prodaja $X$ tretjemu kupcu ter prodaja $Y$ petemu kupcu,
s katero prislužimo $c_3 + c_5 = 7 + 1 = 8$ enot denarja.

\begin{enumerate}[(a)]
\item S pomočjo dinamičnega programiranja izpelji algoritem,
ki za dane $T$, $c$ in $P$ poišče optimalno rešitev.
Podaj ustrezno rekurzivno zvezo ter opiši,
kako rekonstruiramo optimalno rešitev.
\namig{zgleduj se po algoritmu za najdaljše skupno podzaporedje.}

\item Kakšna je časovna zahtevnost tvojega algoritma v najslabšem primeru?

\item Izvedi algoritem na zgornjih podatkih in tako preveri,
da je opisana rešitev v zgornjem primeru res optimalna.
\end{enumerate}
\end{vprasanje}

\begin{odgovor}
\begin{enumerate}[(a)]
\item Denimo, da imamo $n$ kupcev in $m$ predmetov ($m \le n$).
Naj bo $v_{ij}$ največja vsota,
ki si jo lahko prislužimo s prodajo prvih $i$ predmetov prvim $j$ kupcem.
Zapišimo začetne pogoje in rekurzivne enačbe.
\begin{align*}
v_{0j} &= 0 &&\quad (1 \le j \le n) \\
v_{i,i-1} &= v_{i-1,i-1} &&\quad (1 \le i \le m) \\
v_{ij} &= \max\left(\{v_{i,j-1}\} \cup \set{v_{i-1,j-1} + c_j}{T_j = P_i}\right)
&&\quad (0 \le i \le m, i \le j \le n)
\end{align*}
Vrednosti $v_{ij}$ računamo v leksikografskem vrstnem redu
glede na indeksa $(i, j)$.
Največji zaslužek dobimo kot $v^* = v_{mn}$.
Optimalno rešitev rekonstruiramo tako,
da za vsak $j = n, n-1, \dots, 1$
in trenutno vrednost $i$ z začetno vrednostjo $i = m$ preverimo,
ali velja $v_{ij} = v_{i,j-1}$
-- če to velja, potem $i$-tega predmeta nismo prodali $i$-temu kupcu,
sicer pa smo ga in vrednost $i$ zmanjšamo za $1$.

\item Algoritem izračuna $\sum_{i=1}^m (n-i+1)$ vrednosti $v_{ij}$,
vsak izračun pa opravi v konstantnem času.
Ker za rekonstrukcijo rešitve potrebuje $n$ korakov,
je skupna časovna zahtevnost $O(mn)$.

\item Izračunajmo vrednosti $v_{ij}$ ($1 \le i \le 2, i \le j \le 5$).
\begin{alignat*}{2}
v_{11} &= \max\{0, \underline{0+2}\} &&= 2 \\
v_{12} &&&= 2 \\
v_{13} &= \max\{2, \underline{0+7}\} &&= 7 \\
v_{14} &= \max\{\underline{7}, 0+1\} &&= 7 \\
v_{15} &&&= 7 \\
v_{22} &= \max\{2, \underline{2+2}\} &&= 4 \\
v_{23} &&&= 4 \\
v_{24} &&&= 4 \\
v_{25} &= \max\{4, \underline{7+1}\} &&= 8
\end{alignat*}
Igralec lahko torej prisluži največ $v^* = v_{25} = 8$ enot denarja.
Rekonstruirajmo še optimalno rešitev.
\begin{align*}
v_{25} &= v_{14} + c_5 & \text{drugi predmet prodamo petemu kupcu} \\
v_{14} &= v_{13} = v_{12} + c_3 & \text{prvi predmet prodamo tretjemu kupcu}
\end{align*}
\end{enumerate}
\end{odgovor}
\end{naloga}
