Matroids Matheplanet Forum Index
Moderiert von matroid
Mathematik » Kombinatorik & Graphentheorie » Wechselgeldproblem
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule Wechselgeldproblem
Clvrhammer
Junior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 06.11.2019
Mitteilungen: 11
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2019-12-06


Grüße,

Ich habe eine Frage bezüglich des Wechselgeldproblems, i.e. das Problem einen Geldbetrag $n$ mit so wenigen Münzen wie möglich zu erreichen.

Das genaue Problem ist wie folgt:


Wir nehmen an, dass die möglichen Münzwerte Potenzen einer natürlichen Zahl $q > 1$ sind, d.h. die Menge möglicher Münzen ist $\{ q^0, q^1, q^2, ..., q^k \}$ für ein $k \geq 1$.
Nun ist zu zeigen, dass ein Greedy-Algorithmus (d.h. in jedem Schritt wird die Münze mit dem größtmöglichen Wert genommen, solange diese den zu erreichenden Betrag nicht überschreitet) zu einer optimalen Lösung führt.


Zu Anfang dachte ich, das Problem würde sich von selbst erklären; ein Beispiel mit den Münzwerten $\{1,3,4\}$ und dem Geldbetrag $n=6$ (optimale Lösung: $(3,3)$, Greedy-Lösung: $(4,1,1)$ ) belehrte mich aber eines besseren. Nun stehe ich allerdings an und habe keinen Ansatz wie dies tatsächlich zu beweisen ist.

Ich weiß, dass von jedem Münzwert $q^i$ maximal $q$ Münzen genommen werden dürfen, denn ansonsten wäre $q \cdot q^i = q^{i+1}$, also der nächst-höhere Münzwert und die Anzahl reduziert sich um $q-1$ Münzen. Mir ist nur noch nicht so genau klar, wie ich das in meinem Beweis verwende.

Kann hier jemand weiterhelfen?

Grüße,

Silverhammer



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
MartinN
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 05.08.2016
Mitteilungen: 1198
Aus: Bayern
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2019-12-06


1, 3, 4 sind doch gar keine möglichen Münzwertr gemäß deiner Aufgabe?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 6061
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, eingetragen 2019-12-06


Hallo Clvrhammer,

2019-12-06 01:40 - Clvrhammer im Themenstart schreibt:
Ich weiß, dass von jedem Münzwert $q^i$ maximal $q$ Münzen genommen werden dürfen, denn ansonsten wäre $q \cdot q^i = q^{i+1}$, also der nächst-höhere Münzwert und die Anzahl reduziert sich um $q-1$ Münzen.

Dies ist schon der entscheidende Gedanke, und das will jetzt noch technisch korrekt ausgeführt werden.

Es gilt sogar, dass von jedem Münzwert $q^i$ (\(i<k\)) maximal $q-1$ Münzen genommen werden dürfen. (*) (Diese Nuance wirst du noch brauchen.)

Sei also \(n\) ein zu zahlender Betrag und \(\ell\leq k\) maximal mit \(q^\ell\leq n\). Nimm an, dass dieser Betrag mit Münzen \(q^i\) (\(i<\ell\)) bezahlt wird.

Wie kann nun die Eigenschaft (*) zu einem Widerspruch geführt werden?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Clvrhammer
Junior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 06.11.2019
Mitteilungen: 11
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, vom Themenstarter, eingetragen 2019-12-06


Edit: Antwort auf MartinN:

Das war meinerseits etwas missverständlich formuliert.

Gemeint war:

Dass ein Greedy-Algortihmus bei beliebigen Münzenwerten ein optimales Ergebnis liefert, schien mir zu Anfang (fälschlicherweise) einleuchtend. Nachdem ich dieses Gegenbeispiel gesehen hatte, wurde mir klar, dass dies nicht immer der Fall ist. Indem dies nicht immer der Fall ist, muss es auch nicht notwendigerweise bei meinem Beispiel (mit Münzwerten, welche Potenzen einer natürlichen Zahl sind) der Fall sein.



Edit: Antwort auf StrgAltEntf:

Danke für die Antwort, ich werde mir das sobald ich Gelegenheit finde durchüberlegen und melde mich dann mit wieder mit einer Idee.

[Die Antwort wurde nach Beitrag No.1 begonnen.]



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Clvrhammer
Junior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 06.11.2019
Mitteilungen: 11
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, vom Themenstarter, eingetragen 2019-12-09



Ist folgende Argumentation ok?


Ich nehmen an, ich hätte eine optimale Lösung $(b_0, ..., b_k)$ (b für "best") und eine Lösung des Greedy-Algorithmus $(g_0, ..., g_k)$ (g für "greedy").

Wäre nun $b_k > g_k$, so wäre $g_k$ keine Lösung des Greedy-Algorithmus, da offensichtlich eine Lösung existiert, die noch gieriger war. WIDERSPRUCH.

Wäre nun $b_k < g_k$, so müssten die Koeffizienten $b_0,...b_{k-1}$ derart sein, dass der fehlende Münzwert $c^k$ ausgeglichen wird. Da nun aber für alle $j$ gilt, dass $b_j < c$ ist, so ist der maximal mögliche Wert der "ausgeglichen" werden kann:

$(c-1)\cdot c^0 + ... + (c-1) \cdot c^{k-1} = c^k - 1$

(geometrische Reihe). Dieser Maximalwert ist aber kleiner als der Minimalwert der ausgeglichen werden müsste, somit liegt wieder ein WIDERSPRUCH vor.

Folglich ist $b_k = g_k$. Diese Argumentation kann ich jetzt für $(b_0, ...b_{k-1})$ und $(g_0, ..., g_{k-1})$ wiederholen.


Die Argumentation scheint mir soweit ok, aber sicher bin ich mir dabei nicht.

Grüße,

Silverhammer



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 6061
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2019-12-09


Hallo,

die Idee mit der geometrischen Reihe ist sehr gut. Ansonsten ist dein Bewies aber nicht ganz astrein. Erst einmal könnte es ja sein, dass bereits \(p^k>n\) ist, wenn \(n\) der zu zahlende Betrag ist. Dann wäre \(b_k=g_k=0\). Deshalb hatte ich in Beitrag #2 das \(\ell\) eingeführt. (Wieso hast du das \(q\) eigentlich in \(c\) umbenannt? Ich bleibe jetzt mal bei \(q\).)

Sei also \(\ell\) maximal mit \(q^l\leq n\). \((b_0,...,b_\ell)\) sei eine beste Stückelung von \(n\); es gilt \(n=\sum_{i=0}^\ell b_iq^i\). Dann ist ja eigentlich nur zu zeigen, dass \(b_\ell>0\), dass also bei der besten Stückelung der Münzwert \(q^\ell\) verwendet wird. (Du hast dann das Problem \(n\) zu stückeln, auf das Problem \(n-q^\ell\) zu stückeln, zurückgeführt. Formal korrekt kannst du hier noch eine vollständige Induktion einschieben.)

Wegen (*) aus Beitrag #2 gilt \(b_i\leq q-1\) für \(i=0,...,\ell\). Wenn \(b_\ell=0\) wäre, dann ist \(n=\sum_{i=0}^{\ell-1} b_iq^i\leq\sum_{i=0}^{\ell-1}(q-1)q^i=q^\ell-1\leq n-1<n\). Widerspruch.

P. S.: Wie sieht das eigentlich im echten Leben aus? Es gibt insgesamt die möglichen Cent- und Euro-Werte \(w_0=\)1 Cent, \(w_1=\)2 Cent, ..., \(w_{14}=\)500 Euro. Es gilt dann \(2w_i\leq w_{i+1}\) für \(i=0,...,13\). Du kannst ja mal überlegen, ob sich der Beweis modifizieren lässt und auch hier der Greedy-Algorithmus stets die beste Stückelung ergibt.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Clvrhammer hat die Antworten auf ihre/seine Frage gesehen.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


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-2020 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]