Münzwechsel - Problem |
| 12.01.2011, 16:32 | Auf diesen Beitrag antworten » | ||
| boss | Münzwechsel - Problem 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, 22:52 | Auf diesen Beitrag antworten » | ||
| aal | 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:59 | Auf diesen Beitrag antworten » | ||
| boss | ja so ist der greedy algorithmus, aber wie zeigt man denn, dass der optimal ist bei der oben gezeigten münzauswahl? |
||
| 12.01.2011, 23:23 | Auf diesen Beitrag antworten » | ||
| aal | 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 |
||
| Anzeige | |||
|
|
|||
| 13.01.2011, 17:46 | Auf diesen Beitrag antworten » | ||
| Ibn Batuta |
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 |
||
|
|
Verwandte Themen
| Die Beliebtesten » |
| Die Größten » |
| Die Neuesten » |