---

Geschrieben von FFlex am 14.05.2007 um 19:09:

  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

---

Geschrieben von Tobias am 14.05.2007 um 22:30:

 

Ein Matroid ist ein Tupel (E, U) mit endlicher Menge E und einem System aus Teilmengen U.

Daher musst du erstmal sagen was E und was U ist.

---

Geschrieben von FFlex am 14.05.2007 um 23:46:

 

Da fängt das Problem ja schon an, ich hab keine Ahnung.

---

Geschrieben von Tobias am 15.05.2007 um 01:06:

 

Ist das Problem auf die feste Zahl 15 begrenzt oder steht die 15 exemplarisch für eine beliebige Zahl n?

---

Geschrieben von FFlex am 15.05.2007 um 10:27:

 

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)