 Thema: Matroidstruktur bei Münzen |
|
|
Ne, hab 15 nur genommen, weil da deutlich wird, daß Greedy für Beispiel 2 nicht-optimale Lösungen liefert. Würde man zum Beispiel 10 nehmen, würde der Greedy Algoritmus ja auch für Bsp. 2 ein optimales Ergebnis liefern. (5+5=>2 Münzen)
|
|
| Thema: Matroidstruktur bei Münzen |
|
|
Hi!
Es geht um folgendes:
Unser Münzgeld hat die Wertigkeiten 1,2,5,10. Möchte man mit diesen Münzen den Wert 15 bilden, so schafft man dies mit möglichst wenig Münzen, indem man immer die größtmögliche Münze so oft wie möglich nimmt (Greedy-Algorithmus). Hier also: 10+5=>2 Münzen.
Hat man andere Münzen, z.B. 1,5,11 und will 15 bilden, so liefert der Greedy-Algorithmus: 11+1+1+1+1=>5 Münzen. Optimal wäre aber 5+5+5=> 3 Münzen.
Dies liegt daran, daß der Greedy Algorithmus nur auf Matroiden (wie in Beispiel1) optimale Lösungen liefert.
Nun meine Frage:
Kann mir jemand erklären, warum {1,2,5,10} ein Matroid ist, {1,5,11} jedoch nicht? Also wie läßt sich die Definition eines Matroids auf diese Münzmengen anwenden? 
Vielen Dank im Voraus,
FFlex
|
|
|
