Programm: Kleinstmögliche Briefmarkenkombination ausgeben

[Goldarm5]

Hi,

ich arbeite zurzeit an einer Aufgabe, in der wir Porto einlesen sollen und dazu dann eine möglichst kleine Kombination aus den Briefmarken 1,45 ; 0,60 ; 0,45 und 0,01 ausgeben sollen. Ich habe schon versucht dies in einer optimierten Version zu machen, also so, dass wirklich IMMER die kleinste Anzahl erreicht werden soll, jedoch gibt es Ungereimtheiten, die ich leider nicht finden kann. Kurz gesagt das Programm macht nicht das was es eigentlich soll.

Kurz zusammengefasst, was das Programm machen soll:

1. Porto wird eingelesen
2. Es wird berechnet wie viele Briefmarken der Sorten 1,45;0,60 und 0,45 maximal ins Porto passen und 1 addiert (das kommt erst später zum tragen und könnte geändert werden)
3. Beginn der while-Schleife, die ausgeführt wird solange die tatsächliche Anzahl der Briefmarken noch kleiner ist als die maximale
4. Das Restporto wird berechnet aus dem Wert der Briefmarken und der momentan verwendeten tatsächlichen Anzahl ( ist beim ersten mal für alle Briefmarken = 0)
5. Falls das Restporto größer 0 ist wird es mit 100 multipliziert um die Anzahl der 0,01er Briefmarken zu erhalten
6. Wenn nun das Restporto = 0 ist wird die Gesamtzahl der Briefmarken errechnet
7. Wenn die Gesamtzahl der Briefmarken kleiner als die gespeicherte Gesamtzahl ist wird die Gesamtzahl, sowie die einzelnen Anzahlen gespeichert
8. Wenn die momentane Anzahl der Marken 1,45 und 0,60 noch kleiner ist als deren Maximum wird die Anzahl der 0,45er Marken um 1 erhöht
9. Wenn dabei die maximale Anzahl an 0,45er Marken erreicht wird, wird deren Anzahl auf 0 gesetzt und die der 0,60er um 1 erhöht
10. Wenn dabei die maximale Anzahl der 0,60er Marken erreicht wird, wird deren Anzahl auf 0 gesetzt und die der 1,45er um 1 erhöht
(schleifenende und wieder zum Anfang) durch die letzten drei Schritte soll erreicht werden, dass jede mögliche Kombination durchgegangen wird und die kleinsten dabei immer wieder abgespeichert bis man schließlich, da man ja alle Kombinationen durchgeht, die kleinstmögliche hat
Außerdem kommt in diesen Schritten das +1 bei der maxAnzahl zum tragen, da nun erst gestoppt wird die "kleinste" Einheit (0,45er) zu erhöhen wenn das maximimum der vorigen überschritten ist
11. Die Gesamtzahl an Briefmarken wird ausgegeben, die man braucht
12. Falls die gespeicherte Anzahl der einzelnen Briefmarken größer als 0 ist wird die gespeicherte Anzahl der jeweiligen Briefmarke ausgegeben

package de.gpdlabor.aufgabe3;

import java.util.Scanner;

public class GDP3C {
	public static final float MARKE1 = 1.45f;
	public static final float MARKE2 = 0.60f;
	public static final float MARKE3 = 0.45f;
	public static final float MARKE4 = 0.01f;
	public static final int MULTIPLIKATOR = 100;
	public static final int STARTWERT = 200000000;

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		
		float porto = 0f;
		float restporto = 0f;
		int maxAnzahl1 = 0;
		int maxAnzahl2 = 0;
		int maxAnzahl3 = 0;
		int anzahl1 = 0;
		int anzahl2 = 0;
		int anzahl3 = 0;
		int anzahl4 = 0;
		int anzahl1Speicher = 0;
		int anzahl2Speicher = 0;
		int anzahl3Speicher = 0;
		int anzahl4Speicher = 0;
		int gesamtZwischen = 0;
		int gesamtSpeicher = STARTWERT;
		System.out.print("Bitte geben sie den gewünschten Portobetrag ein, das Programm"
		+ " berechnet die kleinste Briefmarkenzusammenstellung.\r\n");
		porto = Float.parseFloat(in.nextLine()); 
		maxAnzahl1 = (int) (porto / MARKE1) + 1;
		maxAnzahl2 = (int) (porto / MARKE2) + 1;
		maxAnzahl3 = (int) (porto / MARKE3) + 1; //Maximal mögliche Anzahl der jeweils zu verwendenden Briefmarken (+1 , was später wichtig ist)
		
		while (anzahl1 < maxAnzahl1 && anzahl2 < maxAnzahl2 && anzahl3 < maxAnzahl3) //führt aus solange die tatsächliche anzahl kleiner als die maximale ist
			{
			restporto = porto - (anzahl1 * MARKE1 + anzahl2 * MARKE2 + anzahl3 * MARKE3); //rechnet das restporto einer briefmarkenkombination aus
			if (restporto > 0) //sollte restporto > 0 über sein wird errechnet wieviele 1 cent briefmarken gebraucht werden
			{
			anzahl4 = (int) (MULTIPLIKATOR * restporto);
			}
			if (restporto == 0) //wenn die kombination das gewünschte porto ergibt, wird die gesamtzahl errechnet
			{
			gesamtZwischen = anzahl1 + anzahl2 + anzahl3 + anzahl4;
			}
			if (gesamtZwischen < gesamtSpeicher && gesamtZwischen > 0) /*sollte die gesamtzahl kleiner als die gespeicherte gesamtzahl sein und 
			größer 0 sein, wird die gesamtzahl gespeicher und die einzelnen anzahlen werden auch gespeichert*/
			{
				gesamtSpeicher = gesamtZwischen;
				anzahl1Speicher = anzahl1;
				anzahl2Speicher = anzahl2;
				anzahl3Speicher = anzahl3;
				anzahl4Speicher = anzahl4;
			}
			
			if (anzahl1 < maxAnzahl1 && anzahl2 < maxAnzahl2)/*die anzahl der breifmarken wird fast wie ein zahlensystem behandelt und hier
				wird dafür gesorgt, dass nach jeder ausführung erhöht wird und falls nötig die nächste stelle des "zahlensystems" erhöht wird*/			
			{
				anzahl3 = anzahl3 + 1;
				if (anzahl3 == maxAnzahl3)
				{
					anzahl3 = 0;
					anzahl2 = anzahl2 + 1;
					if (anzahl2 == maxAnzahl2)
					{
						anzahl2 = 0;
						anzahl1 = anzahl1 + 1;
					}
				}
				
			}
			}
		System.out.print("Sie brauchen insgesamt: " + gesamtSpeicher + " Briefmarken, wie folgt aufgeteilt: \r\n");
		if (anzahl1 > 0)
			/*Nachdem die Schleife zuende ist werden die gespeicherten Werte ausgegeben, die ja auch eigentlich die kleinste Kombination
			  darstellen sollten
			 */
		{
			System.out.print(anzahl1Speicher + "x 1.45\r\n");
		}
		if (anzahl2 > 0)
		{
			System.out.print(anzahl2Speicher + "x 0.60\r\n");
		}
		if (anzahl3 > 0)
		{
			System.out.print(anzahl3Speicher + "x 0.45\r\n");
		}
		if (anzahl4 > 0)
		{
			System.out.print(anzahl4Speicher + "x 0.01\r\n");
		}
		in.close();

	}

}

 

[QwertSmeik]

Ich hab mir dein Programm ein wenig angeschaut und muss sagen, dass es ganz schön wirr ist .

Aber gleich fällt mir auf, dass folgende Bedingung im Allgemeinen NIE erfüllt sein wird:

if (restporto == 0) //wenn die kombination das gewünschte porto ergibt, wird die gesamtzahl errechnet
			{
			gesamtZwischen = anzahl1 + anzahl2 + anzahl3 + anzahl4;
			}

Du testest ja nur die Kombination aus Anzahl1-3. Das ist bei einem Betrag von 1 z.B. nie möglich. Du musst hier irgendwie eine Minimierung hereinbringen.


Hier: Problem mit einem Programm - Pascal - www.programmiersprachen.de
hatte mal jemand ein ähnliches Problem. Anhand der verschiedenen vorgeschlagenen Lösungen kannst du sehr schön erkennen, wie man so ein Problem mit und ohne Arrays angehen kann .
Damals war ich derjenige, der den "Spaghetti-Code" vorgeschlagen hat, heute kann ich dir den Ratschlag geben, es "schöner" zu machen .

Und nebenbei: Es bietet sich hier ein Greedy-Algorithmus an im Gegensatz zu deinem Lösungsweg, alles durchzuprobieren.

 

[Bug Fisher]

Ich würde dir empfehlen, mit ganzen Zahlen in cent Beträgen zu arbeiten;
dann lässt sich das sehr leicht mit ganzzahliger Division und Modulo implementieren.

private static void postStamps(int postageInCents) {
		final int[] values = {145, 60, 45, 1};
		final int[] result = new int[values.length];
		
		for(int i = 0; postageInCents > 0; ++i) {
			final int n = postageInCents/values[i];
			postageInCents %= values[i];
			result[i] = n;
		}
		
		for(int i = 0; i < values.length; ++i) {
			System.out.println(result[i] + " x " + values[i] + " cents");
		}
	}

 

[taro]

@Bug Fisher: Ganz so "sehr leicht" ist das ganze dann doch nicht - frankiere doch einmal einen 2,40 € Maxibrief mit dem von deiner Methode ausgegebenen Frankaturvorschlag

 

[Goldarm5]

Ich hab mir dein Programm ein wenig angeschaut und muss sagen, dass es ganz schön wirr ist .

Aber gleich fällt mir auf, dass folgende Bedingung im Allgemeinen NIE erfüllt sein wird:

if (restporto == 0) //wenn die kombination das gewünschte porto ergibt, wird die gesamtzahl errechnet
			{
			gesamtZwischen = anzahl1 + anzahl2 + anzahl3 + anzahl4;
			}

Du testest ja nur die Kombination aus Anzahl1-3. Das ist bei einem Betrag von 1 z.B. nie möglich. Du musst hier irgendwie eine Minimierung hereinbringen.

Das hab ich geändert, indem ich bei der Berechnung der 1 cent Briefmarken noch
restporto = restporto - (0,01 * anzahl4)
hinzugefügt hab, klappen tuts leider immernoch nicht :/
Die Sache mit den Münzen und Scheinen hat ja nur leider den Vorteil, dass man da ja wirklich stur runtergehen kann.
Wenn man das aber auf die Briefmarken überträgt hat man z.B. bei 1.89 eine 1.45er und 44 0.01er.
Greedy Algorithmus werd ich mir nochmal anschauen.

 

[Bug Fisher]

Backtracking eignet sich, eine (eventuelle) Lösung zu finden, wenn man eine Maximalzahl an Briefmarken eines Wertes vorgibt:

private static boolean postStamp2(	final int postage,
										final  int[] result, final int[] values, 
										final int index, final int maxCount) {
		if(postage == 0) {
			return true;
		}
		
		final int n = postage/values[index];
		
		if(n > maxCount) {
			return false;
		}
		
		for(int i = n; i >= 0; --i) {
			final int p = postage-i*values[index];
			
			if(postStamp2(p, result, values, index+1, maxCount)) {
				result[index] = i;
				return true;
			}
		}
		
		return false;
	}

 

[Goldarm5]

Es funktioniert nun also doch dank einiger kleiner Änderungen. Im Prinzip lag es letztlich an den Fehlern bei Kommazahlen, nach dem umrechnen in ganzzahlige Cent-Beträge klappt es nun wunderbar.

package de.gpdlabor.aufgabe3;

import java.util.Scanner;

public class GDP3C {
	public static final int MARKE1 = 145;
	public static final int MARKE2 = 60;
	public static final int MARKE3 = 45;
	public static final int MARKE4 = 1;
	public static final int MULTIPLIKATOR = 100;
	public static final int STARTWERT = 200000000;


	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		
		double porto = 0;
		int restporto = 0;
		int maxAnzahl1 = 0;
		int maxAnzahl2 = 0;
		int maxAnzahl3 = 0;
		int anzahl1 = 0;
		int anzahl2 = 0;
		int anzahl3 = 0;
		int anzahl4 = 0; //Im Rechenvorgang verwendete Anzahl
		int anzahl1Speicher = 0;
		int anzahl2Speicher = 0;
		int anzahl3Speicher = 0;
		int anzahl4Speicher = 0; //Gespeicherte Anzahl jeder Briefmarke
		int gesamtZwischen = 0; //Gesamtzahl der Briefmarken (momentan)
		int gesamtSpeicher = STARTWERT; //Gespeicherte Gesamtzahl
		int portoalsint = 0; //Porto umgerechnet in Cent(Ganzzahl)
		System.out.print("Bitte geben sie den gewünschten Portobetrag ein, das Programm"
		+ " berechnet die kleinste Briefmarkenzusammenstellung.\r\n");
		porto = Double.parseDouble(in.nextLine());
		portoalsint = (int) (porto * MULTIPLIKATOR);
		maxAnzahl1 = (int) (portoalsint / MARKE1) + 1;
		maxAnzahl2 = (int) (portoalsint / MARKE2) + 1;
		maxAnzahl3 = (int) (portoalsint / MARKE3) + 1; //Maximal ins Porto passende Anzahl der Briefmarken
		
		while (anzahl1 < maxAnzahl1 && anzahl2 < maxAnzahl2 && anzahl3 < maxAnzahl3) //Schleife zur Berechnung, bis maxzahl erreicht ist
			{
			restporto = portoalsint - (anzahl1 * MARKE1 + anzahl2 * MARKE2 + anzahl3 * MARKE3); //restporto nach abzug verw. Briefmarken
			if (restporto > 0) //falls größer 0 sind noch 1 cent stücke übrig
			{
			anzahl4 = restporto;
			restporto = restporto - (MARKE4 * anzahl4);
			}
			if (restporto == 0) //wenn Restporto 0, dann wird Gesamtzahl berechnet
			{
			gesamtZwischen = anzahl1 + anzahl2 + anzahl3 + anzahl4;
			}
			if (gesamtZwischen < gesamtSpeicher && gesamtZwischen > 0) //falls Gesamtzahl kleiner als Speicher neue kleinste Gesamtzahl
			{
				gesamtSpeicher = gesamtZwischen;
				anzahl1Speicher = anzahl1;
				anzahl2Speicher = anzahl2;
				anzahl3Speicher = anzahl3;
				anzahl4Speicher = anzahl4;
			}
			
			if (anzahl1 < maxAnzahl1 && anzahl2 < maxAnzahl2)//systematische erhöhung wie im Zahlensystem		
			{
				anzahl3 = anzahl3 + 1;
				if (anzahl3 == maxAnzahl3)
				{
					anzahl3 = 0;
					anzahl2 = anzahl2 + 1;
					if (anzahl2 == maxAnzahl2)
					{
						anzahl2 = 0;
						anzahl1 = anzahl1 + 1;
					}
				}
				
			}
			anzahl4 = 0;
			restporto = 0;
			}
		System.out.print("Sie brauchen insgesamt: " + gesamtSpeicher + " Briefmarken, wie folgt aufgeteilt: \r\n");
		if (anzahl1Speicher > 0)
		{
			System.out.print(anzahl1Speicher + "x 1.45\r\n");
		}
		if (anzahl2Speicher > 0)
		{
			System.out.print(anzahl2Speicher + "x 0.60\r\n");
		}
		if (anzahl3Speicher > 0)
		{
			System.out.print(anzahl3Speicher + "x 0.45\r\n");
		}
		if (anzahl4Speicher > 0)
		{
			System.out.print(anzahl4Speicher + "x 0.01\r\n");
		}
		in.close();

	}

}