CODEWITHSUNDEEP
c
Federico Galfione
Federico Galfione

Reputation: 1109

Unexpected result from Knapsack problem recursive function

I have to write a simple program to solve the Knapsack problem. I wrote this code for now and I think this is all I need, but I keep having different results everytime I execute it. All I can think is that there is a problem of memory deallocation, but I don't know how to solve it. Any ideas?

P.S. Maybe it's a stupid question but I never worked in 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;
}

RESULTS enter image description here

Upvotes: 0

Views: 51

Answers (1)

liamcomp
liamcomp

Reputation: 386

It looks like you are indexing the arrays with an number that is too large. You get the size of the array doing

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

You cannot index weight at n because it only has indices 0 to n-1

Try calling 

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

Upvotes: 2

Related Questions