Kombinationen. Permutation streichen?

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.