Kombinationen. Permutation streichen?

Hallo zusammen.

Ich möchte ein programm schreiben, mit welchem ich berechnen kann, mit welcher kombinationen an Münzen und Notenscheinen ich eine gegebene Zahl "darstellen" kann.

Also 5 cent kann ich ja

5x 1 Cent darstellen
22 Cent + 1 Cent
51 Cent etc.

Nun habe ich mir mal überlegt, wenn ich da eine schleife bauen würde, dann müsste ich ja pro existierende Münzen / Noten die teiler berechnen (wie ist mir da auch noch ein Rätsel, wohl mit einem Array o.ä.) und vorallem kommen da ja dann gewisse kombinationen 2x vor.

Meine Frage daher,

1. wie kann ich die kombinationen speichern (können ja ganz schön viele werden, bzw. weiss ja nicht wie lange die überhaupt werden können - bei 50 Euro ist das ja kaum mehr überblick bar, wenn man jeden cent zulässt

2. mit welchem verfahren kann ich permutationen streichen?

Habe schon an rekursion gedacht und damit an tiefensuche, aber das macht alles noch viel komplizierter!

Gibt es da einen "einfacheren Weg?

Lg Hugo

Michael E.

Mit Permutationen hat das nichts zu tun.

Du könntest es folgendermaßen versuchen: Du fängst mit der größten Währungseinheit an (z. B. 50 Euro) und schreibst eine Schleife, die damit anfängt, 0 von dieser Einheit zu nehmen, bis du dabei angekommen bist, die maximale Anzahl dieser Einheit zu nehmen, die in den Betrag reinpasst. Mit dem Betrag, der dann noch übrig ist, rufst du die Funktion rekursiv auf.

Ja, hat was...

Das Problem ist einfach, dass eine rekrusion bei 50 euro eine endlos lange laufzeit hat, denn es gibt ja für die kombinationen von 1 cent zu 50 euro hin weiss ich nicht wieviel möglichkeiten.

Zudem ist mir nicht ganz klar, wie diese rekrusion aussehen sollte Michael!

was du lösen willst, nennt sich Rucksackproblem. http://de.wikipedia.org/wiki/Rucksackproblem

Badestrand

namenlos schrieb:

was du lösen willst, nennt sich Rucksackproblem. http://de.wikipedia.org/wiki/Rucksackproblem

Im Rucksackproblem wird doch eine optimale Lösung gesucht, Hugo B/Wulf wollte aber eine Aufzählung aller Möglichkeiten. Soweit, wie ich das Rucksackproblem verstehe, kann man's hierauf nicht anwenden (?).

Wulf schrieb:

Das Problem ist einfach, dass eine rekrusion bei 50 euro eine endlos lange laufzeit hat, denn es gibt ja für die kombinationen von 1 cent zu 50 euro hin weiss ich nicht wieviel möglichkeiten.

Wenn es zu viele Lösungen sind, kannst du sie ja auch nicht alle speichern. Willst du die Anzahl der Lösungen haben, die Lösungen auflisten oder musst du wirklich alle speichern?

der algorithmus zum rucksackproblem kann mehrere probleme lösen. eben auch dieses hier. die kapazität des rucksacks ist der wert in cent, den man aufteilen will. die existierenden münzen entsprechen den dingen, die man in den rucksack geben kann. dass man in dem fall genau auf den wert kommen will, ist nur eine variante.

Badestrand

Wäre dann die Nutzenfunktion die Anzahl der jeweiligen Einheit oder wie?

mit dem algorithmus zum rucksackproblem kann ich alle kombinationen berechnen. der rucksackalgorithmus verwirft nicht optimale lösungen. wenn ich aber den nutzen jedes elements auf 1 setzen (sprich, ich ignoriere den nutzen einfach), sind alle kombinationen optimal, die im gesamten dann genau die größe des rucksackes ergeben. so seh ich das halt.

EDIT: sorry, nicht alle münzen auf 1, sondern auf ihren wert

Nei, es ginge drum, das ich eine möglichkeit nach der anderen ausgebe und nichts davon speichere, aber es happert wohl eher an der rekursion und dann v.a. im umsetzen in c++

der versuch einer lösung:

#include <iostream>
#include <iomanip>

typedef int coins[6];
coins values = { 1, 2, 5, 10, 20, 50 };
int sum(coins& c) {
  int sum = 0;
  for(unsigned int i = 0; i < sizeof(coins) / sizeof(int); ++i) { sum += c[i] * values[i]; }
  return sum;
}
void print(coins& c) {
  for(unsigned int i = 0; i < sizeof(coins) / sizeof(int); ++i) { std::cout << std::setw(2) << c[i] << ' '; }
  std::cout << "= " << sum(c) << std::endl;
  return;
}
void copy(coins& a, coins& b) {
  for(unsigned int i = 0; i < sizeof(coins) / sizeof(int); ++i) { a[i] = b[i]; }
  return;
}

coins transformations[] = {
  /* 2*/ { 2, 0, 0, 0, 0, 0 },
  /* 5*/ { 1, 2, 0, 0, 0, 0 },
  /*10*/ { 0, 0, 2, 0, 0, 0 },
  /*20*/ { 0, 0, 0, 2, 0, 0 },
  /*50*/ { 0, 0, 0, 1, 2, 0 }
};

bool check(coins& c, int n) {
  for(unsigned int i = 0; i < sizeof(coins) / sizeof(int); ++i) {
    if(c[i] < transformations[n][i]) { return false; }
  }
  return true;
}

bool transform(coins& c, int n) {
  if(!check(c, n)) { return false; }
  for(unsigned int i = 0; i < sizeof(coins) / sizeof(int); ++i) { c[i] -= transformations[n][i]; }
  c[n + 1] += 1;
  return true;
}

void combinations(coins& c, int n = 0) {
  while(transform(c, n)) {
    print(c);
    coins tmp;
    copy(tmp, c);
    if(check(c, n + 1)) { combinations(tmp, n + 1); }
  }
  return;
}

int main(void) {
  coins c = { 50, 0, 0, 0, 0 };
  print(c);
  combinations(c);
  return 0;
}

es ist nur ein ansatz. ich muss zugeben, dass ich nicht nachgeprüft hab, ob wirklich alle möglichen kombinationen enthalten sind.

Badestrand

Es sind ja noch eine Ecke mehr Werte, du musst ja alles von 1 Cent bis 50 Euro einbauen, also { 1, 2, 5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000 } . Ich könnte wetten, dass das zu viele Kombinationen ergibt, als dass sich das in einer vernünftigen Zeitspanne ablaufen ließen.. Ich weiß es aber nicht, mal schauen

hm jo. wie gesagt, es ist ein ansatz. die weiteren scheine hinzuzufügen, ist jetzt nicht so schwer. man braucht sie ja nur dazuzuschreiben.

EDIT: wobei das aber eh genau gar nichts bringt, da er schon allein bei der aufgabe, 50000 cent (sprich 500 euro) zu kombinieren, ewig rechnet. das sind auch sicher millionen an möglichkeiten. wenn nit milliarden.
bei 5 euro rechnet er bei mir 37 sekunden lang und hat 6295435 kombinationen.