Wechselgeld

[gd12]

Ich suche für folgende Aufgabe eine Lösungsstrategie:

Mittels eines angepassten Greedy-Ansatzes soll für ein angegebenes Wechselgeld (unter 5 Euro) berechnet werden, wie viele der verschiedenen Münzen (50, 10, 5, 2 und 1 Cent) verwendet werden müssen.
Für das Wechselgeld sollen so wenig Münzen wie möglich verwendet werden.
Jede der verschiedenen Münzen steht nur mit einer begrenzten Anzahl zur Verfügung. Diese Anzahl kann variieren.
Wird der geforderte Betrag nicht genau erreicht muss auf jedem Fall mehr zurück gegeben werden. Nur wenn die Anzahl der Münzen nicht für den geforderten Betrag reichen, darf weniger zurück gegeben werden. (Alle Münzen werden verwendet). Ansonsten soll der zu viel zurück gegebene Betrag möglichst gering gehalten werden.

 

[ARadauer]

ne glaub ich nicht ;-) du suchst eine lösung für deine hausaufgabe...

na überleg dir das mal mit papier und bleistift ... du musst 3,56 raus geben... wie machst du das?
du gibst so lange 50 c hier bis der restbetrag kleiner 50 c ist oder du keine 50 cmehr hast... dann gibst du 20 c her bis du... usw....

 

[SlaterB]

bevor man an hochtrabende Strategien oder Algorithmen denkt, sollte man das ganze per Hand versuchen,
und bei deiner Menge der Münzen sehe ich derzeit keine Möglichkeit für irgendeine Art von Problem,

gib immer die höchstmöglichen Münzen, bis der Betrag erreicht ist,
wenn dann eine höhere Münze drüber wäre, dann versuche es nur noch mit den kleineren Münzen,
falls diese nicht ausreichen, dann gib eine nächsthöhere Münze hinzu und entferne wiederum soviele kleinere Münzen wie möglich

nun muss man sich Problemstellen ausdenken, aber ich sehe wie gesagt keine,
die kleineren Münzen passe alle in die größeren hinein, es gibt keine Überschneidung mit Ausnahme der 5 vs 2,
allerdings ist da noch die 1, die diese Unebenheit sofort ausbügeln würde,

hätte man nicht die 1, dann gäbe es bisschen Probleme:
bei einem Wechselgeld von 8 muss man vier 2er wählen, mit einem 5er wäre man schon auf der falschen Straße, aber durch den 1er hat man das korrigiert, 5 ist die richtige Wahl +2 +1,
solange du also wenigsten einen 1er hast, kann mein obiger vorgeschlagener Algorithmus meiner Meinung nach nix falsch machen

Beispiele:
80 Cent:
wähle 50er,
20er,
10er,

nicht grad spannend

Beispiel
1,16
zur Auswahl stehen nur 2x 50er, 2x10er, 1x5er

wähle 50er
wähle 50er
wähle 10er
-> wähle 5er,
Stand 1,15 und nun nicht mehr genug kleine Münzen (nur 1er wären ok) da, um Restbetrag auszugleichen,
also die nächsthöhere Münze drauf,
wähle 10er
-> Stand 1,25 und nun alle Münzen entfernen 'wo geht' , angefangen mit den kleinsten, also 5er weg und fertig

--------

beim Zurücknehmen, wenn man eine höhere Münze draufpacken müsste, könnte man noch überlegen, ob was zu optimieren ist,
wenn man etwa zwei 2er entfernt obwohl es besser wäre einen zuviel gezahlten 5er zurückzunehmen,

aber mir fällt kein Beispiel ein, wo das auftritt,
das beweist zwar nicht, dass es keins gibt, aber damit endet mein Posting

 

[L-ectron-X]

erst mal verschoben

 

[gd12]

Noch ein Beispiel:

Es sind vorhanden: 2x 50, 3x 10, 2x 5 Cent

Wechselgeld: 126 Cent

-> nimm 50 Cent
-> nimm 50 Cent
-> nimm 10 Cent
-> nimm 10 Cent
noch 6 Cent auszugebender Betrag

Jetzt müsste der Algorithmus aber nicht die 2x 5 Cent Münzen ausgeben, sondern noch die letzte 10 Cent Münze, da ja so wenig wie möglich Münzen ausgegeben werden sollen.

 

[Marco13]

Stimmt

 

[SlaterB]

so wenig Münzen wie möglich habe bisher nicht bedacht, bzw. schnell wieder vergessen nachdem 5+1 ausreichend <= 3x 2 waren,

für das Beispiel wäre dann ausreichend, am Ende nochmal eine Optimierung drüber laufen zulassen, die jeweils y kleinere Münzen durch eine passende größere ersetzt


----

gesucht 49
zunächst vier 10er + zwei 5er
-> optimiert zu fünf 10er
-> optimiert zu einem 50er

 

[Marco13]

Wenn man das mit einem Rekursiven Greedy-Backtrackingalgorithmus löst (ja, manchmal ist es toll, sich wie ein kompletter Fachidiot anzuhören) wird das mit der "naträglichen Opimierung" aber IMHO .. nicht so hübsch .. ins Konzept passen ... aber geht natürlich...

 

[SlaterB]

und auch nur in diesem Fall, wenn die Münzen so gut passen,
bei 7 Cent, 12 Cent, 18 Cent sollte man das nicht mehr versuchen

 

[gd12]

Wie müsste ich dann schlussendlich diese Problem umsetzen?
Rekursiv oder Iterativ? Und was ist Backtracking?

 

[SlaterB]

Backtracking kannst du bei google eingeben und da solltest du erstmal viel lesen, wenn dir das nix sagt,

Rekursiv oder Iterativ ist äquivalent, eine reine Organisationsfrage, ändert am Inhalt eines Algorithmus eher wenig

 

[Marco13]

Wobei sich viele solcher Algorithmen (wie z.B. Backtracking) rekursiv einfacher und intuitiver aufschreiben lassen.

EDIT: Ob das für diesen (der ja einige spezielle Aspekte enthält) auch gilt, kann ich aber spontan nicht sagen)

 

[samy88]

müsste in etwa so aussehen

int eingeworfenesgeld = 500; // 500 cent
int anzahlfünfziger= 0;
int anzahlzwanziger= 0;
int anzahlzehner= 0;
int rest=0;



while(eingeworfenesgeld > 0){

if(eingeworfenesgeld >= 50){

anzahlfünfziger++;
eingeworfenesgeld - 50;

}if else(eingeworfenesgeld >= 20){

anzahlzwanziger++;
eingeworfenesgeld - 20;

}if else(eingeworfenesgeld >= 10){

anzahlzehner++;
eingeworfenesgeld - 10;

}else{

rest = eingeworfenesgeld;

}

}

 

[SlaterB]

so einfach ist es nicht:
> Jede der verschiedenen Münzen steht nur mit einer begrenzten Anzahl zur Verfügung.

 

[samy88]

int eingeworfenesgeld = 500; // 500 cent
int anzahlfünfziger= 0;
int anzahlzwanziger= 0;
int anzahlzehner= 0;
int rest=0;

int anzahlfünfziger2=  anzahl vorhandener münzen;
int anzahlzwanziger2= anzahl vorhandener münzen;
int anzahlzehner2= anzahl vorhandener münzen;



while(eingeworfenesgeld > 0){

if(eingeworfenesgeld >= 50 && anzahlfünfziger2 > 0){

anzahlfünfziger++;
eingeworfenesgeld - 50;

}if else(eingeworfenesgeld >= 20 && anzahlzwanziger2 > 0){

anzahlzwanziger++;
eingeworfenesgeld - 20;

}if else(eingeworfenesgeld >= 10 && anzahlzehner2 > 0){

anzahlzehner++;
eingeworfenesgeld - 10;

}else{

rest = eingeworfenesgeld;

}

}

 

[samy88]

Das ist übrigens eine Prüfungsaufgabe vom Berufskolleg
Prüfungen findet ihr hier Programmiertechnik@WvSS Mannheim
Da sind die Aufgaben und Lösungen dabei