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

Question

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

PS Может быть, это глупый вопрос, но я никогда не работал в 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;
}

РЕЗУЛЬТАТЫ

Answer 1

Похоже, вы индексируете массивы слишком большим числом. Вы получаете размер массива, делая

n = (sizeof(weight))/(sizeof(weight[0]));

Вы не можете индексировать вес на n, потому что он имеет только индексы 0 до n-1

Попробуйте позвонить

result = knapsack(prices, weight, n-1, max_weight);