Aufgabe 3
b)

Eine optimale Lösung zeichnet sich dadurch aus, dass folgende Münzen höchstens in folgendem Verhältnis vorkommen:

1 * (1, 5, 10, 50, 100)
2 * (2, 20)
x * (200)

Wenn in jedem Fall das maximale Vorkommen eingehalten wird, ist der Algorithmus optimal.

Der Algorithmus operiert wie folgt:

n = Centbetrag, der gewechselt werden soll.

1. Schritt:
Falls n>=200, wende n=n-200 solange an, bis n<200.

wir erhalten x*200 als Wechselgeld, dies erfüllt unser Kriterium.

Falls n jetzt zweistellig ist, springe zu Schritt 2.
Falls n jetzt einstellig ist, springe zu Schritt 3.
Falls n jetzt nullstellig, sind wir fertig.

2. Schritt:
p = zweite Stelle von n:
			p=9 => 50, 20, 20
			p=8 => 50, 20, 10
			p=7 => 50, 20
			p=6 => 50, 10
			p=5 => 50
			p=4 => 20, 20
			p=3 => 20, 10
			p=2 => 20
			p=1 => 10
Daraufhin wird die zweite Stelle null.
Falls n einstellig ist, springe zu Schritt 3.
Falls n nullstellig ist, sind wir fertig.

3.Schritt
t = erste Stelle von n:
			t=9 => 5, 2, 2
			t=8 => 5, 2, 1
			t=7 => 5, 2
			t=6 => 5, 1
			t=5 => 5
			t=4 => 2, 2
			t=3 => 2, 1
			t=2 => 2
			t=1 => 1
Daraufhin sind wir fertig.

Wie wir sehen, ist egal welchen Centbetrag wir wechseln müssen, das Kriterium für die optimale Lösung erfüllt.