\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 16 bez ograni\v{c}enja. 

\begin{table}[h!]
\centering
    \begin{tabular}{|l|r|r|r|r|r|r|r|r|}
    \hline
    p: & p1 & p2 & p3 & p4 & p5 & p6 & p7 & p8 \\ \hline
    v: & 1 & 2 & 8 & 14 & 6 & 13 & 7 & 10\\ \hline
    x: & 1 & 2.2 & 12 & 15 & 7 & 15 & 8 & 13.5\\ \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 dekadne brojeve ca N cifara  (bez cifre 0), takve da je broj zbir cifara ve\'{c}i od D, a manji od G. Korisnik unosi N, D i G. Nije potrebno \v{c}uvati dekadne brojeve, dovoljno je samo ispisati ih. Test primer (redosled ispisa ne mora biti isti kao u test primeru):
\end{z}

\begin{verbatim}
3 10 20
119
129
139
...
\end{verbatim}

\begin{z}
Edit rastojanje za data dve re\v{c}i x i y, predstavlja najmanji broj operacija izmene, brisanja ili dodavanja slova, koji od prve re\v{c}i drugu. Npr., za re\v{c}i x=\emph{"tekst"} i y=\emph{"test"} edit rastojanje je 1, zato \v{s}to je potrebno samo ukloniti slovo k iz prve re\v{c}i. Za re\v{c}i x=\emph{"formirati"} i y=\emph{"normiran"}, edit rastojanje se zasniva na zamenama $f \rightarrow n$, $t \rightarrow n$, i brisanja slova i iz prve re\v{c}i, tako da je edit rastojanje 3. Napisati program koji: a) nalazi edit rastojanje dinami\v{c}kim programiranje (13 poena) i b) rekurzivno (12 poena). 

Ako sa a[i,j] ozna\v{c}imo edit rastojanje za prvih i slova prve re\v{c}i i prvih j slova druge re\v{c}i, 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,j]=\left\{
\begin{array}{ll}
  j, &  i=0\\
  i, & j=0\\
  min\{a[i,j-1]+1, a[i-1,j]+1, a[i-1,j-1]+\mathbbm{1}_{x[i]=y[j]} \}, & i>0, j>0\\
\end{array}\right.
\end{equation}

Test primer:

\begin{table}[h!]
\centering
    \begin{tabular}{|c|ccccccccccc|}
    \hline
     &  & P & O & L & Y & N & O & M & I & A & L \\ \hline
     & 0 & 1  & 2  & 3  & 4  & 5  & 6  & 7  & 8  & 9  & 10  \\
     E& 1 & 1  & 2  & 3  & 4  & 5  & 6  & 7  & 8  & 9  & 10 \\
     X&  2& 2  & 2  & 3  & 4  & 5  & 6  & 7  & 8  & 9  & 10 \\
     P&  3&  2 &3   &3   &4   &5   &6   & 7  & 8  & 9  &  10\\
     O& 4 & 3  & 2  & 3  & 4  & 5  & 5  & 6  & 7  & 8  & 9 \\
     N&  5&  4 & 3  & 3  & 4  & 4  & 5  & 6  & 7  & 8  & 9 \\
     E&  6& 5  & 4  & 4  & 4  &  5 & 5  & 6  & 7  &8   &9  \\
     N& 7 & 6  & 5  & 5  & 5  & 4  & 5  & 6  & 7  & 8  & 9 \\
     T&  8& 7  & 6  & 6  & 6  & 5 & 5  & 6  &  7 & 8  & 9 \\
     I&  9&  8 &  7 & 7  & 7  &  6 & 6  & 6  & 6  & 7  & 8 \\
     A& 10 & 9  & 8  & 8  & 8  & 7  & 7  & 7  &7   &6   &7  \\
     L&  11&  10 &  9 &  8 & 9  & 8  & 8  & 8  &   8&  7 & 6 \\
     \hline 
    \end{tabular}
\end{table}

\end{z}

\end{document}

