Matroidstruktur bei Münzen |
| 14.05.2007, 18:06 | FFlex | Auf diesen Beitrag antworten » | ||
| Matroidstruktur bei Münzen 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? Die Definition eines Matroids ist mir bekannt, ich weiß nur nicht, wie ich das auf die Münzmengen anwenden kann?! 
Vielen Danke, FFlex |
||||
| 14.05.2007, 18:09 | Dual Space | Auf diesen Beitrag antworten » | ||
RE: Matroidstruktur bei Münzen
Mir nicht. Wäre daher vielleicht ganz nützlich diese hier zu posten. |
||||
| 14.05.2007, 18:13 | AD | Auf diesen Beitrag antworten » | ||
Ich kenn's auch nicht. Scheint eher in die Informatik zu passen. |
||||
| 14.05.2007, 18:57 | FFlex | Auf diesen Beitrag antworten » | ||
Oh, sorry... Wollts jetzt reinschreiben, aber der Formeleditor kann die Mengensymbole teilweise net (oder ich raff es nicht 
). Deshalb hier kurz der wikipedia-link:http://de.wikipedia.org/wiki/Matroid
Ich werds dann mal noch in nem Informatikerboard posten. Aber trotzdem danke für eure Mühe! Gruß, FFlex |
||||
| 14.05.2007, 18:59 | AD | Auf diesen Beitrag antworten » | ||
Sollte nicht heißen, dass es hier nicht (auch) hingehört. Aber vielleicht ist das den Informatikexperten eher vertraut. |
||||
|
|
Verwandte Themen
| Die Beliebtesten » |
| Die Größten » |
| Die Neuesten » |
