 Münzwechselproblem - Danymische Programmierung |
|
|
| 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 ...
__________________
I'm 71% Megatron!
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von JROppenheimer: 05.02.2008 12:09.
|
|
05.02.2008 11:59 |
|
|
Tobias
Routinier
Dabei seit: 18.09.2006
Beiträge: 324
 |
|
|
|
05.02.2008 23:18 |
|
|
|
|
Du bist einfach TobiasPedia.
Vielen vielen Dank!
__________________
I'm 71% Megatron!
|
|
|
06.02.2008 10:16 |
|
|
|
