Münzwechselproblem - Danymische Programmierung |
| 05.02.2008, 11:59 | Auf diesen Beitrag antworten » |
| JROppenheimer | Münzwechselproblem - Danymische Programmierung Ich soll das Münzwechselproblem mit Hilfe des Ansatzes der Dynamischen Programmierung lösen. Das Problem mit einem naiven Greedy ist ja, dass er nicht unbedingt das globale Optimum herausfindet. Bsp: Betrag = 10 Münzwerte: 8, 5, 1 greedy gibt 8 - 1 - 1 zurück optimal wäre 5 - 5 Jetzt dachte ich mir das so: Als ich das per Greedy gelöst habe, habe ich mit mod gearbeitet. Das könnte ihc doch auch benutzen um das optimal zu lösen. Ich schaue in jedem Durchlauf, mit welcher Münze ich (Betrag mod Münzewert) minimal habe und mache das solange, bis der Betrag 0 ist. Dafür gehe ich beim ersten Durchlauf ALLE Münzarten durch. Beim zweiten Durchlauf muss ich ja dann nur noch die münzen durchgehen, die kleiner als der Restbetrag sind. SO IN ETWA dachte ich mir das. Klingt das nach ner richtigen Lösung?! *edit Okay, da kommt mit der Gedanke ... die Münze mit dem Wert 1 gibts ja immer, folglich wird da auch immer ein minimales Ergebnis rauskommen. ...optimal ist meine Methode also offensichtlich noch net ... |
|
|
|
| 05.02.2008, 23:18 | Auf diesen Beitrag antworten » |
| Tobias | Algo "DPChange" http://www.informatik.uni-kiel.de/filead..._comparison.pdf |
| 06.02.2008, 10:16 | Auf diesen Beitrag antworten » |
| JROppenheimer | Du bist einfach TobiasPedia. Vielen vielen Dank! |
| 06.02.2008, 10:29 | Auf diesen Beitrag antworten » |
| JROppenheimer | bestNumCoins mit M als Index. ist M ein Index, oder ist M ein Übergabeparameter? darf ich fragen wie man von dieser Rekursion "so leicht" auf diese Iterative Lösung kommt?! *edit: Okay hat sich erledigt ... irgendwie habe ich mir in letzer Zeit angewöhnt, durch deine Hilfe ERST zu fragen, dann zu denken .... meist erledigen sich die simplen Sachen ja schon durch selbst denken 
Danke nochmal! |
| Anzeige | |
|
|
|
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
