\documentclass{bschlangaul-aufgabe}
\bLadePakete{java,mathe,komplexitaetstheorie,pseudo}
\begin{document}
\bAufgabenMetadaten{
  Titel = {Aufgabe 4},
  Thematik = {Gutschein},
  Referenz = 66115-2020-H.T2-TA2-A4,
  RelativerPfad = Examen/66115/2020/09/Thema-2/Teilaufgabe-2/Aufgabe-4.tex,
  ZitatSchluessel = examen:66115:2020:09,
  BearbeitungsStand = mit Lösung,
  Korrektheit = unbekannt,
  Ueberprueft = {unbekannt},
  Stichwoerter = {Dynamische Programmierung},
  EinzelpruefungsNr = 66115,
  Jahr = 2020,
  Monat = 09,
  ThemaNr = 2,
  TeilaufgabeNr = 2,
  AufgabeNr = 4,
}

Das GUTSCHEIN-Problem ist gegeben durch eine Folge $w_1, \dots, w_n$ von
Warenwerten (wobei $w \in N_0$ für $i = 1, \dots, n$ ) und einem
Gutscheinbetrag $G \in \mathbb{N}_0$.
\index{Dynamische Programmierung}
\footcite{examen:66115:2020:09}

Da Gutscheine nicht in Bargeld ausgezahlt werden können, ist die Frage,
ob man eine Teilfolge der Waren findet, sodass man genau den Gutschein
ausnutzt. Formal ist dies die Frage, ob es eine Menge von Indizes $I$
mit $I \subseteq \{1, \dots, n \}$ gibt, sodass $\sum_{i \in I} w_i = G$

\begin{bExkurs}[Teilsummenproblem]
\bProblemSubsetSum
\end{bExkurs}

\begin{enumerate}

%%
% a)
%%

\item Sei $w_1 = 10, w_2 = 30, w_3 = 40, w_4 = 20, w_5 = 15$ eine Folge
von Warenwerten.

\begin{enumerate}

%%
% (ii)
%%

\item Geben Sie einen Gutscheinbetrag $40 < G < 115$ an, sodass die
GUT\-SCHEIN-Instanz eine Lösung hat. Geben Sie auch die lösende Menge $I
\subseteq \{ 1, 2, 3, 4, 5 \}$ von Indizes an.

\begin{bAntwort}
$50$

$I = \{ 1, 3 \}$
\end{bAntwort}

%%
% (ii)
%%

\item Geben Sie einen Gutscheinbetrag $G$ mit $40 < G < 115$ an, sodass
die GUTSCHEIN-Instanz keine Lösung hat.

\begin{bAntwort}
$51$
\end{bAntwort}

\end{enumerate}

%%
% b)
%%

\item Sei \emph{table} eine $(n \times (G + 1))$-Tabelle mit Einträgen
$\text{table}[i,k]$, für $1 \leq i \leq n$ und $0 \leq k \leq G$, sodass

\begin{equation*}
\text{table}[i,k] =
\begin{cases}
\textbf{true} &
\text{falls es } I \subseteq \{1, \dots, n \} \text{ mit }
\sum_{i \in I} w_i = G \text{ gibt}\\

\textbf{false} & \text{sonst}
\end{cases}
\end{equation*}

Geben Sie einen Algorithmus in Pseudo-Code oder Java an, der die Tabelle
\emph{table} mit \emph{dynamischer Programmierung} in
Worst-Case-Laufzeit $\mathcal{O}(n \times G)$) erzeugt. Begründen Sie
die Korrektheit und die Laufzeit Ihres Algorithmus. Welcher Eintrag in
\emph{table} löst das GUTSCHEIN-Problem?

\begin{bAntwort}
\begin{algorithm}[H]
\newcommand{\meinkommentar}[1]{\texttt{\scriptsize #1}}
\SetCommentSty{meinkommentar}

table = boolean array $n + 1 \times (G +  1)$
\tcp*{Initialisiere ein boolsches Feld mit $n + 1$ Zeilen für jeden
  Warenwert und 0 für keinen Warenwert und mit
  $G + 1$ Spalten für alle Gutscheinbetrag bis $G$ und $0$ für keinen Gutscheinbetrag}

\bigskip

\For(\tcp*{Wenn der Gutscheinbetrag größer als $0$ ist und es keine
     Warenwerte gibt, \dh $n = 0$, kann der Gutschein nicht eingelöst
     werden.}){$k$ in $1 \dots G$}{
  $\text{table}[0][k] = \text{false}$
}

\bigskip

\For(\tcp*{Ist der Gutscheinbetrag $0$, dann kann er immer eingelöst werden.}){$i$ in $0 \dots n$}{
  $\text{table}[i][0] = \text{true}$
}

\For(\tcp*{Durchlaufe jede Zeile der Warenwerte}){$i$ in $1 \dots n$}{
  \For(\tcp*{Durchlaufe jede Spalte der Gutscheinbeträge in dieser Zeile}){$k$ in $1 \dots G$}{
    $\text{table}[i][k] = \text{table}[i - 1][k]$
    \tcp*[r]{Übernehme erstmals das Ergebnis der Zelle der vorhergehenden
             Zeile in der gleichen Spalte}

    \If(\tcp*{Wenn der aktuelle Gutscheinbetrag größer als der aktuelle
              Warenwert und die aktuelle Zelle noch nicht als wahr
              markiert ist}){$k \geq w_i$ und $\text{table}[i][k]$ noch nicht markiert}{
      $\text{table}[i][k] = \text{table}[i - 1][k - w_i]$
      \tcp*{übernimmt das Ergebnis des aktuellen Gutscheinbetrags
            minus des aktuellen Warenwerts};
    }
  }
}
\caption{Gutschein-Problem}
\end{algorithm}

\bJavaExamen{66115}{2020}{09}{Gutschein}

Die äußere for-Schleife läuft $n$ mal und die innere for-Schleife $G$ mal.

Der letzte Eintrag in der Tabelle, also der Wert in der Zelle
\bJavaCode{table[W.length][G]}, löst das Gutscheinproblem. Steht hier
\bJavaCode{true}, dann gibt es eine Teilfolge der Waren, die den
Gutscheinbetrag genau ausnutzt.

\end{bAntwort}
\begin{bAdditum}[Test-Klasse]

\bJavaTestDatei{examen/examen_66115/jahr_2020/herbst/GutscheinTest}

\begin{itemize}
\item \bJavaCode{gutscheinDP(3, new int[] { 1, 2, 3 }));}: wahr (w)

\begin{minted}{md}
[
  [w, f, f, f],
  [w, w, f, f],
  [w, w, w, w],
  [w, w, w, w]
]
\end{minted}

\item \bJavaCode{gutscheinDP(7, new int[] { 1, 2, 3 });}: falsch (f)

\begin{minted}{md}
[   0  1  2  3  4  5  6  7 G
 0 [w, f, f, f, f, f, f, f],
 1 [w, w, f, f, f, f, f, f],
 2 [w, w, w, w, f, f, f, f],
 3 [w, w, w, w, w, w, w, f]
 W
]
\end{minted}

\item \bJavaCode{gutscheinDP(10, new int[] { 10, 30, 40, 20, 15 });}: wahr (w)

\begin{minted}{md}
[    0  1  2  3  4  5  6  7  8  9  10 G
 0  [w, f, f, f, f, f, f, f, f, f, f],
 10 [w, f, f, f, f, f, f, f, f, f, w],
 30 [w, f, f, f, f, f, f, f, f, f, w],
 40 [w, f, f, f, f, f, f, f, f, f, w],
 20 [w, f, f, f, f, f, f, f, f, f, w],
 15 [w, f, f, f, f, f, f, f, f, f, w]
 W
]
\end{minted}
\end{itemize}

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