# Greedy: Austauschargument Beispiel
Diese Aufgabe ist bewusst einfach gehalten und soll eher saubere Beweisführung als Problemlösen vermitteln.

## Aufgabe: Schönschrift
Ein anonymer Tutor S.$^1$ wurde von seiner Gruppe wegen seiner Handschrift gerügt. Leider wurde der 2-Wochen-Intensiv-Schönschreibkurs wegen Corona abgesagt und S. braucht dringend Hilfe. Zum Glück sind seine Studis alle chronisch arm und lassen sich durch eine offensichtlich versteckte Nachricht in einer Aufgabe, die ihnen Schwarz-Anstellung und Bezahlung weit unter Mindestlohn verspricht, zu Angeboten ihrerseits hinreißen, sich als Diktier-Minion zu versklaven. Alle Studis geben S. ein Angebot, wie viel Geld sie pro Stunde für die Diktierarbeiten nehmen würden und wie viele Stunden sie pro Woche maximal arbeiten können (glücklicherweise haben Studis nichts anderes zu tun und sind ansonsten unbeschränkt in ihrem Einsatz als Minion). S. braucht für insgesamt $n$ Stunden ein Diktierminion, welches in der Zeit aber auch wechseln kann. Durch sein kluges Marketing ist es S. immer möglich genug Minions zu finden. Gegeben die Angebote der Studis, gib an, welche Angebote zu welchen Stundenzahlen S. annehmen sollte, um für möglichst wenig Geld Diktierminions zu bekommen.

## Lösung
Eingabe: Zeitbedarf $n$ in Stunden für Diktierminions, Liste A von Angeboten über $\mathbb{N}^2$, wobei für $(g, h) \in A$ der Wert $g$ den Stundenlohn und $h$ die maximale Stundenzahl darstellt

Ausgabe: Liste $L$, wobei für $(A', t) \in L$ der Wert $A'$ einem Angebot aus $A$ gleicht und $t$ die Anzahl an bezahlten Stunden für dieses Angebot entspricht

Korrektheitsbedingung: Für alle $(A', t) \in L$ mit $A' = (g,h)$ gilt $t \leq h$, alle Studis werden maximal so lange beschäftigt wie angeboten. Außerdem gilt $\sum_{(k, t) \in L}t$ ist mindestens $n$, durch die Auswahl an Angeboten kann für $n$ Stunden ein Minion gefunden werden.

Für alle Lösungen $L'$, die die obige Bedingung erfüllen gilt außerdem $$ \sum_{(k', t') \in L'}t'k' \geq \sum_{(k, t) \in L}tk, $$ die benötigten Kosten sind unter allen validen Lösungen minimal.

---
Algorithmusidee: Wir wählen greedy die Angebote mit geringsten Stundenlohn, bis wir $n$ Stunden abdecken können.

Algorithmus: Wir sortieren die Liste $A$ aufsteigend nach Stundenlohn. Wir erstellen unsere Ausgabeliste $L$ und merken uns die Anzahl an Stunden $s$, die die Angebote aus $L$ abdecken. Wir fügen solange das erste Angebot aus $A$ in unsere Lösung $L$ ein, bis wir mindestens $n$ Stunden überdecken. Dabei wird ein Angebot $(g,h)$ jeweils mit $\min(s, h)$ Stunden in $L$ eingefügt. Sind $n$ Stunden überdeckt, geben wir $L$ aus.

Korrektheitsbeweis: Wir fügen jedes Angebot $(g,h)$ nur mit maximal $h$ Stunden in unsere Ausgabeliste ein, somit beschäftigen wir alle Studis maximal so lange wie angeboten. Außerdem hören wir mit unserem Algorithmus erst auf, wenn wir $n$ Stunden überdecken konnten. Da dies nach Aufgabenstellung immer möglich ist, ist auch diese Eigenschaft gegeben.

Sei $L$ unsere Ausgabe und $O$ die Ausgabe einer optimalen Lösung. Wir wandeln für den Beweis die Listen $L$ und $O$ in $L', O'$ um, indem wir für jedes Ausgabeelement $(a, t) \in L$ (analog mit $O$) mit $a=(g,h)$ das Element $g$ genau $t$ mal in die Liste $L'$ einfügen. Wir verändern somit die Ausgabelisten zu Listen aus Zahlen. Da wir hierbei lediglich das Produkt aus Stundenlohn und Arbeitsstunden auffächern, bleiben die Kosten der Lösung gleich.
Außerdem muss $|L'| = |O'| = n$ gelten, da alle Angebote positive Kosten haben und man somit ein Element aus $L'$ oder $O'$ entfernen kann (wodurch die Kosten sinken), sollten diese mehr als $n$ Elemente haben.

Wir zeigen per Austauschargument, dass $L'$ nicht höhere Kosten hat als $O'$. Dazu sortieren wir beide Lösungen $L'$ und $O'$ aufsteigend. Sei $O'_i$ eine Lösung, die für die ersten $i$ Elemente gleich ist wie $L'$ und ansonsten $O'$ gleicht. Wir zeigen induktiv, dass für alle $i \in \mathbb{N}$ die Lösung $O'_i$ nicht höhere Kosten hat als $O'$.
IA: Für $i = 0$ gilt dies offensichtlich, da $O' = O'_0$.
IS: Gelte die Aussage nun für ein $i \in N$ (IV). Sei $e$ das $i+1$-te Element aus $L$ und $e'$ das entsprechende Element aus $O$.
Fall 1: Gelte $e = e'$, so ist $O'_{i+1} = O'_i$. Nach Induktionsvoraussetzung hat somit $O'_{i+1}$ auch nicht höhere Kosten als $O$.
Fall 2: Gelte $e \neq e'$. Unser Algorithmus wählt immer die Angebote mit niedrigsten Stundenlohn solange nicht alle Stunden überdeckt sind, somit muss $e < e'$ gelten, da wir ansonsten das Angebot mit Kosten $e'$ hätten wahrnehmen können. Somit hat $O'_{i+1}$ echt niedrigere Kosten als $O'_i$ und nach IV auch als $O'$.

Da $O'_{|L'|} = L'$ ist, hat $L'$ nicht höhere Kosten als eine optimale Lösung und ist somit selbst optimal.

---

$^1$ Anmerkung: Der Gebrauch des Maskulins im Text ist rein zufällig. Dies hat nichts mit echten Personen oder Gegebenheiten zu tun.