Aufgabe:
(optimales Wechselgeld). Ein Kassierer benutzt folgende Greedy-Strategie, um Münz-Wechselgeld herauszugeben. Er nimmt immer die wertvollste Münze aus der Kasse, deren Wert den Rest dessen, was er herausgeben muss, nicht übersteigt. Zum Beispiel gibt er den Betrag \( w=99 \) als \( 1 \times 50+2 \times 20+1 \times 10+1 \times 5+2 \times 2 \) heraus (jeweils Cent).
procedure GierigesWeCHSELGELD \( (w, M) \)
Require: \( 1 \in M \)
// w: herauszugebender Betrag
\( / / M=\left(w_{1}, \ldots, w_{n}\right): \) zur Verfügung stehende Münzwerte, aufsteigend sortiert \( c_{i} \leftarrow 0 \quad(i=1, \ldots, n) / / \) Anzahl der Münzen vom Wert \( w_{i} \)
while \( w>0 \) do
\( \begin{array}{l} j \leftarrow \operatorname{argmax}\left\{1 \leq i \leq n \mid w_{i} \leq w\right\} \\ c_{j} \leftarrow c_{j}+1 \\ w \leftarrow w-w_{j} \end{array} \)
nehme \( c_{i} \) Münzen mit Wert \( w_{i} \) für \( i=1, \ldots, n \)
a) Beweise, dass bei dem Euro-Münzsatz \( M=\left(w_{1}, \ldots, w_{n}\right)=\{1,2,5,10,20,50,100,200\} \) GiERIGESWECHSELGELD die kleinste Anzahl an Münzen ergibt, also dass für das vom Algorithmus ausgegebene \( c \) die Anzahl \( \sum \limits_{i=1}^{n} c_{i} \) minimal ist unter allen Münzauswahlen \( c=\left(c_{1}, \ldots, c_{n}\right) \) mit \( \sum \limits_{i=1}^{n} c_{i} w_{i}=w \).
b) Gebe einen Münzsatz \( M=\left(w_{1}, \ldots, w_{n}\right) \) mit \( w_{1}=1 \) an, bei dem GierigesWECH\( \operatorname{SELGELD}(w, M) \) nicht für alle Beträge \( w \) eine minimale Anzahl von Münzen ermittelt.
Hallo zusammen, könnte mir jemand bitte dabei helfen?
Danke im Voraus!
