Неожиданный результат рекурсивной функции задачи Knapsack

Мне нужно написать простую программу для решения задачи о рюкзаке. Я написал этот код на данный момент, и я думаю, что это все, что мне нужно, но каждый раз, когда я его выполняю, я получаю разные результаты. Все, что я могу думать, это то, что есть проблема с освобождением памяти, но я не знаю, как ее решить. Есть идеи?

P.S. Может быть, это глупый вопрос, но я никогда не работал в C.

#include <stdio.h>

int max(int a, int b){
  if (a > b) {
    return a;
  } else {
    return b;
  }
}

int knapsack(int prices[], int weight[], int n, int max_weight){
  if (n < 0)
    return 0;
  if (weight[n] > max_weight)
    return knapsack(prices, weight, n-1, max_weight);
  else
    return max(knapsack(prices, weight, n-1, max_weight), (knapsack(prices, weight, n-1, max_weight - weight[n]) + prices[n]));
}

int main(int argc, char const *argv[]) {
  int i, weight[] = {2,3,3,4}, prices[] = {1,5,2,9}, max_weight = 7, n, result;
  for (i=0; i<argc; i++) {
    printf("%d: \"%s\"\n", i, argv[i]);
  }
  n = (sizeof(weight))/(sizeof(weight[0]));
  result = knapsack(prices, weight, n, max_weight);
  printf("%d\n", result);
  return 0;
}

РЕЗУЛЬТАТЫ