 Matroidstruktur bei Münzen |
FFlex 
Grünschnabel
Dabei seit: 14.05.2007
Beiträge: 3
 |
|
| 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 19:09 |
|
|
Tobias
Routinier
Dabei seit: 18.09.2006
Beiträge: 324
|
|
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 22:30 |
|
|
FFlex
Grünschnabel
Dabei seit: 14.05.2007
Beiträge: 3
|
|
Da fängt das Problem ja schon an, ich hab keine Ahnung. 
|
|
|
14.05.2007 23:46 |
|
|
Tobias
Routinier
Dabei seit: 18.09.2006
Beiträge: 324
|
|
Ist das Problem auf die feste Zahl 15 begrenzt oder steht die 15 exemplarisch für eine beliebige Zahl n?
|
|
|
15.05.2007 01:06 |
|
|
FFlex
Grünschnabel
Dabei seit: 14.05.2007
Beiträge: 3
|
|
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)
|
|
|
15.05.2007 10:27 |
|
|
|
