Methoden Bezahlalgorithmus bei Kassenautomat - Sackgasse

[slopsucker]

Hallo Community,

nach erfolgloser Suche und erschöpftem Gehirnschmalz bin ich hier gelandet, und hoffentlich könnt ihr mir auch weiterhelfen! Zuerst mal zu meiner Person, ich heiße Jan und bin 20 Jahre alt, Fachinformatiker im 2. Lehrjahr und bei mir zählt das Motto "geht nicht gibts nicht".

Leider steh ich nun vor einem Problem...

Ich sollte einen Algorithmus Programmieren um eine bestimmte Geldmenge im Kassenautomat zu bezahlen.

Dazu hab ich mir eine Klasse Geldmenge erstellt und einen Enum mit Muenzgrößen.

for (int i = GrößteMünze; i >= KleinsteMünze; i--) {
	Münze ma = i;
	while (wechselgeld >= ma.wert() && geldspeicher.get(ma) > 0) {
		rueckgeld.add(ma);
		geldspeicher.sub(ma);
		wechselgeld -= ma.wert();
	}
}

Ich hoffe der ist einigermaßen Verständlich so (hab die Variablen Namen wegen dem Verständnis angepasst).

Münze ist ein Enum mit den jeweiligen Münzen (10 Cent, 20 Cent usw..) und die Methode wert() gibt einen int Wert zurück der den Cent Wert der Münze repräsentiert. geldspeicher und rueckgeld sind Instanzen der Klasse Geldmenge.

Jetzt habe ich jedoch ein Problem: Dieser Algorithmus würde 60 Cent folgendermaßen zurückgeben:

1x 50 Cent, 1x 10 Cent.

Wenn ich im Geldspeicher 8x 20 Cent habe, aber keine 10 Cent, würde keine Rückgabe erfolgen, weil er ja erst 50 Cent ausgibt und dann bemerkt das er keine 10 Cent mehr hat aber 20 Cent zu groß ist.

Wie wäre es also möglich immer die größtmöglichen Münzen laut vorhandenen Geldspeicher auszugeben?

Er müsste irgendwie überprüfen: Wenn 1x 50 Cent + 1x 10 Cent = erfolglos, Dann 3x 20 Cent usw... bei natürlich allen Möglichkeiten von bis zur Geldart 20 Euro.

Ich steh total am schlauch, weiß jemand weiter?

 

[SlaterB]

du brauchst Backtracking/ Zurücklegen,
merke dir die Münzen in einer Liste oder die Zahlen pro Münzart an sich,

wenn du mit einer Kombination in einer Sackgasse angekommen bist,
dann gehe die Liste rückwärts durch und streiche die letze Münze
(nicht unbedingt alle dieser Art, vielleicht aber bei späterem Backtracking)
so dass dann mit der nächstkleineren fortgefahren werden kann,
dafür braucht es eine übergeordnete Schleife, bisschen Arbeit, Rekursion wäre je nach Code-Geschmack übersichtlicher

das kann allerdings in Reinform zu unzähligen durchzuprüfenden Kombinationen führen,
wobei ja nur relativ wenig Stellen wirklich zu prüfen sind,
für alle 'Münzen' ausser 5 Cent 50 Cent + 5 Euro ist es eh sinnlos,

und selbst bei den 5ern reicht es, das genau einmal zu probieren, wenn also von 2 auf eine Münze reduziert wurde,
lohnt später doch nicht, es nochmal mit 0 Münzen dieser Art zu probieren,


naja, da bleibt noch viel Arbeit, nur grob angerissen

 

[slopsucker]

Danke SlaterB,

so einen ähnlichen Ansatz hab ich mir auch gedacht, nur ich glaube bei der Umsetzung hast du andere Vorstellung.

Wenn ich mir die letzte Münze merke, geht das ja nur mit EINER anderen Kombination und auch nur mit der nächstkleineren oder?

Sagen wir einmal ich hab folgende Münzen: 10 Cent, 20 Cent, 50 Cent, 1 Euro, 2 Euro...

Mein Geldspeicher hat folgenden Array (Index repräsentiert die Münze aufsteigend)
{0,4,1,0,0}

Und ein Wechselgeld von 80 Cent. Er gibt zuerst 1x50 Cent zurück, dann 1x 20 Cent. Merkt bei 10 Cent, dass keine Münze vorhanden ist und springt zurück auf 20 Cent. Ab dort versucht er es wieder, aber geht logischerweise nicht. Muss ich mir sozusagen die ganze "Transaktion", jeden Schritt bzw. jede Möglichkeit abspeichern? Bei 5 Münzen wäre das ja die Fakultät von 5 - sprich 120 Möglichkeiten. Oder liege ich grad falsch? :S

Ich hab mal was von nem "Greedy Algorithmus" gehört, aber der soll angeblich ungenau sein, und wie der in Java aussieht wüsste ich auch nicht.

Kannst du mir ein grobes Beispiel nennen wie du das mit der Übergeordneten Schleife meinst?

 

[SlaterB]

mit der einen Kombination hast du recht, eine komplette weitere Schleife usw. wäre dann doch vermeidbar und damit schon wieder Geschichte,
mein neuer Vorschlag nun:
wenn mit einer der 1er-Positionen fertig (Wechsel zur nächsten 5er) dann zurückblicken auf die letzte Serie 5er, 2er, 1er,
falls ungerade Anzahl 5er, kein 1er augewählt aber ein 1er noch passen würde (demnach also keine 1er vorhanden),
und außerdem noch 3 2er vorhanden, genau dann den 5er entfernen und durch 3 2er ersetzen

das kann man mehr oder weniger direkt in ein if an die richtige Position einbauen,
mit Enum auch einigermaßen so dass kein doppelter Code benötigt wird, die Münzen untereinander verknüpfen

------

eine andere Idee, stand vorher schon kurz als edit im ersten Posting:
vielleicht lohnt sich auch der Weg andersrum,
alles zunächst nur mit kleinen Münzen aufbauen, und dann nach gewissen Regeln ersetzen:
70 Cent = 7x 10 Cent
falls 20er vorhanden sind: leichte Ersetzung, 2 10er = 1 20er
-> 3x 20 Cent + 10 Cent
falls 50er vorhanden: mehrere Regeln, etwa wie angesprochen 3x 20 = 50 + 10,
mit höherer Priorisierung, weil vorteilhafter aber die Regel 2x 20 + 10 durch 1x 50 ersetzen,
das ist hier der Fall -> 1x 50 Cent + 1x 20 Cent

komplexe Probleme wie dass die andere Regel besser wäre um die 10 Cent drinzubehalten damit diese
woanders noch günstig getauscht werden können sollten nicht bestehen,
dafür ist das ganze zu gering vernetzt

dieser Aufbau von kleinen Münzen aus müsste eindeutig zum Ziel führen,
allerdings mit im Durchschnitt mehr Schritten, da man immer zunächst mit vielen kleinen Münzen hantiert


bisschen kompliziert wird es dann aber doch durch die Begrenzheit der Münzen,
dann muss auch schonmal 10x 10 Cent durch einen Euro ersetzt werden usw.,
nix nur mit einfachen Regeln, lohnt wohl nicht

 

[rudi888]

ich würde schon so rangehen das ich mir die größte Münze suche also 50 cent diesen wert würde ich in einer variablen zwischenspeichern wenn dann die rechnung nicht aufgeht welches ich in einer bool hinterlegen würde nehme einfach die nächt kleinere münze also 20 cent wenn keine kleinere münze vorhanden ist ist das wechseln nicht möglich

Gruß
Rudi

 

[slopsucker]

Hi Rudi888,

das hab ich auch schonmal probiert, das funktioniert leider auch nicht.

Nehmen wir das Beispiel 2.80 als Wechselgeld und die Geldmenge {0,4,1,0,1}

Er gibt 1x2 Euro, 1x50, 1x20 und dann scheitert er.

Mit deiner Methode macht er dann bei 50 Cent weiter, und scheitert natürlich erneut.

Ich komm einfach nicht auf eine Lösung... grml.

 

[rudi888]

dann tenne doch 100er euro 10er euro 1er euro cent bleibt über
ich hoffe du weist was ich meine

Gruß
Rudi

 

[SlaterB]

zwischen Euro und Cent bzw. generell den Ebenen kann man vielleicht nicht trennen,
falls 24 Euro durch 20 Euro + 8x 50 Cent ausgegeben werden müssen als bestmögliche Variante

die 5er-Frage muss auch nicht unbedingt nur bei Sackgassen auftreten, je nach Anforderungen könnte
3x 20 Cent besser sein als 50 Cent + 10x 1 Cent

 

[rudi888]

beispiel 3,80€ 1x2€ 1€ ist nicht vorhanden dann umrechnen in cent = 180 cent = 3x50 + 1x20 + 1x10 oder 2x50 + 4x20
sollte doch kein prob sein

Gruß
Rudi

 

[SlaterB]

also muss mehrfach geschaut werden,
erst ob ein Euro-Betrag mit 5 Euro funktioniert, dann mit 2 Euro,
dann ist nicht Ende wie du meintest ("nehme einfach die nächt kleinere münze also 20 cent wenn keine kleinere münze vorhanden ist ist das wechseln nicht möglich")
sondern es geht mit den nächsten Münzen weiter

 

[rudi888]

so sehe ich das aber ich bin auch nicht das maß aller dinge
ich würde da so rangehen

bei bsp 5,50 1€ münze ist nicht vorhanden und 5€ scheine gibt es nicht

den wert aufteilen und in int packen

int euro = 5
int cent = 50

nächt kleinere Münze von 5 = 2
5/2 = 2 rest 1
1 ist nicht vorhanden
kleiner in euro geht nicht dann 1*100 = 100
cent += 100
nächst kleinere Münze = 50
150/ 50 = 3
die sind vorhanden
also fertig
nicht vorhanden
nächt kleinere münze
150/20
usw.

gruß
Rudi

 

[SlaterB]

ich weiß nicht genau welches Thema du verfolgst und will auch nicht zuviel meckern, aber ein Hinweis:

> bei bsp 5,50 1€ münze ist nicht vorhanden und 5€ scheine gibt es nicht

das ursprüngliche Problem war doch gerade, dass 5 vorhanden ist,
bzw. bei 5.50 gibt es ja überhaupt keine Frage wie 5 durch 2 zu ersetzen sein könnte,

dagegen: 6 Euro, 5 abgezogen, Rest reicht nicht, 3x 2 Euro wären aber da

 

[faetzminator]

rudi888, wie kommst du auf umrechnen?
Einfach den Betrag und alle Münzen/Noten in Cents speichern und dann muss man nichts umrechnen.

den wert aufteilen und in int packen
int euro = 5
int cent = 50

Nein :autsch:

 

[California]

Stell Dir vor, du legst die Münzen auf Stapel, sortiert nach Wert.
Dann nimmst Du von einem Stapel solange (erstmal eine...) Münze(n) herunter, wie Münzen da sind und die Restsumme größer ist als der Münzwert. Danach zum nächstkleineren Wert.
ähm.. ich glaub ich schreib mal was von Papier und Bleistift in meine Signatur...
was man nicht mit P&B zeigen kann kann man auch nicht programmieren...

Siehe hier:

package de.biprod.sandbox;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Cashier {
	// aus dem Handgelenk ohne Anspruch auf volle Richtigkeit

	private Amount moneyInCash;

	public static void main( String[] args ) {
		Cashier cashier = new Cashier();

		System.out.println( "Total in cash: " + cashier.getMoneyInCash().getTotal() );
		display( cashier.getMoneyInCash().pay( 150 ) );
		System.out.println( "Total in cash: " + cashier.getMoneyInCash().getTotal() );
		display( cashier.getMoneyInCash().pay( 70 ) );
		System.out.println( "Total in cash: " + cashier.getMoneyInCash().getTotal() );
		display( cashier.getMoneyInCash().pay( 234 ) );
		System.out.println( "Total in cash: " + cashier.getMoneyInCash().getTotal() );
	}

	public Cashier() {

		moneyInCash = new Amount();
		moneyInCash.addCoins( 50, 11 );
		moneyInCash.addCoins( 20, 1 );
		moneyInCash.addCoins( 10, 11 );
		moneyInCash.addCoins( 5, 11 );
		moneyInCash.addCoins( 2, 11 );
		moneyInCash.addCoins( 1, 11 );
	}

	public Amount getMoneyInCash() {
		return moneyInCash;
	}

	public static void display( Amount amount ) {

		System.out.println( "Total amount: " + amount.getTotal() );
		for (CoinStack coinStack : amount.getCoinStacks()) {
			System.out.println( "total: " + coinStack.getTotal() + " value: " + coinStack.getValue() + " count: " + coinStack.getCount() );
		}
	}

	private class Amount {
		private List<CoinStack> coinStacks;

		public List<CoinStack> getCoinStacks() {

			if (null == coinStacks) {
				coinStacks = new ArrayList<Cashier.CoinStack>();
			}
			return coinStacks;
		}

		public void setCoinStacks( List<CoinStack> coinStacks ) {
			this.coinStacks = coinStacks;
		}

		public void addCoinStack( CoinStack coinStack ) {
			getCoinStacks().add( coinStack );
			Collections.sort( getCoinStacks() );
		}

		public CoinStack findCoinStack( int value ) {
			CoinStack result = null;

			for (CoinStack coinStack : getCoinStacks()) {
				if (value == coinStack.getValue()) {
					result = coinStack;
					break;
				}
			}
			if (null == result) {
				result = new CoinStack( value, 0 );
				addCoinStack( result );
			}
			return result;
		}

		public void addCoins( int value, int count ) {
			findCoinStack( value ).addCoins( count );
		}

		public boolean hasMoney() {

			return (0 != getTotal());
		}

		public int getTotal() {
			int result = 0;

			for (CoinStack coinStack : getCoinStacks()) {
				result += coinStack.getTotal();
			}
			return result;
		}

		public Amount pay( int sum ) {
			int work = sum;
			Amount result = new Amount();

			while ((0 != work) && hasMoney()) {
				for (CoinStack coinStack : getCoinStacks()) {
					if (coinStack.hasCoins() && (work >= coinStack.getValue())) {
						result.addCoins( coinStack.value, 1 );
						coinStack.takeCoin();
						work -= coinStack.value;
						break;
					}
				}
			}
			return result;
		}
	}

	private class CoinStack implements Comparable<CoinStack> {
		private int value;
		private int count;

		public CoinStack( int value, int count ) {
			this.value = value;
			this.count = count;
		}

		public boolean hasCoins() {
			return 0 != count;
		}

		public int getValue() {
			return value;
		}

		public void setValue( int value ) {
			this.value = value;
		}

		public int getCount() {
			return count;
		}

		public void setCount( int count ) {
			this.count = count;
		}

		public void addCoins( int count ) {
			this.count += count;
		}

		public void takeCoin() {
			--count;
		}

		public int getTotal() {
			return value * count;
		}

		@Override
		public int compareTo( CoinStack that ) {
			return that.value - this.value;
		}
	}
}

Hausaufgaben:
- finde den Schwachpunkt (es gibt Potential für eine Endlosschleife, hehe)
- die pay() Methode lässt sich noch mit Anzahl Münzen optimieren, statt immer nur eine Münze vom Stapel zu nehmen
- "nicht genug Geld für die Summe" fehlt noch
- takeCoin() ist unsicher (warum?)