Matroids Matheplanet Forum Index
Moderiert von matroid
Informatik » Algorithmen / Datenstrukturen » Dynamische Programmierung - Münzwechsel
Autor
Universität/Hochschule Dynamische Programmierung - Münzwechsel
JROppenheimer
Ehemals Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 20.11.2007
Mitteilungen: 115
  Themenstart: 2008-02-05

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 ... [ Nachricht wurde editiert von JROppenheimer am 05.02.2008 12:09:20 ]


   Profil
JROppenheimer
Ehemals Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 20.11.2007
Mitteilungen: 115
  Beitrag No.1, vom Themenstarter, eingetragen 2008-02-05

Ich versuch mal meine Idee in PseudoCode zu formulieren: B = Betrag, der in Münzen auszugeben ist. A = [a1,a2,...,ak] mit 1 = a1 < a2 < ... < ak Ich dachte mir das ungefähr so: \sourceon PseudoCode while (B >= a2) {     finde alle min{B mod ai} mit ai!= 1     for all ai aus min{B mod ai}         aktuelleMünze <- finde ai mit B\ai ist minimal     B = B mod aktuelleMünze } //jetzt ist B < a2, also muss der Restbetrag in 1er-Münzen ausgegeben werden. \sourceoff Ich hoffe meine Idee kommt da ETWAS verständlich rüber....


   Profil
TheBear
Senior Letzter Besuch: im letzten Quartal
Dabei seit: 31.01.2006
Mitteilungen: 1329
  Beitrag No.2, eingetragen 2008-02-05

Moin JROppenheimer, Der erste Schritt beim Lösen eines Problems mit dynamischer Programmierung sollte immer das Beschreiben des Problems durch eine Rekursionsformel sein. Dazu muss man erstmal einen Term finden, den man gut rekursiv beschreiben kann, üblicherweise ersteinmal nur, um den Wert einer optimalen Lösung zu bestimmen, nicht gleich die Lösung selbst. Daraus lässt sich dann durch eine mehr oder weniger leichte Modifikation des Algorithmus auch die Lösung selbst berechnen. Hier bietet es sich an, M(i,B) als die minimale Anzahl an Münzen zu definieren, die man benötigt, um mit den ersten i Münztypen den Betrag B auszuzahlen. Versuch mal für M(i,B) eine Rekursionsformel zu finden (Bloß nicht zu kompliziert denken an der Stelle!). Gruß TheBear [Die Antwort wurde vor Beitrag No.1 begonnen.]


   Profil
JROppenheimer
Ehemals Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 20.11.2007
Mitteilungen: 115
  Beitrag No.3, vom Themenstarter, eingetragen 2008-02-05

Ich muss ehrlich gestehen, ich steh ein bisschen aufm Schlauch und vor allem auf Kriegsfuß mit den Rekursionen... Wäre es vlt möglich,dass Du mir ein BISSCHEN auf die Sprünge hilfst?! Nicht die Komplettlösung, nur noch n Stubs ... danke! Meinst Du mit "die ersten i" a1,a2,....,ai oder ak,....ak-i ??? [ Nachricht wurde editiert von JROppenheimer am 05.02.2008 14:37:42 ]


   Profil
JROppenheimer
Ehemals Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 20.11.2007
Mitteilungen: 115
  Beitrag No.4, vom Themenstarter, eingetragen 2008-02-05

Rekursionen rufen sich ja immer selbst auf, bis zu einem bestimmten Punkt, an dem sie abbrechen. Diese Abbruch bedingung ist doch, wenn i=1, oder? also: M(i,B) = B, wenn i=1 (denn 1*B = B) an der Rekursion kaue ich noch n bisschen ... *edit: Müsste das nicht ne Summe sein!? Nämlich die Menge der Münzen bis zur i-1.ten Münze + die Menge der Münzen bei der i-ten Münze? also sowas wie: M(i,B) = B, wenn i=1 (denn 1*B = B)          M(i, B) + M(i-1, B mod ai), sonst (wenn ai die aktuell betrachtete Münze ist... [ Nachricht wurde editiert von JROppenheimer am 05.02.2008 14:46:53 ]


   Profil
GrafZahl
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 22.04.2003
Mitteilungen: 1455
Wohnort: Leverkusen, D
  Beitrag No.5, eingetragen 2008-02-05

Hallo JROppenheimer, was heißt denn 'optimal' (minimale Münzanzahl ?!?) Wie wäre es in dem Fall mit Breitensuche ? mfG Graf Zahl P.S Minimales Gewicht der Münzen wäre sicher auch ein interessantes Optimum [Die Antwort wurde nach Beitrag No.3 begonnen.]


   Profil
TheBear
Senior Letzter Besuch: im letzten Quartal
Dabei seit: 31.01.2006
Mitteilungen: 1329
  Beitrag No.6, eingetragen 2008-02-05

Ok, Hinweis: Wenn man den Betrag B mit den ersten i möglichen Münzentypen bezahlen will (die Reihenfolge der Münzen ist hier übrigens völlig egal), dann hat man doch zwei Möglichkeiten: 1. Man nimmt eine (weitere) Münze vom Typ i zu seiner Münzmenge hinzu. 2. Man lässt es bleiben. Dann muss man nur noch aus den ersten i-1 möglichen Münztypen auswählen. Wenn man in Fall 1 ist, was ist dann die minimal benötigte Anzahl an Münzen (rekursiv)? Wenn man in Fall 2 ist, wie kann man diese Anzahl dann rekursiv hinschreiben? Welchen der beiden Fälle muss man auswählen, um eine insgesamt minimale Anzahl an Münzen zu erhalten? Zu den Abbruchbedingungen: Wenn der Betrag B=0 auszuzahlen ist, sollte klar sein, wie viele Münzen man braucht. Wenn i = 0 ist (d.h. es steht kein Münztyp mehr zur Verfügung) und B > 0 gilt, wird man den Betrag niemals auszahlen können. Hier müsste man dann einen Fehlerwert einführen (Welchen man da genau nimmt, kann man sich später überlegen. Am besten so einen, dass der Rest der Rekursion "ordentlich" damit klarkommt.) Übrigens muss man bei den Abbruchbedingungen meist nicht nur die Fälle betrachten, dass einer der Parameter 0 wird, sondern auch, dass einer der Parameter negativ wird. Ich empfehle dir, in diesem Fall zuerst den rekursiven Fall zu betrachten. Gruß TheBear EDIT: @GrafZahl Worauf willst du die Breitensuche denn ausführen? Ich sehe hier nirgends einen Graphen? [Die Antwort wurde nach Beitrag No.4 begonnen.] [ Nachricht wurde editiert von TheBear am 05.02.2008 15:12:19 ]


   Profil
JROppenheimer
Ehemals Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 20.11.2007
Mitteilungen: 115
  Beitrag No.7, vom Themenstarter, eingetragen 2008-02-05

Das mit dem Editor ist ja ein Krampf .... Meinst Du das so!? m(k , B) = cases(B, k=1; minimum{m(k, B - ak) oder  m((k-1,B))}, sonst) m sollte eigendlich min heissen, aber die die funktion heisst, ist ja egal geht das wenigstens in die richtige Richtung?


   Profil
matph
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 20.11.2006
Mitteilungen: 5506
Wohnort: A
  Beitrag No.8, eingetragen 2008-02-05

Hallo JROppenheimer, Ich verstehe zwar nicht ganz was du meinst, was ist z.B. a,... macht auch nicht viel, du musst vor allem mal m definieren Ich würde mal von den ganzen Ausnahmebehandlungen die beschrieben wurden abraten, falls das Element 1 vorkommt, was aus deinem ersten Beitrag hervorgeht, ist diese nämlich unnötig. Poste doch mal den greedy Alg. für dieses Problem, denn im Grunde muss nur eine einzige kleine Ergänzung vorgenommen werden, um generell die optimalen Ergebnisse zu erhalten. smile -- mfg matph


   Profil
JROppenheimer
Ehemals Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 20.11.2007
Mitteilungen: 115
  Beitrag No.9, vom Themenstarter, eingetragen 2008-02-05

relativ weit oben hab ich geschrieben, wie ich mir das in etwa denke, da hab ich auch einfach greedy verändert ... Oben steht auch, was a1,.....,ak ist und m ist nur die funktion wie von TheBear beschrieben M(i,B) .... bei mir halt aus versehen m(k,B) das problem ist ja, dass ich das hier per dynamischer programmierung lösen soll. Greedy ging so: \sourceon Pseudo münzenart = [a1, a2, .... , ak] mit a1 = 1 und a1 < a2 <.... 0 and k>0) {        münzen[k] = B/münzenart[k]        B = B mod münzenart[k]        k-- } \sourceoff kann sein, dass da der ein oder andere kleine fehler drin ist, aber im grunde müsste das gehn. Fange mit der größsten Münze an, und packe so viele zusammen, wie in B "reinpassen". Mache mit der nächst kleineren Münze weiter und führe das auf den Restbetrag aus....


   Profil
matph
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 20.11.2006
Mitteilungen: 5506
Wohnort: A
  Beitrag No.10, eingetragen 2008-02-05

Hallo JROppenheimer, Sehr schön, das gleiche können wir natürlich auch Rekursiv schreiben, wie wir dies für die Optimierung benötigen: \sourceon Code muenz(x) = f(x, [], [200,100,50,20,10,5,2,1]) f(x, ys, zs) =   if x == 0   then ys   if x-z >= 0 then f(x-z, head zs to ys, zs)   otherwise        f(x, ys, tail zs) \sourceoff Nun ist es noch notwendig, nicht nur die erste Münze, sondern auch alle anderen zu betrachten, also für jede in der Liste die Funktion rekursiv auf zu rufen smile -- mfg matph


   Profil
JROppenheimer
Ehemals Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 20.11.2007
Mitteilungen: 115
  Beitrag No.11, vom Themenstarter, eingetragen 2008-02-05

was machen \sourceon nameDerSprache f(x-z, head zs to ys, zs)   otherwise        f(x, ys, tail zs) \sourceoff ??


   Profil
JROppenheimer
Ehemals Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 20.11.2007
Mitteilungen: 115
  Beitrag No.12, vom Themenstarter, eingetragen 2008-02-05

Ich frage mich sowieso, was mir die dynamimsche Programmierung hier bringen soll. Dynamisch Programmiert wird doch, wenn rekursiv viele Aufrufe doppelt oder mehrfach auftreten, oder? In dem Fall passiert das doch gar net, weil jeh nach Restbetrag und Münze immer was anderes berechnet wird... oder verstehe ich hier wieder was prinzipiell nicht?


   Profil
matph
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 20.11.2006
Mitteilungen: 5506
Wohnort: A
  Beitrag No.13, eingetragen 2008-02-05

Hallo JROppenheimer, Die Zeilen welche du gepostet hast, sind die Rekursion, hier wird erneut die Funktion f aufgerufen wink Oder mainszt du head und tail, hierbei wird das erste Element und der Rest einer Liste betrachtet smile -- mfg matph


   Profil
JROppenheimer
Ehemals Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 20.11.2007
Mitteilungen: 115
  Beitrag No.14, vom Themenstarter, eingetragen 2008-02-05

Ich meinte head und tail. head ist das erste element, und tail alle elemente die nach dem ersten kommen?!


   Profil
matph
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 20.11.2006
Mitteilungen: 5506
Wohnort: A
  Beitrag No.15, eingetragen 2008-02-05

Hallo JROppenheimer, Ganz genau. smile -- mfg matph


   Profil
JROppenheimer
Ehemals Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 20.11.2007
Mitteilungen: 115
  Beitrag No.16, vom Themenstarter, eingetragen 2008-02-05

Aber dann lag ich doch oben mit dem, was ich da geschrieben habe gar net so falsch, oder? mal abgesehn von der unschönnen Form :D


   Profil
GrafZahl
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 22.04.2003
Mitteilungen: 1455
Wohnort: Leverkusen, D
  Beitrag No.17, eingetragen 2008-02-05

@TheBear Mir schwebte so etwas vor: Bild mfG Graf Zahl [Die Antwort wurde nach Beitrag No.12 begonnen.]


   Profil
JROppenheimer
Ehemals Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 20.11.2007
Mitteilungen: 115
  Beitrag No.18, vom Themenstarter, eingetragen 2008-02-05

Als Du von der Breitensuche gesprochen hast, dachte ich auch an sowas, denn das Optimum wäre dann das erste ergebnis, das gefunden wird, bei dem der Betrag rauskommt, den wir auszahlen wollen. Fand die Idee nicht schlecht!!!


   Profil
JROppenheimer
Ehemals Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 20.11.2007
Mitteilungen: 115
  Beitrag No.19, vom Themenstarter, eingetragen 2008-02-06

Hier eine Lösung: Sei m der Betrag, der herauszugeben ist. Sei c = [c1,c2,c3,...,ck] das array mit den verschiedenen Münzen, mit c1=1 \sourceon PseudoCode DPChange(m,c,k)     bestNumCoins[0] = 0     for(m=1;m<=M; m++)         if m >= c[i]         if bestNumCoins[m - c[i]]+1 < bestNumCoins[m]             bestNumCoins[m] = bestNumCoins[m - c[i]]+1     return bestNumCoins[m] \sourceoff Ich muss gestehen alleine wäre ich nicht drauf gekommen.


   Profil
matph
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 20.11.2006
Mitteilungen: 5506
Wohnort: A
  Beitrag No.20, eingetragen 2008-02-07

Hallo, Der Vollständigkeit halber noch der gesamte Algorithmus: smile \sourceon Ruby def f(a, b)   if a == nil then false   elsif b == nil then true   else a+1 < b   end end def muenz(m, c)   bestNumCoins = [0]   (1..m).each do |n|     (0...c.length).each do |i|       if n >= c[i] then         if f(bestNumCoins[n-c[i]], bestNumCoins[n]) then           bestNumCoins[n] = bestNumCoins[n-c[i]] + 1         end       end     end   end   bestNumCoins[m] end puts muenz(gets.to_i,[1,5,8]) \sourceoff Und auch gleich wieder das Häkchen... -- mfg matph


   Profil
Folgende Antworten hat der Fragesteller vermutlich noch nicht gesehen.
Er/sie war noch nicht wieder auf dem Matheplaneten
MalcomY
Wenig Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 12.05.2020
Mitteilungen: 46
  Beitrag No.21, eingetragen 2021-02-27

Es ist ein ziemlich alter Thread, aber ich habe die selbe Aufgabe und möchte es mit dynamic programming programmieren. Leider kenne ich Ruby nicht ich habe versucht das gleiche Problem in Python zu programmieren. \sourceon nameDerSprache def DPChange(m,c): k = len(c) bestNumCoins = m * [0] for i in range(1,m): for j in range(k): if i >= c[j]: if bestNumCoins[i - c[j]] == 0: continue elif bestNumCoins[i] == 0 or bestNumCoins[i - c[j]]+1 < bestNumCoins[i]: bestNumCoins[i] = bestNumCoins[i - c[j]]+1 return bestNumCoins print(DPChange(10,[1,5,8])) \sourceoff Leider funktioniert der Code nicht. Wo ist mein Fehler?


   Profil
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 3042
  Beitrag No.22, eingetragen 2021-02-27

Instinktiv vermute ich einen Off-by-One-Error. Das wäre mein Vorschlag: \sourceon Python \numberson def DPChange(m,C): bestNumCoins = [m+1 for i in range(m+1)] bestNumCoins[0] = 0 for i in range(1,m+1): for c in C: if i-c >= 0 and bestNumCoins[i-c]+1 < bestNumCoins[i]: bestNumCoins[i] = bestNumCoins[i-c] + 1 return bestNumCoins \sourceoff


   Profil
MalcomY
Wenig Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 12.05.2020
Mitteilungen: 46
  Beitrag No.23, eingetragen 2021-02-27

Vielen Dank


   Profil
MalcomY
Wenig Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 12.05.2020
Mitteilungen: 46
  Beitrag No.24, eingetragen 2021-02-27

Ich habe noch nicht ganz verstanden was bestNumCoins macht. Hat es etwas mit der Abbildung von GrafZahl zu tun?


   Profil
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 3042
  Beitrag No.25, eingetragen 2021-02-27

bestNumCoins ist ein Array von 0 bis m. Für jeden Wert wird die minimale Anzahl Münzen gespeichert. Am Ende sieht es (zurückgegeben) wie folgt aus: [0, 1, 2, 3, 4, 1, 2, 3, 1, 2, 2] Es sind 0 Münzen notwendig, um 0 zu wechseln. Es ist 1 Münze notwendig, um 1 zu wechseln. ... Es sind 3 Münzen notwendig, um 7 zu wechseln. ... Es sind 2 Münzen notwendig, um 10 zu wechseln. Für jeden Wert und jede Münzsorte ist eine Lösung gleich der besten Lösung für Wert minus Münzsorte plus 1. Falls diese Lösung besser ist als die bekannte, wird sie gespeichert. Zu Beginn setzt man alle Lösungen außer für die 0 auf Unendlich bzw. einen unerreichbar hohen Wert. Edit: Hier noch eine andere Variante: \sourceon Python \numberson def coin_change_breadth_first(N,C): D = {0: []} S = {0} while S and not N in S: _S = set() for n in S: for c in C: if n+c <= N and not n+c in S: _S.add(n+c) D[n+c] = D[n]+[c] S = _S if N in S: return D[N] return None \sourceoff


   Profil
MalcomY
Wenig Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 12.05.2020
Mitteilungen: 46
  Beitrag No.26, eingetragen 2021-02-27

Ich glaube jetzt habe ich das Verfahren verstanden. Was denkst du welche Variante wäre besser. Da in der Aufgabenstellung in dynamischen Programmierung steht. Edit: In der Aufgabenstellung steht "Definieren Sie als erstes die Teilprobleme, und stellen Sie die Rekursionsgleichungen mit den Randbedingungen auf. Schreiben Sie danach den Algorithmus in Pseudocode."


   Profil

Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]