Die Mathe-Redaktion - 19.01.2020 20:48 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte / Top 15
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
Listenpunkt? im neuen Schwätz
ListenpunktWerde Mathe-Millionär!
ListenpunktAward-Abstimmung ab 1.1.
ListenpunktFormeleditor fedgeo
Schwarzes Brett
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden. Mitglieder können den Matheplanet-Newsletter bestellen, der etwa alle 2 Monate erscheint.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 662 Gäste und 32 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von matroid
Mathematik » Kombinatorik & Graphentheorie » Wechselgeldproblem
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule Wechselgeldproblem
Clvrhammer
Junior Letzter Besuch: im letzten Monat
Dabei seit: 06.11.2019
Mitteilungen: 9
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



Wahlurne Für Clvrhammer bei den Matheplanet-Awards stimmen
  Profil  Quote  Link auf diesen Beitrag Link
MartinN
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 05.08.2016
Mitteilungen: 1121
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?



Wahlurne Für MartinN bei den Matheplanet-Awards stimmen
  Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 5402
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?



Wahlurne Für StrgAltEntf bei den Matheplanet-Awards stimmen
  Profil  Quote  Link auf diesen Beitrag Link
Clvrhammer
Junior Letzter Besuch: im letzten Monat
Dabei seit: 06.11.2019
Mitteilungen: 9
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.]



Wahlurne Für Clvrhammer bei den Matheplanet-Awards stimmen
  Profil  Quote  Link auf diesen Beitrag Link
Clvrhammer
Junior Letzter Besuch: im letzten Monat
Dabei seit: 06.11.2019
Mitteilungen: 9
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



Wahlurne Für Clvrhammer bei den Matheplanet-Awards stimmen
  Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 5402
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.



Wahlurne Für StrgAltEntf bei den Matheplanet-Awards stimmen
  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-2019 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. 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]