Münzen berechnen.

[E.]

Hallo zusammen,
Ich habe folgendes Problem:
Ich suche einen Algorithmus, der mir die Anzahl von Münzen für einen bestimmten Betrag berechnet. Ich habe dabei 2 Münzenwertigkeiten in der Kasse, mit denen ich diesen Betrag so genau als möglich rausgeben möchte.

Beispiel:

In der Kasse habe ich 0,5 Euro und 0,2 Euro - Münzen.
Ich möchte den Betrag von 1,10 Euro rausgeben.

Jetzt soll der Algoritmus mir berechnen, dass ich eine 0,5 Euro und 3 0,2 Euro Münzen nehmen muss.

Ich habe mir das mit dem Greedy-Algorithmus angesehen, und habe den Auszahlbetrag durch 0,5 Euro dividiert und die Anzahl der Münzen reingestopft, und das gleiche für die 0,2 Euro.
Allerdings dauerte die Berechnung von höheren Beträgen eine Ewigkeit (5 Sekunden und mehr....)

Ich bitte euch um Hilfe bzw. Anregungen, Tipps für mein Problem !

Danke

[Jester]

Das Problem ist, dass sich Greedy nicht bei allen Münzwerten anwenden lässt. Im Prinzip hast Du im Allgemeinen so eine Art Rucksackproblem und das ist leider recht schwer. Allerdings gibt's ein dynamisches Programm mit dem sich das ganze für viele Instanzen noch gut lösen lässt: siehe http://de.wikipedia.org/wiki/Rucksackproblem , da gibt's auch das dynamische Programm.

[E.]

Ich habe das mit dem Rucksackproblem bereits probiert, allerdings ist das total langsam...... ich hoffe, dass mir jemand helfen kann, das volle kanne zu beschleunigen, ich bin leider kein Mathe-Genius, daher bitte ich euch mir zu helfen....

///////////////////////////////////////////////////////////////////////////////
#include <conio.h>
#include <string>
#include <vector>
#include <iostream>
#include <sstream>
#include <windows.h>

using namespace std;
///////////////////////////////////////////////////////////////////////////////
// 
class KnapsackObject
{
public:
	///////////////////////////////////////////////////////////////////////////////
	// initializes an new instance of the KnapsackObject-class
	KnapsackObject()
	{

	}
	///////////////////////////////////////////////////////////////////////////////
	// initializes an new instance of the KnapsackObject-class
	KnapsackObject(const std::string& coinName,const int& hopperCoinValue)
		: m_coinName(coinName), m_hopperCoinValue(hopperCoinValue)
	{

	}
	///////////////////////////////////////////////////////////////////////////////
	// returns the coins name
	const std::string& GetCoinName() const
	{
		return m_coinName;
	}
	///////////////////////////////////////////////////////////////////////////////
	// returns the coin value
	const int& GetCoinValue() const
	{
		return m_hopperCoinValue;
	}
private:
	std::string m_coinName;
	int m_hopperCoinValue;
};

///////////////////////////////////////////////////////////////////////////////
//
class KnapsackSolution
{
public:
	///////////////////////////////////////////////////////////////////////////////
	// sets the total cost
	void SetTotalCost(const int& totalCost)
	{
		m_totalCost=totalCost;
	}
	///////////////////////////////////////////////////////////////////////////////
	// returns the total cost
	const int& GetTotalCost() const
	{
		return m_totalCost;
	}
	///////////////////////////////////////////////////////////////////////////////
	// sets the selectd objects
	void SetSelectedObjects(std::vector<KnapsackObject> knapsackObjects)
	{
		m_selectedObjects=knapsackObjects;
	}
	///////////////////////////////////////////////////////////////////////////////
	// returns the selected objects
	std::vector<KnapsackObject> GetSelectedObjects() 
	{
		return m_selectedObjects;
	}
private:
	std::vector<KnapsackObject> m_selectedObjects;
	int m_totalCost;
};

///////////////////////////////////////////////////////////////////////////////
//
class KnapsackSolver
{
public:
	KnapsackSolver()
		: m_maxCost(0),m_knapsackSize(0),m_totalCost(0) 
	{

	}
	///////////////////////////////////////////////////////////////////////////////
	// retuns the size
	const int GetSize() const
	{
		return m_knapsackSize;
	}
	///////////////////////////////////////////////////////////////////////////////
	// sets the size
	void SetSize(const int& size)
	{
		m_knapsackSize = size;
	}
	///////////////////////////////////////////////////////////////////////////////
	// enumerate
	void Enumerate(int z,int vcost,int vweight,std::vector<bool>& v)
	{
		if(vweight <= GetSize())
		{
			if(vcost > m_maxCost)
			{
				m_maxCost = vcost;
				for(int i=0;i<v.size();++i)
				{
					m_bestFoundSolution[i] = v[i];
				}
			}
			int size = m_knapSackObjects.size();
			for(int i=z+1;i<size;++i)
			{
				v[i]=true;
				Enumerate(i,vcost+m_knapSackObjects[i].GetCoinValue(),vweight+m_knapSackObjects[i].GetCoinValue(),v);
				v[i]=false;
			}
		}
	}
	///////////////////////////////////////////////////////////////////////////////
	// returns the knapsack solution
	KnapsackSolution Solve()
	{
		m_totalCost = 0;
		m_bestFoundSolution.clear();
		m_bestFoundSolution.resize(m_knapSackObjects.size());
		std::vector<bool> v;
		v.resize(m_knapSackObjects.size());
		Enumerate(-1,0,0,v);
		KnapsackSolution knapsackSolution;
		knapsackSolution.SetTotalCost(m_maxCost);
		std::vector<KnapsackObject> al;
		for(int i=0;i<m_knapSackObjects.size();++i)
		{
			if(m_bestFoundSolution[i])
			{
				al.push_back(m_knapSackObjects[i]);
			}
		}
		std::vector<KnapsackObject> akobj;
		akobj.resize(al.size());
		for(int i=0;i<al.size();++i)
		{
			akobj[i] = al[i];
		}
		knapsackSolution.SetSelectedObjects(akobj);
		return knapsackSolution;
	}
	///////////////////////////////////////////////////////////////////////////////
	// sets the objects
	void SetKnapStackObjects(const std::vector<KnapsackObject>& knapStackObjects)
	{
		m_knapSackObjects=knapStackObjects;
	}

private:
	std::vector<KnapsackObject> m_knapSackObjects;
	int m_knapsackSize;
	int m_totalCost;
	int m_maxCost;
	std::vector<bool> m_bestFoundSolution;
};

void main(void) 
{
	int münzen[] = { 5, 20 };
	int anzahlMünzen[] = {0,0};
	DWORD averageTime=0;
	for(int betrag = 1;betrag < 100;++betrag)
	{
		KnapsackSolver k;
		k.SetSize(betrag);

		for(int j=0;j<sizeof(münzen)/sizeof(int);++j)
		{
			anzahlMünzen[j] = betrag / münzen[j];

		}

		std::vector<KnapsackObject> objs;
		for(int j=0;j<sizeof(münzen)/sizeof(int);++j)
		{
			for(int i=0;i<anzahlMünzen[j];++i)
			{
				if(anzahlMünzen[j])
				{
					std::stringstream ss;
					std::string str;
					ss << münzen[j];
					ss >> str;
					str = "Muenze "+str;
					objs.push_back(KnapsackObject(str,münzen[j]))	;
				}
			}
		}
		k.SetKnapStackObjects(objs);
		DWORD time = GetTickCount();
		KnapsackSolution r = k.Solve();
		time = GetTickCount()-time;

		if(time > averageTime)
		{
			averageTime=time;
		}
		std::vector<KnapsackObject> objects = r.GetSelectedObjects();
		std::vector<KnapsackObject>::iterator i = objects.begin();
		cout << "Betrag: " << betrag << " Zeit: " << time << " Maximalzeit: " << averageTime << endl;
		cout << "=================================================================" << endl;
		while(i != objects.end())
		{
			cout << (*i).GetCoinName() << " " << (*i).GetCoinValue() << endl;
			++i;
		}
	}
	getch();
}

[Jester]

E. schrieb:

Ich habe das mit dem Rucksackproblem bereits probiert, allerdings ist das total langsam...... ich hoffe, dass mir jemand helfen kann, das volle kanne zu beschleunigen, ich bin leider kein Mathe-Genius, daher bitte ich euch mir zu helfen....

Der Code ist leicht unübersichtlich, aber soweit ich das erkennen kann hast Du eine Brute-Force Lösung für Knapsack implementiert. Die ist natürlich sehr langsam. Und wenn nicht gerade P=NP gilt, dann gibt es auch keine effiziente Lösung für das Problem.

Ich denke aber, dass für Deine Instanzen das dynamische Programm noch ganz gut funktionieren sollte. Also nochmal die Empfehlung: probier's doch mal damit.

[E.]

Danke für deine rasche Antwort. Ich werde mir das ansehen. Vielen Dank erstmal.