\documentclass{bschlangaul-aufgabe}

\begin{document}
\bAufgabenMetadaten{
  Titel = {Aufgabe 6},
  Thematik = {Wäscheleinenaufgabe},
  Referenz = 66115-2009-H.T2-A6,
  RelativerPfad = Examen/66115/2009/09/Thema-2/Aufgabe-6.tex,
  ZitatSchluessel = examen:66115:2009:09,
  ZitatBeschreibung = {Seite 6},
  BearbeitungsStand = nur Angabe,
  Korrektheit = unbekannt,
  Ueberprueft = {unbekannt},
  Stichwoerter = {Greedy-Algorithmus},
  EinzelpruefungsNr = 66115,
  Jahr = 2009,
  Monat = 09,
  ThemaNr = 2,
  AufgabeNr = 6,
}

Die Wäscheleinenaufgabe besteht darin, n Wäschestücke der Breiten bı,
ba,...,b„ auf Wäscheleinen der Breite b aufzuhängen. Idealerweise sollte
die Zahl der benutzten Leinen möglichst klein werden. Formal ist eine
Aufhängung der Wäsche auf ! Leinen also eine Einteilung der Menge
(1,...,n) in I! Klassen Lı,...,L,, sodass für alle j = 1...1 gilt Vier,
b; < b. Eine Lösung der Wäscheleinenaufgabe ist dann eine Zahl ! und
eine Aufhängung der Wäsche auf ! Leinen. Eine Lösung ist umso besser, je
kleiner / ist.\index{Greedy-Algorithmus}
\footcite[Seite 6]{examen:66115:2009:09}

\begin{enumerate}

%%
% a)
%%

\item Beschreiben Sie einen sinnvollen Greedy-Algorithmus für das
Wäscheleinenproblem. (Also nicht einfach für jedes Wäschestück eine neue
Leine)

%%
% b)
%%

\item Geben Sie ein Beispiel einer Wäscheladung (Instanz des
Wäscheleinenproblems), für die Ihr Algorithmus mehr als die minimal
mögliche Zahl von Leinen verbraucht.

%%
% c)
%%

\item Nennen Sie ein Beispiel einer Problemstellung, die mit einem
Greedy-Algorithmus optimal gelöst werden kann.

\end{enumerate}

\end{document}