Rückgabe von Wechselgeld nach einem Kauf

life

Dobi schrieb:

Geht sicher auch wesentlich eleganter und wiederverwendbarer, aber damit du siehst, wie ich es meine, reichts, denk ich.

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    ...
	for ( vector <int>::const_iterator it( geldEinheiten.begin() ); it != geldEinheiten.end(); ++it )
	{
		int anzahl( 0 );
		while ( *it <= wechselgeld )
		{
			++anzahl;
			wechselgeld -= *it;
		}
		cout << anzahl << " Gegenstaende, die einen Wert von " << *it << " Cent repräsentieren." << endl;
	}
	return 0;
}

Fehlt nur noch der Korrektheitsbeweis. Wenn man z.B. auch 4€ Münzen hätte, wäre deine Strategie ja fehlerhaft (z.B. 8€ mittels 5€+2€+1€ zu wechseln wäre dann nicht optimal, sondern 4€+4€). Warum klappt die Strategie also in diesem Fall?

Dobi

life schrieb:

Warum klappt die Strategie also in diesem Fall?

Weil die nächstgrößere Einheit bei unserer Währung immer mindestens doppelt so groß ist wie die kleinere.
Hab ich deinen Test bestanden?

volkard

Dobi schrieb:

life schrieb:

Warum klappt die Strategie also in diesem Fall?

Weil die nächstgrößere Einheit bei unserer Währung immer mindestens doppelt so groß ist wie die kleinere.
Hab ich deinen Test bestanden?

Gegenbeispiel:
Die 1-Cent-Münze wurde abgeschafft.
Will 8 Cent rausgeben.
Gebe zuerst 5 und verzweifle.

Dobi

Mhh, stimmmt. Ok, dann vielleicht, weil geldEinheiten.at(n) immer größer als geldEinheiten.at(n+1)*2 ist und weil es die Basiseinheit auch als Element gibt?
Was machen wir eigentlich, wenn wir beliebige Geldeinheiten haben, von allen aber nicht beliebig viel. Dann kanns ja sein, dass das Ziel ist, dem Kunden möglichst viel Wechselgeld zurückzugeben aber nicht mehr als nötig. Hilft es dann, wenn wir uns vorstellen, dass der Kunde das Welchselgeld nicht in ein Portemonnaie tut, sondern in einen Rücksack?

life

Dobi schrieb:

Mhh, stimmmt. Ok, dann vielleicht, weil geldEinheiten.at(n) immer größer als geldEinheiten.at(n+1)*2 ist und weil es die Basiseinheit auch als Element gibt?

Gegenbeispiel:
90€ Schein
25€ Schein
1€ Münze
Will 100€ rausgeben.
Gebe zuerst 90€ und verzweifle.

Dobi

life schrieb:

Dobi schrieb:

Mhh, stimmmt. Ok, dann vielleicht, weil geldEinheiten.at(n) immer größer als geldEinheiten.at(n+1)*2 ist und weil es die Basiseinheit auch als Element gibt?

Gegenbeispiel:
90€ Schein
25€ Schein
1€ Münze
Will 100€ rausgeben.
Gebe zuerst 90€ und verzweifle.

90+1+1+1+1+1+1+1+1+1+1 ist zwar unschön, aber nicht zum Verzweifeln.

life

Dobi schrieb:

life schrieb:

Dobi schrieb:

Mhh, stimmmt. Ok, dann vielleicht, weil geldEinheiten.at(n) immer größer als geldEinheiten.at(n+1)*2 ist und weil es die Basiseinheit auch als Element gibt?

Gegenbeispiel:
90€ Schein
25€ Schein
1€ Münze
Will 100€ rausgeben.
Gebe zuerst 90€ und verzweifle.

90+1+1+1+1+1+1+1+1+1+1 ist zwar unschön, aber nicht zum Verzweifeln.

Jedenfalls nicht optimal.

Dobi

Ich hab doch schon eingesehen, dass man das so aufblähen kann, dass es ne O(c^n)-Rucksack-Geschichte wird. Und nein, DAS werde ich nicht beweisen.

life

Im Allgemeinen ist das Problem NP-Vollständig. In dem konkreten Fall funktioniert die Greedy-Strategie allerdings tatsächlich. Und genau letzteres sollst du beweisen ;).

Dobi

Heute ist Informatik für mich dann halt Natur- und nicht Strukturwissenschaft. Also darfst du versuchen, meine Theorie zu falsifizieren. Die Möglichkeit dazu bietet sie ja, so.
OK, ich denk mal (googleunterstützt) nach. Jetzt interessierts mich.

Ich denke, wenn man die Optimas von allen Geldbeträgen betrachtet, wird es irgendwann eine Regelmässigkeit geben, so dass Opt(n) = g + Opt(n - g) aller n>c, wobei g=grösster Münzwert.

Die Tabelle bis dahin lässt sich in konstanter Zeit generieren und auch der Rest ist eine simple Rechnung. Folglich wäre das Problem in O(1) lösbar, von NP-complete keine Spur. Das wäre im Übrigen auch eine Vorgehensweise, mit der sich die Greedy-Strategie noch optimieren liesse: n = n mod g. Auch dann ist die Laufzeitkomplexität O(1).

Den Beweis überlasse ich dir

[quote="wikisid"so dass Opt(n) = g + Opt(n - g) aller n>c, wobei g=grösster Münzwert.[/quote]Ups, soll heissen g ist ein Vielfaches des grössten Münzwertes, es muss nicht genau ihm entsprechen (siehe Beispiel mit Münzsatz (90, 24, 1)).

life

Beim verallgemeinerten NP-vollständigen Problem sind die Münzbeträge, die einem zum Wechseln zur Verfügung stehen, auch eine Eingabe des Algorithmus.

Der Algo geht auch mit Eingabe der Münzbeträge. Und die Periode tritt IMHO nach kgV(m₁, m₂, m₃, ..., m_n) Einheiten auf, also läuft er in O(n·m_n).

NP-Complete wird er IMHO, wenn nur eine begrenzte Anzahl Münzen zur Verfügung steht.

Hmm, ich sollte meine Beiträge genauer lesen... m_nⁿ ist natürlich exponentiell.

Clonex

Ich möchte mich vielmals für die Hilfe hier bedanken.

Hier mal meine Lösung. Ich weiß wenn Ihr Profis das jetzt seht wird euch bestimmt schlecht aber wie gesagt ich lerne noch....

#include <iostream>
using namespace std;

int main() {

	int kaufbetrag, gezahlt;
	cout << "Bitte geben Sie den den Kaufbetrag in Cent ein: " << endl;
	cin >> kaufbetrag;
	cout << "Bitte geben Sie den Gezahlten Betrag in Cent ein: " << endl;
	cin >> gezahlt;

	int wechselgeld = gezahlt - kaufbetrag;
	if (kaufbetrag==gezahlt) {
		cout << " Passend bezahlt!" << endl;
	}
	if (kaufbetrag>gezahlt) {
		cout << "Zu wenig bezahlt, restart!" << endl;
	}
	int change [] = { 50000, 20000, 10000, 5000, 2000, 1000, 500, 200, 100, 50,
			20, 10, 5, 2, 1 };
	int j=0;
	int calc;

	while (j<=14) {
		calc= wechselgeld/change[j];
		if (calc>0) {
			cout << "Sie bekommen " << calc <<" mal " << change[j]
					<< " cent zurück!" << endl;
			wechselgeld=wechselgeld-calc*change[j];
		}
		j++;
	}
	return 0;
}

Skym0sh0

nein sieht doch ganz gut aus am anfang...

volkard

Die while-Schleife wäre lieber eine for-Schleife.
Die Variable calc wäre lieber noch lokaler.
Sonst perfekt, würde ich sagen.

wechselgeld noch lokaler
"Bitte geben Sie den Gezahlten Betrag in Cent ein: " ← "gezahlten" klein, ev. Punkt anstatt Doppelpunkt
else if bei zweitem if
14 nicht hardcoden sondern als const int change_size = sizeof(change)/sizeof(*change); definieren
zeile 29: operator -= nehmen

Versteh das nicht falsch; deines ist wirklich nahezu perfekt, gerade für einen Anfänger. Aber bevor Mods so etwas als perfekt deklarieren dürfen, muss man es doch noch etwas perfektionieren.

mrperfekt schrieb:

wechselgeld noch lokaler
"Bitte geben Sie den Gezahlten Betrag in Cent ein: " ← "gezahlten" klein, ev. Punkt anstatt Doppelpunkt
else if bei zweitem if
14 nicht hardcoden sondern als const int change_size = sizeof(change)/sizeof(*change); definieren
zeile 29: operator -= nehmen

Versteh das nicht falsch; deines ist wirklich nahezu perfekt, gerade für einen Anfänger. Aber bevor Mods so etwas als perfekt deklarieren dürfen, muss man es doch noch etwas perfektionieren.

Der Text ist nun ja mal ziemlich wayne.
Er braucht kein else if bei dem 2. if. Die Bedingungen schliessen sich gegenseitig aus. Wenn der Betrag == ist, dann procct die 1. if-verzweigung, wenn der Betrag > ist dann procct die 2.
Wie sollt er den operator -= nehmen ? Das ist ja wohl Geschmackssache, seine Variante sogar irgendwie lesbarer.
Was ich für mehr erwähnenswert halten würde ist :

if (kaufbetrag>gezahlt) {
        cout << "Zu wenig bezahlt, restart!" << endl;
    }

Du behauptest zwar etwas von einem restart, dieser geschieht aber nie. Dein Programm würde in dem Fall einfach weiterlaufen und zu irgendeinem Crap-Ergebnis führen. Pack die Eingaben in eine while-schleife die erst endet, wenn alles richtig eingegeben wurde.
Und : Mach die Überprüfungen doch bevor du Wechselgeld berechnest.