Programmieraufgabe "Münzenproblem"

[ands]

Hallo zusammen

Als Übung sollen wir auf C++ ein Programm schreiben welches testet, ob ein Betrag B durch bestimmte Münzen passend bezahlt werden kann.
Der Betrag B soll eingegeben werden. Genauso soll man eingeben können, wie viele verschiedene Münzen (Anzahl n) es gibt und deren Werte w1 bis wn.

Das Program habe ich zuerst für eine fixe Anzahl Münzen und fixe Münzenwerte geschrieben. Dann ist das Problem einfach lösbar. Ich habe dazu eine rekursive Funktion geschrieben in der Form:

if(betrag == 0)
{
return true;
}
else if(betrag < 0)
{
return false,
}
else
{
return funktion(betrag - w1) || funktion(betrag - w2);
}

Dies klappt ohne Probleme, aber ich verstehe nicht ganz wie ich es lösen kann, dass ich die Anzahl Münzen und die Münzenwerte nicht fix setzen muss.

Wäre es vielleicht sinnvoll die Münzwerte w in einem array zu speichern?
Habt ihr mir dazu einen Tipp / Lösungsansatz?

[SG1]

Genau. Und die letzte Zeile der Funktion ersetzt Du dann mit einer Schleife, in der Du alle Array-Elemente durchgehst. Jetzt musst Du Dir nur noch überlegen, wie Du dann das || nachbaust.

[Die erinnerung]

Also. Du musst dein programm umstrukturieren.

Erstes muss der Benutzer eingeben, wie viele verschiedene Münzen er hat.

Dann erzeugst du einen Vector von dieser Größe.

Dann lässt du das ganze in einer Schleife einlesen (die Münzwerte)

Dann sortierst du den Vector (das größte Element an den Anfang)

Dann gibt der Benutzer den Betrag ein.

Dann gehst du den Vector durch und schaust, ob der Betrag größergleich dem Münzwert ist. Wenn ja, den Münzwert abziehen. wenn nein, zum nächst kleineren Münze gehen.

Wenn du am Ende einen Restbetrag hast, dann gehst halt nicht, wenn der Restbetrag null ist, dann gehts.

P.S.: Editiert.....

[Belli]

Die erinnerung schrieb:

[...]

Das funktioniert so nicht. Angenommen ich habe einen Betrag von 8 und Münzen mit dem Wert 5 und 2.
Nach der von Dir skizzierten Methode würde ich zunächst 5 von 8 subtrahieren und dann feststellen, dass ich den verbleibenden Betrag von 3 nicht mehr mit meinem Münzvorrat darstellen kann.

[Die erinnerung]

Die erinnerung schrieb:

Dann gehst du den Vector durch und schaust, ob der Betrag größergleich dem Münzwert ist. Wenn ja, den Münzwert abziehen. wenn nein, zum nächst kleineren Münze gehen.

Gegenbeweis:

Betrag: 8

Münzen (sortiert): 5; 2

8 >= 5 ?
Ja!
8 - 5 = 3
3 >= 5 ?
Nein! Nächste Münze.
3 >= 2 ?
Ja!
3 - 2 = 1
1 >= 2 ?
Nein! Nächste Münze nicht vorhanden! Letzter Schritt

1 == 0?
Nein!
=> Betrag nicht auszahlbar! :p

[Belli]

Jo eben, das ist Dein Ergebnis, aber der Betrag ist doch auszahlbar, wenn ich ihn in vier 2er - Münzen auszahle.

[icarus2]

Belli schrieb:

Jo eben, das ist Dein Ergebnis, aber der Betrag ist doch auszahlbar, wenn ich ihn in vier 2er - Münzen auszahle.

@Die erinnerung
Dein Greedy-Algorithmus - so wie du ihn beschrieben hast - funktioniert nicht. Ein Gegebeispiel hat ja Belli bereits gebracht.

[Die erinnerung]

ok. Stimmt! Denkfehler.

Wenn du deinen Nimmst, versuche die ganzen || in einer Schleife zu lösen.

bool flag = false;

for(int i = 0; i < muenzen.size(); i++)
{
    flag ||= funktion(betrag -  muenzen[i]);
}

return flag;

Die Rekursion könnte dann aber ganz schnell überhand nehmen...

Aber so funktionierts (relativ) sicher.

[icarus2]

Die Rekursionsgleichung kann man folgendermassen schreiben:
Sei B der Betrag, der man erreichen moechte und $M = \{m\_1, m\_2, \ldots, m_n\}$ die Menge der Muenzen. Erreichbar(B) entscheidet, ob man B mit M erreichen kann oder nicht.

$Erreichbar(Wert) = \begin{cases} True, \quad Wert = 0 \\ False, \quad Wert < 0 \\ \forall m \in M: Erreichbar(Wert-m), \quad sonst \end{cases}$

Damit man nicht so viele Rekursionsaufrufe hat verwendent man Memoization oder noch besser Dynamische Programmierung.

In diesem Fall braucht man fuer die Dynamische Programmierung nicht einmal eine Tablle. Es reicht ein Array der Laenge B.

[Belli]

Ich glaube, so gehts:

#include <vector>

using namespace std;

vector<int> m; //Vektor mit den zur Verfügung stehenden Münzwerten

bool erreichbar(int b)
{
	if(b == 0)
		return true;
	if(b < 0)
		return false;

	for(int i = 0; i < m.size(); ++i)
	{
		if(erreichbar(b - m[i]))
			return true;
	}

	return false;
}

[icarus2]

@Belli
Ja, diese Implementierung scheint korrekt zu sein. Allerdings ist sie sehr ineffizient, wegen den vielen Rekursionsaufrufen. Wie gesagt kann hier Memoization oder Dynamische Programmierung verwendet werden.

Ich moechte die Loesung dafuer hier allerdings nicht posten, da ich dem Thread Ersteller nicht den Spass nehmen will.

[Belli]

Tja, diese Begriffe, die Du da in den Raum wirfst, sagen mir nichts. Deshalb bin ich nicht in der Lage, eine andere Lösung zu entwerfen. Ich hab hier mal ein vollständiges Beispiel, das am Ende die benötigten Stücke ausgibt, wenn es denn eine Lösung gibt:

#include <iostream>
#include <vector>
#include <sstream>

using namespace std;

vector<int> m;
vector<int> r;

bool erreichbar(int b)
{
	if(b == 0)
		return true;
	if(b < 0)
		return false;

	for(int i = 0; i < m.size(); ++i)
	{
		if(erreichbar(b - m[i]))
		{
			r.push_back(m[i]);
			return true;
		}
	}

	return false;
}

int main(int argc, char **argv)
{
	stringstream ss;
	ss << argv[1];
	int b;
	ss >> b;

	m.push_back(3);
	m.push_back(5);

	erreichbar(b);	

	if(!r.size())
		cout << "geht nicht\n";

	for(int i = 0; i < r.size(); ++i)
		cout << r[i] << ' ';

}

[icarus2]

Belli schrieb:

Tja, diese Begriffe, die Du da in den Raum wirfst, sagen mir nichts.

Falls du dich fuer algorithmische Methoden interessierst soltest du dir einmal Dynamische Programmierung anschauen. Ist eine interessante Methode um schwierige Probleme effizient (in Pseudopolynomieller Zeit) zu loesen.

[ands]

Habe mir mal das Konzept der Memoization angeschaut, bin mir aber nicht sicher, ob ich das richtig verstehe...
Das Ziel der Memoization besteht ja darin, dass Zwischenergebnisse nicht mehrmals neu berechnet werden, sondern gespeichert und wiederverwendet werden. Habt ihr einen Tipp, wie man das auf das Münzenbeispiel anwendet?
Meine Idee:
Einen Vektor "vector<int> memory" welcher alle Zwischenbeträge die berechnet werden speichert. Das heisst ein neuer Zwischenwert soll nur berechnet werden, wenn er nicht schon im Vektor steht. Ich habe nun aber zwei Fragen/Probleme...an welchen Positionen muss ich diese Zwischenbeträge jeweils speichern bzw. wie muss ich sie speichern damit ich einfach prüfen kann, ob ein Betrag bereits vorhanden ist oder nicht? Und zweitens ist mir nicht ganz klar, wie ich die Schritte einbauen kann für Betrag == 0 oder Betrag <0?

[icarus2]

Eine rekursive Loesung hat ja Belli oben bereits gepostet. In der Loesung dort gibt es einen einzigen rekursiven Aufruf in Zeile 20, naemlich

erreichbar(b - m[i])

Das Ziel ist es nun, diesen Aufruf nicht jedes mal neu berechnen zu muessen. Das heisst du erzeugst ein Array einer bestimmten Laenge, um berechntete Teile der Rekursion zu speichern. Wenn du dann zum rekrusiven Aufruf kommst, hast du folgende zwei Moeglichkeiten:
1. Du hast erreichbar(b - m[i]) bereits berechnet. Dann verwende den Wert aus dem Array und rufe erreichbar(b - m[i]) nicht rekursiv auf.
2. Du hast erreichbar(b - m[i]) noch nicht berechnet. Dann rufe erreichbar(b - m[i] rekursiv auf und speichere dann die Loesung im Array.

Um herauszufinden, ob du erreichbar(b - m[i]) bereits berechnet hast oder nicht kannst du ein zweites Array der gleichen Groesse anlegen und dann mit true oder false speichern, ob du den Wert bereits berechnet hast.

Was du dich noch fragen musst ist, wie gross du das Array waehlen musst. Aber das kannst du sicher selber rausfinden.

Ich hoffe, die Beschreibung hilft dir etwas.

[Die erinnerung]

Da würde ich eher einen Vector nehmen.

[icarus2]

Die erinnerung schrieb:

Da würde ich eher einen Vector nehmen.

Wenn man Array sagt duerfte klar sein, dass man dann in C++ einen std::vector oder ein std::array verwendet

[Die erinnerung]

Soooooooooooooo sicher wäre ich mir da nicht...
(Ich hätte, hätte ich nicht nachgedacht, z.B bool benutzt[123]; gemacht. Zum Beispiel...)

[Belli]

Deswegen ist Nachdenken ja auch so wichtig. Ich würde auf den ersten Blick eine map wählen.

[ands]

Habe es mit Vektoren gemacht... mit den Tipps von icarus2 (danke!) ist's dann ziemlich einfach und klappt gut