\frametitle <presentation>{Entwurf einer L"osung f"ur das Rucksackproblem}

\begin{semiverbatim}\mode<presentation>{int \underline{sack} (int cap) \{
\uncover<1->{   int i, space, max, }\uncover<2->{\alert<2>{max_i}, }\uncover<1->{t;}
\uncover<1->{   if (maxKnown[cap] != UNSET) return maxKnown[cap];}
\uncover<1->{      for (i = 0, max = 0; i < N; i++)}
\uncover<1->{         if ((space = cap - items[i].size) >= 0)}
\uncover<1->{            if ((t = \underline{sack}(space) + items[i].val) > max) \{}
\uncover<1->{               max = t; }\uncover<2->{\alert<2>{max_i = i;}}
\uncover<1->{         \}}
\uncover<1->{   maxKnown[cap] = max; }\uncover<3->{\alert<3>{itemKnown[cap] = items[max_i];}}
\uncover<1->{   return max;}
\uncover<1->{\}} } \end{semiverbatim}

\mode<article>{
\vspace{-0.6cm}
Die Speicherung der gew"ahlten Gegenst"ande wurde in
\lstlistingname ~\ref{knapsack_dp} bereits stillschweigend
implementiert. Hierzu wurde zus"atzlich das Array \texttt{itemKnown}
angelegt (Zeile~5) und nach jeder Auswahl zus"atzlich zum Wert auch der
gerade selektierte Gegenstand gespeichert (Zeile~17).
}