 Münzwechsel - Problem |
boss
unregistriert
 |
|
Tach,
ich muss mich mit dem Greedy-Münzwechsel-Problem auseinandersetzen und zeigen, dass unser Münzsystem (1c,2c,5c,10c,20c,50c,100c,200c) mit dem Greedy-Algo immer den zu wechselnden Betrag in der optimale (minimale) Anzahl an Münzen zurückgibt. Als Tipp wurde gesagt, dass man sich klarmachen soll, wieviele der Münzen max. bei einer optimalen Lösung vorkommen. (1x1c,2x2c,1x5c,1x10c,2x20c,1x50c,1x100c)
Weiter komme ich leider nicht. Kann mir einen nen Hinweis geben? Gib etwas am verzweifeln. Danke!
der boss
|
|
12.01.2011 16:32 |
|
|
aal
unregistriert
|
|
War das nicht so ,dass erst die größte Münze solange ausgeben wird, bis der Wert < GrößteMünze ist ,dann kommt die zweit größte usw. ?
|
|
|
12.01.2011 22:52 |
|
|
boss
unregistriert
|
|
ja so ist der greedy algorithmus, aber wie zeigt man denn, dass der optimal ist bei der oben gezeigten münzauswahl?
|
|
|
12.01.2011 22:59 |
|
|
aal
unregistriert
|
|
Wenn man alle Münzen des Tips addiert ergibt das 210 , und angewannt auf den Algorithmus ,wäre das 1x200c und 1x10c
Man sieht aber eine Reihenfolge :
(1x1c,2x2c,1x5c,1x10c,2x20c,1x50c,1x100c)
100-150-190-200-205-209-210
also immer 10 - 15 - 19 - 20 ----100-150-190-200...
10000-15000-19000-20000....usw
Besser weiß ich das auch nicht, ich denke es hängt von vom Betrag ab ;D
|
|
|
12.01.2011 23:23 |
|
|
Ibn Batuta 
Mitglied
Dabei seit: 02.01.2011
Beiträge: 26
|
|
| Zitat: |
Original von boss
ja so ist der greedy algorithmus, aber wie zeigt man denn, dass der optimal ist bei der oben gezeigten münzauswahl? |
Ich würde es so beweisen:
Sei I eine Menge {i,ii,iii, iv, ..., n}, L eine Münze und ein Betrag b => L.
Dann ist es suboptimal, b < C auszudrücken.
Sei L eine 1-Euro-Münze und b >= L. Ich konstruiere nun einen Widerspruch. Nehme hierzu an, dass b mit genau j L/2 und an Wert noch kleineren Münzen für die verbliebenen b-k*L/2 optimal bezahlt werden kann. Jetzt ist allerdings der Widerspruch schon da, denn weil b-k*L/2 optimal ausgezahlt werden, muss nun gelten: b-k*L/2<L/2, also auch b < L/2*(k+1). Da k>=2 ist, ist das ein Widerspruch.
Zu zeigen ist, dass der Greedy-Algorithmus für das Münzwechselproblem optimal ist.
Nimm dazu an, dass L_i, L_ii, L_iii, ... , L_n mit L_{i+1}<L_{i} ist. Dann kannst du mit vollständiger Induktion zeigen, dass eine optimale Lösung mit L_i, L_ii, L_iii, ..., L_k mit k Element I beginnt.
Du kannst dir nun noch überlegen, wenn das nicht zutreffen würde. 
Denn das muss auch noch abgehandelt werden. Hierfür kannst du meinen obigen Beweis anbringen.
Ibn Batuta
|
|
|
13.01.2011 17:46 |
|
|
|
