B
Typ222 schrieb:
Hat da vlt wer ne Idee mit der Rekursion blick da im Moment nicht ganz durch...
Aus deiner Erklärung geht nicht ganz hervor, was für dich alle Kombinationen sind. Du sagst, dass der Maximalwert nicht erreicht werden muss, so dass z.B. 5, 4 gültig ist, obwohl die Summe nur 9 statt 1 ist. OK, also alle Kombinationen, deren Summe 11 nicht übersteigt. Aber warum ist dann 5 nicht in deiner Aufzählung dabei? Ich vermute, du suchst alle maximalen Kombinationen, deren Summe kleiner gleich einem bestimmten Maximalwert ist.
Ich hab die Idee mit der Rekursion hier mal ausprogrammiert:
void print_combinations_max(vector<int> const& values, int start,
vector<int>& work, int max_sum) {
bool is_maximal = true;
for (int i = start, n = values.size(); i < n; ++i) {
int x = values[i];
if (x <= max_sum) {
is_maximal = false;
work.push_back(x);
print_combinations_max(values, start, work, max_sum - x);
work.pop_back();
}
}
if (is_maximal) {
for (int i = 0, n = work.size(); i < n; ++i)
cout << work[i] << " ";
cout << '\n';
}
}
Aufruf:
int valuesArray[] = {4, 3, 5};
const int nValues = sizeof(valuesArray) / sizeof(valuesArray[0]);
vector<int> values(valuesArray, valuesArray + nValues);
vector<int> work;
print_combinations_max(values, 0, work, 11);
Ausgabe:
4 4 3
4 3 4
4 3 3
4 5
3 4 4
3 4 3
3 3 4
3 3 3
3 3 5
3 5 3
5 4
5 3 3
5 5
Zur Erkärung:
Rekursion braucht immer einen Basisfall und eine Regel, wie ein komplizierter Fall auf einen einfacheren Fall reduziert werden kann, so dass irgendwann der Basisfall erreicht wird. In diesem Fall lässt sich die Aufgabe, alle Kombinationen aus einer Menge {a1, a2, ..., an} bis zu einer Maximalsumme M zu finden folgendermaßen auf kleinere Aufgaben zurückführen: Für a1 bis an bildet man jeweils alle Kombinationen bis zu einer nicht-negativen Maximalsumme von M - ai und hängt ai davor. Der Basisfall ergibt sich automatisch dadurch, dass das nicht möglich ist, wenn M - ai irgendwann negativ wird.
