Münzwechsler

Hi,

ich habe folgendes Problem. Ich soll ein Programm schreiben, was für einen gegebene Betrag (Bsp.: n=5)
alle Möglichkeiten des Münzwechsels ausgibt. Also zum Beispiel 5*1 und 2*2+1 (in diesem Fall gibt es 2 Münzsorten). Ich denke diese Aufgabe ist rekursiv zu lösen, komme jedoch nicht weiter. Hat jemand von euch so etwas vielleicht schon mal gemacht und kann mir helfen????

life

naja.. z.B. so (rohentwurf):

void getCoins(int* muenzen,int* usedMuenzen, int length, int value, int start ) 
{
	int* usedMuenzenLocal = new int[length];
	//kopiere die benutzen münzen..
	for(int i = 0; i < length; ++i)
		usedMuenzenLocal[i] = usedMuenzen[i];

    for(int i = start; i < length;) 
	{		
		if(value >= muenzen[i])
		{
			//man könnte hier aber auch muenze[i+1] stattdessen nehmen...
			//die möglichkeit wollen wir natürlich nicht unterschlagen -->
			getCoins(muenzen,usedMuenzenLocal, length, value,i+1);

			//jetzt jedenfalls eine muenze nehmen
			++usedMuenzenLocal[i];
			//muenzwert noch vom übrigen wert abziehn
			value -= muenzen[i];
		}
		else
		{
			//mit der muenze kann man nix mehr anfangen...
			++i;
		}
	}
	if(value == 0)
	{
		cout << "Moegliche Muenzausgabe: ";
		for(int i = 0; i < length; ++i)
		{
			cout << usedMuenzenLocal[i] << "x " << muenzen[i] << " ";
		}
		cout << endl;
	}
	delete[] usedMuenzenLocal;
}

int main() 
{ 
	int muenzen[] = {200,100,50,20,10,5,2,1}; //oder so ;)
	int length = sizeof(muenzen)/sizeof(int);
	int* usedMuenzen = new int[length];
	for(int i = 0; i < length; ++i) 
	{
		usedMuenzen[i] = 0;
	}
    //value ist der wert, der in muenzen ausgegeben werden soll.. (in cent)
	int value = 30;
	getCoins(muenzen,usedMuenzen,length,value,0);
	delete[] usedMuenzen;

}

das geht aber bestimmt noch effektiver

Fertige Lösungen sind Scheiße.