\documentclass{article}

\usepackage{amsthm}
\newtheorem{thm}{Teorema}

\title{Nedelja 5 - Problem ranca i problem najkra\'ceg puta izmedju dva grada}

\begin{document}
\maketitle

\begin{enumerate}

\item Problem ranca je definisan na slede\'ci na\v{c}in. Dato je N vrsta predmeta \v{c}ije su zapremine prirodni brojevi dati nizom v, a vrednosti predmeta nizom x. Kreirati metod koijm se popunjava ranac kapaciteta $c > 0$. Ne sme se pre\'{c}i kapacitet, a potrebno je da vrednost predmeta u rancu bude masimalna. Pritom razmotriti samo slu\v{c}aj da predmeta svake vrste ima neograni\v{c}eno (postoji i varijanta problema gde je broj predmeta svake vrste ograni\v{c}en). Test primer:

\begin{table}[h!]
\centering
    \begin{tabular}{|l|l|l|l|l|l|l|l|}
    \hline
    p: & p1 & p2 & p3 & p4 & p5 & p6 & p7 \\ \hline
    v: & 1 & 2 & 8 & 14 & 6 & 13 & 7 \\ \hline
    x: & 1 & 3 & 15 & 15 & 7 & 15 & 8 \\ \hline
    \end{tabular}
\end{table}

\begin{enumerate}
\item Dati rekurzivno re\v{s}enje problema.
\item Dati re\v{s}enje zasnovano na dinami\v{c}kom programiranju. Logika u slu\v{c}aju
dinami\v{c}kog programiranja je slede\'ca. Najpre pokazujemo da sme da se primeni dinami\v{c}ko
programiranje. Da bi moglo da se primeni, mora da va\v{z}i da je optimalno re\v{s}enje
sa\v{c}injeno iz optimalnih re\v{s}enja manjih problema (potproblema).
\begin{thm}
Neka je P skup predmeta koji predstavljaju optimalno re\v{s}enje za zadati kapacitet c. Ukoliko iz tog skupa izvadimo predmet p \v{c}ija je zapremina data sa v, a cena sa x, onda \'ce P$\setminus${p} biti optimalno re\v{s}enje za problem ranca kapaciteta c-x. 
\end{thm}
\begin{proof}[Dokaz]
Pretpostavimo suprotno tvrdjenju, naime, da za kapacitet c-x postoji re\v{s}enje Q koje ima ve\'cu vrednost od re\v{s}enja P$\setminus${p}. Tada je skup Q $\cup$ {p} po kapacitetu manji ili jednak od c, a njegova vrednost je ve\'ca od vrednosti skupa predmeta P, \v{s}to je nemogu\'ce jer je P optimalno re\v{s}enje za kapacitet c. Kontradikcija.
\end{proof}

Veza izmedju re\v{s}enja problema manjih i ve\'cih dimenzija je slede\'ca (sa a[c] je obele\v{z}eno optimalno re\v{s}enje za kapacitet c):

\begin{equation}
\nonumber
a[c]=\left\{
\begin{array}{ll}
  0 &  c=0\\
  max\{a[c-v[i]]+x[i]\}, i=1,...,N, v[i]\leq c & c>0
\end{array}\right.
\end{equation}

Re\v{s}imo problem za dimenziju ranca 10 i prethodno dat spisak predmeta. Postupak je da se re\v{s}ava za sve kapacitete po\v{c}ev od kapaciteta 0. Za svaki kapacitet pamtimo samo predmet koji smo dodali poslednji dodali tako da maksimizuje gornji izraz. Ovo \'ce biti dovoljno da se kasnije rekonstrui\v{s}e re\v{s}enje problema:

\begin{table}[h!]
\centering
    \begin{tabular}{|l|l|l|l|l|l|l|l|l|l|l|l|}
    \hline
    c: & 0 & 1  & 2   & 3   & 4    & 5   & 6   & 7  & 8   & 9   & 10\\ \hline
    p: & - & p1 & p2 & p1 & p2 & p1 & p2 & p1 & p3& p1& p2\\ \hline
    v: & 0 & 1  & 2   & 3   & 4   & 5   & 6    & 7  & 8  &  9 &  10 \\ \hline
    x: & 0 & 1  & 3   & 4   & 6   &  7  & 9    & 10 &15& 16&  18 \\ \hline
    \end{tabular}
\end{table}

Zaklju\v{c}ujemo da optimalno re\v{s}enje ima ukupnu cenu 18, a re\v{s}enje rekonstrui\v{s}emo tako \v{s}to \v{c}itamo predmete unazad. Poslednji predmet je p2, \v{s}to zna\v{c}i da kada izbacimo taj predmet, problem svodimo na kapacitet c=8. Onda \v{c}itamo optimalno re\v{s}enje za c=8, u pitanju je predmet p3. Njega izbacujemo, pa se problem svodi na c=0. Kako je re\v{s}enje za c=0 prazan skup, zavr\v{s}ili smo, pa konstatujemo da je re\v{s}enje skup predmeta \{p2,p3\}. Test primer:

\begin{table}[h!]
\centering
    \begin{tabular}{|l|l|l|l|l|l|l|}
    \hline
      & g1 & g2 & g3 & g4 & g5 & g6 \\ \hline
    g1 & 0  & 7  & 9  & $\infty$  & $\infty$  & 14 \\ \hline
    g2 &   & 0  & 10 & 15 & $\infty$  & $\infty$  \\ \hline
    g3 &   &   & 0  & 11 & $\infty$  & 2  \\ \hline
    g4 &   &   &   & 0  & 6  & $\infty$  \\ \hline
    g5 &   &   &   &   & 0  & 9  \\ \hline
    g6 &   &   &   &   &   & 0  \\ \hline
    \end{tabular}
\end{table}

\end{enumerate}

\item Problem najkra\'ceg puta izmedju dva grada je definisan na slede\'ci na\v{c}in. Dato je N gradova ozna\v{c}enih sa g1,...,gN. 
Udaljenosti izmedju svaka dva grada su data matricom rastojanja D (rastojanje izmedju grada gi i gj je dato sa D(i,j)=D(j,i)). Za odabrana dva grada gx i gy potrebno je na\'ci najkra\'cu putanju izmedju njih. Re\v{s}enje problema podrazumeva spisak gradova kroz koje se prolazi na tom putu. 

\begin{enumerate}
\item Dati rekurzivno re\v{s}enje problema. 
\item Dati re\v{s}enje zasnovano na dinami\v{c}kom programiranju (u ovom re\v{s}enju \'ce se besplatno dobiti i putevi izmedju polaznog grada i svih ostalih). 
\begin{thm}
Neka je P optimalni put predstavljen nizom gradova koji se prolaze izmedju grada gx i gy. Posmatrajmo neki grad gz koji se nalazi na optimalnoj putanji. Obele\v{z}imo sa P1 deo optimalne putanje izmedju gx i gz, a sa P2 deo optimalne putanje izmedju gz i gy. Tvrdimo da je P1 najkraci (optimalni put) za gradove gx i gz.
\end{thm}
\begin{proof}[Dokaz]
Pretpostavimo suprotno tvrdjenju, naime, da za gradove gx i gz postoji put Q koji je kra\'c{c}i. Jasno je da bi onda put Q+P2$<$P, \v{s}to je nemogu\'ce jer je P optimalni put.  Kontradikcija.
\end{proof}

Prethodno tvrdjenje mo\v{z}emo i namerno malo "oslabiti", i za grad gz uvek uzimati samo direktne susede grada gy. Na osnovu toga dolazimo do slede\'ce relacije (a(x,y) ozna\v{c}ava du\v{z}inu optimalnog puta izmedju gx i gy):

\begin{equation}
\nonumber
a(x,y)=\left\{
\begin{array}{ll}
  0 &  x=y\\
  min\{a(x,z)+D(z,y)\}, z=1,...,N, D(z,y)\neq \infty & x \neq y
\end{array}\right.
\end{equation}

Sada kori\v{s}\'cenjem ove relacije mo\v{z}emo pre\'ci na tabli\v{c}no re\v{s}avanje problema (obja\v{s}njena ideja na \v{c}asu). Ovo je re\v{s}enje za prethodno datu matricu udaljenosti i za polazni grad g1.

\begin{table}[h!]
\centering
    \begin{tabular}{|l|l|l|l|l|l|}
    \hline
    g1 & g2   & g3   & g4    & g5    & g6    \\ \hline
    0  & 7/g1 & 9    & $\infty$     & $\infty$     & 14    \\ \hline
      &     & 9/g1 & 20    & 23    & 11    \\ \hline
      &     &     & 20    & 20    & 11/g3 \\ \hline
     &     &     & 20/g3 & 20    &      \\ \hline
     &     &     &      & 20/g6 &      \\ \hline
    \end{tabular}
\end{table}

\textbf{Napomena:} U cilju pripreme za kontrolni uraditi pod (a) i (b), a takodje uraditi i ru\v{c}nu proceduru nala\v{z}enja najkra\'ceg puta za slede\'cu matricu tro\v{s}kova i polazni \v{c}vor g3. 

\begin{table}[h!]
\centering
    \begin{tabular}{|l|l|l|l|l|l|l|l|l|}
    \hline
    ~  & g1 & g2 & g3 & g4 & g5 & g6 & g7 & g8 \\ \hline
    g1 & 0  & 5  & 8  & 3  & $\infty$  & $\infty$  & 12 & 12 \\ \hline
    g2 & ~  & 0  & $\infty$  & 5  & $\infty$  & 2  & $\infty$  & $\infty$  \\ \hline
    g3 & ~  & ~  & 0  & 7  & $\infty$  & $\infty$  & 13 & $\infty$  \\ \hline
    g4 & ~  & ~  & ~  & 0  & 9  & 6  & $\infty$  & $\infty$  \\ \hline
    g5 & ~  & ~  & ~  & ~  & 0  & $\infty$  & 7  & 23 \\ \hline
    g6 & ~  & ~  & ~  & ~  & ~  & 0  & 4  & $\infty$  \\ \hline
    g7 & ~  & ~  & ~  & ~  & ~  & ~  & 0  & 6  \\ \hline
    g8 & ~  & ~  & ~  & ~  & ~  & ~  & ~  & 0  \\ \hline
    \end{tabular}
\end{table}

\end{enumerate}
\end{enumerate}
\end{document} 
