Matroidstruktur bei Münzen |
| 14.05.2007, 19:09 | Auf diesen Beitrag antworten » |
| FFlex | 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 |
|
|
|
| 14.05.2007, 22:30 | Auf diesen Beitrag antworten » |
| Tobias | 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. |
| 14.05.2007, 23:46 | Auf diesen Beitrag antworten » |
| FFlex | Da fängt das Problem ja schon an, ich hab keine Ahnung. 
|
| 15.05.2007, 01:06 | Auf diesen Beitrag antworten » |
| Tobias | Ist das Problem auf die feste Zahl 15 begrenzt oder steht die 15 exemplarisch für eine beliebige Zahl n? |
| Anzeige | |
|
|
|
| 15.05.2007, 10:27 | Auf diesen Beitrag antworten » |
| FFlex | 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) |
|
|