Ich habe Probleme beim Versuch, das Knapsack-Problem mithilfe von Backtraking zu lösen.

Für die folgenden Werte gibt die Knapsack-Funktion beispielsweise 14 als Lösung zurück, das richtige Ergebnis sollte jedoch 7 sein.

int n = 3, weights[] = {2, 3, 1}, values[] = {6, 15, 7};

int solution = 0, max = 2;


void Knapsack (int i, int max, int value, int *solution)
{
  int k;

  for (k = i; k < n; k++) {
    if (weights[k] <= max) {
      Knapsack (k, max - weights[k], value + values[k], solution);

      if (value+ values[k] > *solution) 
         *solution= value + values[k];
    }
  }
}

Was ist das Problem hier?