OOP Banknoten Algorithmus Teil 2

[alex_fairytail]

Hallo und willkommen zu meinem 3. Thread wegen eines einzigen Projekts, ich hoffe Ihr seid so gnädig mich trotzdem zu unterstützen...
Dieser Algorithmus bereitet mir kopfzerbrechen:

Wie schonmal geschrieben musste ich erst einen Betrag in verschiedene Banknoten aufteilen (CH-Noten: 1000, 200, 100, 50, 20, 10). Dieser Algorithmus funktioniert, ich bekomme ein Array bei dem an der Stelle 0 die Anzahl Tausender stehen, an der Stelle 1 die Anzahl 200er usw.
Ich habe ausserdem den verfügbaren Bestand der Banknoten nach dem selben Schema in einem zweiten Array.

Was ich nun brauche ist ein Algorithmus, der die beiden Arrays vergleicht und, falls es von einer Note mal zu wenig haben sollte, diese auf andere Noten aufteilt. Tricky dabei ist ja, das die Noten nicht linear kleiner werden. Ausserdem kann man eine Note nicht nur in die nächstkleineren sondern im Falle von z.B. 2 50ern auch in die nächstgrösseren (1 100er) aufteilen.
Jetzt bin ich ziemlich ratlos... Meinen momentanen Stand findet ihr unten, aber das funktioniert so nicht immer richtig... :bahnhof:

Vielen Dank schonmal!

PS: Falls nötig bitte ins Matheboard verschieben, rein technisch gesehen ist es ja kein Java-spezifisches Problem.

public class bestandsalgorithmus{
	public static void main(String[] args){
		int[] def_bestand = {0,1,200,1,1,1}; // Soviel von jeder Note ist vorhanden, atm also keine 1000er
		int[] def_betrag =   {1,1,1,1,1,1}; // Der Betrag, 1380 Fr.
		int[] test = new int[def_bestand.length];

		test = mtest(def_betrag, def_bestand);

		for(int i=0; i < def_bestand.length; i++){
			System.out.println(test[i]);
		}
	}
	static  int[] mtest(int[] arg_betrag, int[] arg_bestand){
		int[] betrag = arg_betrag;
		int[] bestand = arg_bestand;

		for(int i=0; i < bestand.length; i++){
			if(bestand[i] < betrag[i]){
				int diff = betrag[i]-bestand[i];
				bestand[i] = bestand[i]-(betrag[i]-diff);

				System.out.println("test"+bestand[i]);
				System.out.println("test"+betrag[i]);

				switch(i){

					case 0:
						betrag[1] = betrag[1]+ 5*betrag[i];
					break;


					case 1:
						betrag[2] = betrag[2] + 2*betrag[i];
					break;


					case 2:
						betrag[3] = betrag[3] + 2*betrag[i];
					break;


					case 3:
						if(betrag[i] % 2 == 0){
							betrag[4] = betrag[4]+(5*betrag[i])/2;
						}else{
							betrag[4] = betrag[4] + ((5*betrag[i]) -1)/2;
							betrag[5] = betrag[5] + 1;
						}
					break;


					case 4:
						betrag[5] = betrag[5] + 2*betrag[i];
					break;

                                        case 5:
                                                if(betrag[5] >= bestand[5]){

                                                }
                                        break;

				}

				betrag[i] = betrag[i]-diff;

			}
		}
		return betrag;
	}
}

 

[Marco13]

Nur kurze Zwischenfrage: Täuscht mich das, oder ist das irgendein NP-hartes Packingproblem (im Stil von Bin Packing oder Knapsack)?

EDIT: Ach nee, es soll ja schon immer versucht werden, die größten zu nehmen... dann ist das wohl nicht NP-hard (*mehr Cola zum rausschwitzen sauf*)

 

[TiME-SPLiNTER]

Nur mal eine kleine Frage: Was machst du wenn der Betrag durch den Bestand nicht gedeckt werden kann? Sprich der Bestand enthält die ungünstige Kombination an Noten, die den Betrag nicht nach diesen auflösen lässt?

 

[alex_fairytail]

Nur mal eine kleine Frage: Was machst du wenn der Betrag durch den Bestand nicht gedeckt werden kann? Sprich der Bestand enthält die ungünstige Kombination an Noten, die den Betrag nicht nach diesen auflösen lässt?

Sollte es tatsächlich nicht möglich sein, wenn z.B. 30 Sfr. gewünscht sind und keine 10er mehr da sind wird dies dem Benutzer gemeldet und er wird gebeten, einen anderen Betrag einzutippen. Also naja, momentan wird das noch nicht gemacht, aber so werde ich es dann umsetzen

 

[Michael...]

Tricky dabei ist ja, das die Noten nicht linear kleiner werden. Ausserdem kann man eine Note nicht nur in die nächstkleineren sondern im Falle von z.B. 2 50ern auch in die nächstgrösseren (1 100er) aufteilen.

Du verfolgst doch sicherlich beim Zerlegen der Summe eine Strategie? z.B. möglichst wenige/"große" Scheine zu verwenden. Dann kann der Fall garnicht auftreten, dass man zwei fehlende 50er durch einen 100er ersetzen muss.
Ich würde mir eine Hilfsmethode schreiben, die mir den Betrag zerlegt, der ich aber z.B. den gößten zu verwendenen Schein vorgeben kann:

	static int[] notes = {1000, 200, 100, 50, 20, 10};	//Notenwerte
	static int[] stock = {5, 5, 5, 0, 0, 10};			//verfuegbare Noten

	public static void main(String[] s) throws InterruptedException {
		int betrag = 1380;
		int[] numOfNotes = calcNumOfNotes(betrag, 0);
		
		System.out.println("Auszahlung mit moeglichst grossen Scheinen:");
		for (int i=0; i<notes.length; i++)
			System.out.println(numOfNotes[i] + " x " + notes[i]);
		
		for (int i=0; i<notes.length; i++) {
			if (numOfNotes[i]>stock[i]) {
				int[] buffer = calcNumOfNotes((numOfNotes[i]-stock[i])*notes[i], i +1);
				numOfNotes[i] = stock[i];
				for (int k=0; k<notes.length; k++)
					numOfNotes[k] +=buffer[k];
				if (i>=notes.length) {
					System.out.println("**************************************");
					System.out.println("Auszahlung des Betrags nicht moeglich!");
					System.out.println("**************************************");
				}
			}
		}
		
		System.out.println("Auszahlung auf Basis vorhandener Scheine:");
		for (int i=0; i<notes.length; i++)
			System.out.println(numOfNotes[i] + " x " + notes[i]);
	}
	
	public static int[] calcNumOfNotes(int value, int minIndex) {
		int rest = value;
		int[] numOfNotes = new int[notes.length];
		for (int i=minIndex; i<notes.length; i++) {
			numOfNotes[i] = rest/notes[i];
			rest %=notes[i];
		}
		if (rest>0)
			System.out.println("Achtung: Restbetrag von " + rest + " vorhanden!");
		return numOfNotes;
	}

 

[TiME-SPLiNTER]

Ich habe auch einen Ansatz gemacht:

static  int[] mtest(int[] arg_betrag, int[] arg_bestand){
        int[] betrag = arg_betrag;
        int[] bestand = arg_bestand;
 
        Map<Integer,Integer> argBestandMap = new HashMap<Integer, Integer>();
        argBestandMap.put(10, arg_bestand[5]);
        argBestandMap.put(20, arg_bestand[4]);
        argBestandMap.put(50, arg_bestand[3]);
        argBestandMap.put(100, arg_bestand[2]);
        argBestandMap.put(200, arg_bestand[1]);
        argBestandMap.put(1000, arg_bestand[0]);
        
        Map<Integer,Integer> argBetragMap = new HashMap<Integer, Integer>();
        argBetragMap.put(10, arg_betrag[5]);
        argBetragMap.put(20, arg_betrag[4]);
        argBetragMap.put(50, arg_betrag[3]);
        argBetragMap.put(100, arg_betrag[2]);
        argBetragMap.put(200, arg_betrag[1]);
        argBetragMap.put(1000, arg_betrag[0]);
        
        Map<Integer,Integer> outMap = new HashMap<Integer, Integer>();
        
        // Berechne betrag
        double betragTotal = 0;
        for(Map.Entry<Integer, Integer> betragCount : argBetragMap.entrySet()) {
        	betragTotal += betragCount.getKey()*betragCount.getValue();
        }
        
        System.out.println("BETRAG: " + betragTotal);
        
        // Aufteilen
        for(Map.Entry<Integer, Integer> bestandCount : argBestandMap.entrySet()) {
        	if(bestandCount.getValue() <= 0)
        		continue;
        	
        	double notes = Math.floor(betragTotal/(double)bestandCount.getKey());
        	
        	System.out.println("Note: " + bestandCount.getKey() + ", Vorhanden: " + bestandCount.getValue() + " , Gebraucht: " + notes);
        }
        
        return betrag;
    }

Wenn du diese Methode aufrufst kommt folgender Output:

BETRAG: 1380.0
Note: 50, Vorhanden: 1 , Gebraucht: 27.0
Note: 100, Vorhanden: 200 , Gebraucht: 13.0
Note: 200, Vorhanden: 1 , Gebraucht: 6.0
Note: 20, Vorhanden: 1 , Gebraucht: 69.0
Note: 10, Vorhanden: 1 , Gebraucht: 138.0
1
1
1
1
1
1

Du hast nun also den Betrag (1380.0) und du weist wie viel Mal du eine Note mit einem bestimmten Wert nehmen musst um __möglichst nahe__ an den Betrag heranzukommen.

Jetzt kannst du dich diesen Informationen bedienen und die Notenkombination zusammenstellen (das habe ich nicht mehr gemacht ;-)). Immer wenn du eine Note genommen hast vom Bestand, deren Wert vom betragTotal abziehen, bis der == 0 ist. Wird er nicht == 0 dann kann der Betrag nicht aufgelöst werden.

 

[alex_fairytail]

Du verfolgst doch sicherlich beim Zerlegen der Summe eine Strategie? z.B. möglichst wenige/"große" Scheine zu verwenden. Dann kann der Fall garnicht auftreten, dass man zwei fehlende 50er durch einen 100er ersetzen muss.
Ich würde mir eine Hilfsmethode schreiben, die mir den Betrag zerlegt, der ich aber z.B. den gößten zu verwendenen Schein vorgeben kann:

	static int[] notes = {1000, 200, 100, 50, 20, 10};	//Notenwerte
	static int[] stock = {5, 5, 5, 0, 0, 10};			//verfuegbare Noten

	public static void main(String[] s) throws InterruptedException {
		int betrag = 1380;
		int[] numOfNotes = calcNumOfNotes(betrag, 0);
		
		System.out.println("Auszahlung mit moeglichst grossen Scheinen:");
		for (int i=0; i<notes.length; i++)
			System.out.println(numOfNotes[i] + " x " + notes[i]);
		
		for (int i=0; i<notes.length; i++) {
			if (numOfNotes[i]>stock[i]) {
				int[] buffer = calcNumOfNotes((numOfNotes[i]-stock[i])*notes[i], i +1);
				numOfNotes[i] = stock[i];
				for (int k=0; k<notes.length; k++)
					numOfNotes[k] +=buffer[k];
				if (i>=notes.length) {
					System.out.println("**************************************");
					System.out.println("Auszahlung des Betrags nicht moeglich!");
					System.out.println("**************************************");
				}
			}
		}
		
		System.out.println("Auszahlung auf Basis vorhandener Scheine:");
		for (int i=0; i<notes.length; i++)
			System.out.println(numOfNotes[i] + " x " + notes[i]);
	}
	
	public static int[] calcNumOfNotes(int value, int minIndex) {
		int rest = value;
		int[] numOfNotes = new int[notes.length];
		for (int i=minIndex; i<notes.length; i++) {
			numOfNotes[i] = rest/notes[i];
			rest %=notes[i];
		}
		if (rest>0)
			System.out.println("Achtung: Restbetrag von " + rest + " vorhanden!");
		return numOfNotes;
	}

Ich habe so eine Methode, der wird der Betrag übergeben und die teilt mir das dann in Noten auf (d.h. gibt mir das Array zurück).
Die geht eigtl. nach diesem Prinzip vor, soviele Grosse wie möglich, wenn nicht mehr möglich springts zur nächst kleineren.
Die Aufteilung klappt schon, ich scheitere immer daran das Array mit der Aufteilung mit dem wo der Bestand drin ist abzugleichen...

 

[alex_fairytail]

Output:

BETRAG: 1380.0
Note: 50, Vorhanden: 1 , Gebraucht: 27.0
Note: 100, Vorhanden: 200 , Gebraucht: 13.0
Note: 200, Vorhanden: 1 , Gebraucht: 6.0
Note: 20, Vorhanden: 1 , Gebraucht: 69.0
Note: 10, Vorhanden: 1 , Gebraucht: 138.0
1
1
1
1
1
1

Du hast nun also den Betrag (1380.0) und du weist wie viel Mal du eine Note mit einem bestimmten Wert nehmen musst um __möglichst nahe__ an den Betrag heranzukommen.

Jetzt kannst du dich diesen Informationen bedienen und die Notenkombination zusammenstellen (das habe ich nicht mehr gemacht ;-)). Immer wenn du eine Note genommen hast vom Bestand, deren Wert vom betragTotal abziehen, bis der == 0 ist. Wird er nicht == 0 dann kann der Betrag nicht aufgelöst werden.

Interessante Idee... Ich versuch's mal. Könntest du mir evtl. noch kurz sagen was es mit dem Hashmap auf sich hat?

 

[Michael...]

Die Aufteilung klappt schon, ich scheitere immer daran das Array mit der Aufteilung mit dem wo der Bestand drin ist abzugleichen...

Das macht ja die mittlere for Schleife.

 

[TiME-SPLiNTER]

Die HashMap ist eigentlich ein Array, dem man aber Key => Value angeben kann.

Also eine leere HashMap<Key-Class,Value-Class> habe ich so initialisiert: HashMap<Integer,Integer>.

Ich habe dann gesagt, dass der Key der Wert der Note ist z.B. 50 und der Value ist, wieviele Noten z.B. 3.

Das heisst das man ein Element der HashMap folgendermassen hinzufügen würde: hashMap.put(key,value) => hashMap.put(50,3). Danach weiss ich immer welche Note wieviele Stück hat.

Was ich noch vergessen habe, du musst die HashMap noch dem Key nach absteigend sortieren, sonst funktioniert es nicht, wenn man über die HashMap iteriert.

 

[alex_fairytail]

Das macht ja die mittlere for Schleife.

Habs grade gesehen danke

Die HashMap ist eigentlich ein Array, dem man aber Key => Value angeben kann.

Also eine leere HashMap<Key-Class,Value-Class> habe ich so initialisiert: HashMap<Integer,Integer>.

Ich habe dann gesagt, dass der Key der Wert der Note ist z.B. 50 und der Value ist, wieviele Noten z.B. 3.

Das heisst das man ein Element der HashMap folgendermassen hinzufügen würde: hashMap.put(key,value) => hashMap.put(50,3). Danach weiss ich immer welche Note wieviele Stück hat.

Was ich noch vergessen habe, du musst die HashMap noch dem Key nach absteigend sortieren, sonst funktioniert es nicht, wenn man über die HashMap iteriert.

Okay gut zu wissen vielen Dank

 

[TiME-SPLiNTER]

Oke ich konnt's nicht lassen, ich habe sie noch fertig geschrieben:

import java.util.HashMap;
import java.util.Map;
import java.util.NavigableMap;
import java.util.TreeMap;

public class bestandsalgorithmus{
    public static void main(String[] args){
        int[] def_bestand = {0,1,200,1,1,1}; // Soviel von jeder Note ist vorhanden, atm also keine 1000er
        int[] def_betrag =   {1,1,1,1,1,1}; // Der Betrag, 1380 Fr.
        Map<Integer,Integer> test;
 
        test = mtest(def_betrag, def_bestand);
 
        System.out.println("====================\nBetrag wurde aufgeteilt in:");
        for(Map.Entry<Integer, Integer> entry : test.entrySet()){
            System.out.println("Note: " + entry.getKey() + ", Anzahl: " + entry.getValue());
        }
    }
    static  Map<Integer,Integer> mtest(int[] arg_betrag, int[] arg_bestand){
        NavigableMap<Integer,Integer> argBestandMap = new TreeMap<Integer, Integer>();
        argBestandMap.put(1000, arg_bestand[0]);
        argBestandMap.put(200, arg_bestand[1]);
        argBestandMap.put(100, arg_bestand[2]);
        argBestandMap.put(50, arg_bestand[3]);
        argBestandMap.put(20, arg_bestand[4]);
        argBestandMap.put(10, arg_bestand[5]);
        
        NavigableMap<Integer,Integer> argBetragMap = new TreeMap<Integer, Integer>();
        argBetragMap.put(1000, arg_betrag[0]);
        argBetragMap.put(200, arg_betrag[1]);
        argBetragMap.put(100, arg_betrag[2]);
        argBetragMap.put(50, arg_betrag[3]);
        argBetragMap.put(20, arg_betrag[4]);
        argBetragMap.put(10, arg_betrag[5]);
        
        Map<Integer,Integer> outMap = new HashMap<Integer, Integer>();
        
        // Berechne betrag
        double betragTotal = 0;
        for(Map.Entry<Integer, Integer> betragCount : argBetragMap.entrySet()) {
        	betragTotal += betragCount.getKey()*betragCount.getValue();
        }
        
        System.out.println("BETRAG: " + betragTotal);
        
        // Aufteilen
        
        for(Map.Entry<Integer, Integer> bestandCount : argBestandMap.descendingMap().entrySet()) {
        	if(bestandCount.getValue() <= 0)
        		continue;
        	
        	Double notes = Math.floor(betragTotal/(double)bestandCount.getKey());
        	
        	System.out.println("Note: " + bestandCount.getKey() + ", Vorhanden: " + bestandCount.getValue() + " , Gebraucht: " + notes);
       
        	if(notes > bestandCount.getValue()) {
        		outMap.put(bestandCount.getKey(), bestandCount.getValue());
        		betragTotal -= bestandCount.getKey()*bestandCount.getValue();
        	} else {
        		outMap.put(bestandCount.getKey(), notes.intValue());
        		betragTotal -= bestandCount.getKey()*notes;
        	}
        }
        
        if(betragTotal != 0)
        	return null;
        
        return outMap;
    }
}

Gibt eine HashMap mit Key = NotenWert und Value = Anzahl Noten zurück. Konnte der Betrag nicht auf den übergebenen Bestand aufgelöst werden, wird NULL von der Methode zurückgegeben. Der Vorteil das auf diese Art zu lösen ist, dass beliebig neue Einheiten kommen könnten... also sollte eine Währung vllt 2000er Noten haben wird automatisch auch mit 2000er Noten gerechnet sofern das in den Argumenten angegeben wurde.

Denkbar wäre auch statt NULL zurückzugeben eine eigene Exception zu werfen. Ebenso wäre es von Vorteil die Argumente wären bereits entsprechende Map-Objects und keine Arrays... aber so wie's jetzt ist funktionierts auch .

 

[alex_fairytail]

Oke ich konnt's nicht lassen, ich habe sie noch fertig geschrieben:


Gibt eine HashMap mit Key = NotenWert und Value = Anzahl Noten zurück. Konnte der Betrag nicht auf den übergebenen Bestand aufgelöst werden, wird NULL von der Methode zurückgegeben. Der Vorteil das auf diese Art zu lösen ist, dass beliebig neue Einheiten kommen könnten... also sollte eine Währung vllt 2000er Noten haben wird automatisch auch mit 2000er Noten gerechnet sofern das in den Argumenten angegeben wurde.

Denkbar wäre auch statt NULL zurückzugeben eine eigene Exception zu werfen. Ebenso wäre es von Vorteil die Argumente wären bereits entsprechende Map-Objects und keine Arrays... aber so wie's jetzt ist funktionierts auch .

Hey super! :applaus: Ich schau mir das später noch im Detail an, aber ich glaube damit müsste ich es schaffen ... ;-)

Danke vielmals jedenfalls und guten Appetit wünsch ich! :toll:

 

[TiME-SPLiNTER]

Keine Ursache. En guete!