\documentclass[a4paper]{article}
\usepackage[cm]{fullpage}
\usepackage[serbian]{babel}

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

\newtheorem{z}{Zadatak}

\title{Pismeni zadatak - pretraga sa vra\'canjem i dinami\v{c}ko programiranje}
\date{}

\begin{document}
\maketitle

\emph{Napomena:} Prvi zadatak se radi na papiru, ostali se programiraju u C\#. 

\begin{z} (10 poena) Problem ranca kapaciteta 13 bez ograni\v{c}enja. 

\begin{table}[h!]
\centering
    \begin{tabular}{|l|r|r|r|r|r|r|r|r|r|r|r|}
    \hline
    p: & p1 & p2 & p3 & p4 & p5 & p6 & p7 & p8 & p9 & p10 & p11 \\ \hline
    v: & 1 & 2 & 8 & 14 & 6 & 13 & 7 & 10 & 11 & 3 & 2\\ \hline
    x: & 1 & 2.2 & 12 & 15 & 7 & 15 & 8 & 13.5 & 14.2 & 3.4 & 2.3\\ \hline
    \end{tabular}
\end{table}

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}

\end{z}

\begin{z}  (15 poena) Implementirati program koji gener\v{s}e sve binarne brojeve ca N cifara koji ne sadr\v{z}e dve uzastopne jedinice niti tri uzastopne nule:
\end{z}

\begin{verbatim}
6
010101
001010
010010
...
\end{verbatim}

\begin{z}
Na\'ci najdu\v{z}i strogo rastu\'ci podniz datog niza x. Napisati program koji: a) nalazi edit rastojanje dinami\v{c}kim programiranje (13 poena) i b) rekurzivno (12 poena). 

Ako sa a[i] ozna\v{c}imo du\v{z}inu najdu\v{z}eg rastu\'ceg podniza u okviru prvih i elemenata niza x, onda je relacija izmedju re\v{s}enja problema i potproblema data na slede\'ci na\v{c}in (ova relacija se mo\v{z}e iskoristiti i kod rekurzivnog re\v{s}enja):

\begin{equation}
\nonumber
a[i]=\left\{
\begin{array}{ll}
 0, & i=0\\
  max\{a[j] | j=0,...,i, x[j]<x[i]\}+1, & i>0\\
\end{array}\right.
\end{equation}

Test primer:

\begin{verbatim}
6 2 1 3 7 3 7 2 4 5 7 3 19 6
2 3 4 5 7 19 (ili 1 2 4 5 7 19)
\end{verbatim}

\end{z}

\end{document}

