\documentclass[a4paper]{article}
\usepackage[cm]{fullpage}
\usepackage[serbian]{babel}
\usepackage[table]{xcolor}
\usepackage{graphicx,amsmath}
\usepackage{bbm}

\def\d{{\fontencoding{T1}\selectfont\dj}}
\def\D{{\fontencoding{T1}\selectfont\DJ}}

\newtheorem{z}{Zadatak}

\title{Blok 2 - Dinami\v{c}ko programiranje}
\date{}

\begin{document}
\maketitle

\emph{Napomena:} U svim narednim zadacima dati rekurzivno re\v{s}enje i re\v{s}enje zasnovano na dinami\v{c}kom programiranju. 

\begin{z}  (10 poena = 4+6) Data je matrica \v{c}iji su elementi celi brojevi razli\v{c}iti od nule. Idu\'{c}i od gornjeg levog ugla i kre\'{c}u\'{c}i se samo jedno polje dole ili desno mo\v{z}e se sti\'{c}i do donjeg desnog ugla matrice $A_{m x n}$ na vi\v{s}e na\v{c}ina. Odrediti barem jednu putanju \v{c}iji je broj promena znaka susednih polja minimalan. \emph{[M\v{C}SM, gl. 17, z. 16]}
\end{z}

\begin{table}[h!]
\centering
\begin{tabular}{|r|r|r|r|r|}
\hline
 \cellcolor{blue!25}3  &-5 &19  &1 &-11 \\ 
\hline
 \cellcolor{blue!25}4 &-15  &6 &14 &17 \\
\hline
\cellcolor{blue!25}13 &13  &-6  &-1  &9  \\ 
\hline
 \cellcolor{blue!25}5  &\cellcolor{blue!25}4  &\cellcolor{blue!25}4 &\cellcolor{blue!25}17 &\cellcolor{blue!25}17 \\
\hline
\end{tabular}
\end{table}

Ako je sa a[i,j] ozna\v{c}eno optimalno re\v{s}enje dolaska do polja (i,j), onda je veza za dinami\v{c}ko programiranje data sa:
\noindent\rotatebox{180}{\vbox{%
\begin{equation}
\nonumber
a[i,j]=\left\{
\begin{array}{ll}
  0 & i=0, j=0\\
  a[0,j-1]+\mathbbm{1}_{sgn([a[0,j-1] a[0,j])<0}&  i=0, j=1,...,n-1\\
a[i-1,0]+\mathbbm{1}_{sgn([a[i-1,0] a[i-1,0])<0}&  j=0, i=1,...,m-1\\
  min\{a[i-1,j]+\mathbbm{1}_{sgn([a[i-1,j] a[i,j])<0},a[i,j-1]+\mathbbm{1}_{sgn([a[i,j-1] a[i,j])<0}\} & i>0, j>0
\end{array}\right.
\end{equation}}%
}
Re\v{s}enje se rekonstrui\v{s}e sli\v{c}no kao kod matrice najmanjih tro\v{s}kova. 

\begin{z}  (10 poena = 4+6) Dat je niz x od N celih brojeva. Na\'ci njegov podniz za koji va\v{z}i da ima najve\'ci zbir elemenata, i pritom ne sadr\v{z}i susedne elemente niza x.  \emph{[SMDVM\DJ, Din. prog. , re\v{s}. z. 2]}. Test primer:

\begin{verbatim}
4 -2 5 2 5 12 23 -23 21 12
4 5 5 23 21
\end{verbatim}

Ako je sa a[k] dato optimalno re\v{s}enje sa najvi\v{s}e k prvih elementa niza, onda je veza za dinami\v{c}ko programiranje:
\noindent\rotatebox{180}{\vbox{%
\begin{equation}
\nonumber
a[k]=\left\{
\begin{array}{ll}
  0 & k=0\\
 max\{0,a[0]\}& k=1\\
 max\{a[k-2]+x[k-1], a[k-1]\} & k>1 \\
\end{array}\right.
\end{equation}}%
}

Re\v{s}enje se rekonstrui\v{s}e sli\v{c}no kao kod problema ranca. 

\end{z}

\begin{z}
(10 poena = 4+6) Dat je niz x od N karaktera, i drugih niz y od M karaktera. Prona\'ci najdu\v{z}i zajedni\v{c}ki podniz z za ta dva niza \emph{[M\v{C}SM, gl. 17, z. 25]}. Test primer:

\begin{verbatim}
a b c d a
a d b a
a b a (ili a d a)
\end{verbatim}

Ako je sa a[i,j] ozna\v{c}ena du\v{z}ina najdu\v{z}eg zajedni\v{c}kog podniza za najvi\v{s}e i prvih karaktera niza x, i najvi\v{s}e j prvih karaktera niza y, onda je veza slede\'ca:

\noindent\rotatebox{180}{\vbox{%
\begin{equation}
\nonumber
a[i,j]=\left\{
\begin{array}{ll}
  0 & i=0 \lor j=0\\
 max\{a[i-1,j], a[i,j-1], a[i-1,j-1]+\mathbbm{1}_{a[i-1,j-1]=a[i,j]}\} & i>0, j>0\\
\end{array}\right.
\end{equation}}%
}

Re\v{s}enje se rekonstrui\v{s}e tako \v{s}to se u formiranoj matrici, tako \v{s}to se prelazi dijagonalno unazada sa a[i,j] na a[i-1,j-1] ako je a[i-1,j-1]$<$a[i,j], ina\v{c}e se ide ulevo na a[i,j-1]. Pri svakom dijagonalnom pomeraju se na izlaz ispi\v{s}e vrednost x[i]. 
\end{z}

\end{document}

