Knaspsack Recursion

#1

int profitKnapsack(int *weights, int *prices, int N, int C)
{
//Base case is when bag is full or when there are no items left
if (N == 0 || C == 0)
{
return 0;
}
//Recursive Case

int profit1, profit2;
profit1 = 0;
profit2 = 0;
//Include item
if (C >= weights[N - 1])
{
	profit1 = prices[N - 1] + profitKnapsack(weights, prices, N - 1, C - weights[N - 1]);
}
//Exclude item
if (C < weights[N - 1])
{
	profit2 = profitKnapsack(weights, prices, N - 1, C);
}
return max(profit1, profit2);

}

I wrote this code which is slightly different from Prateek sirs code what is wrong here? I am getting 120 as answer but answer should be 140

#2

hi @aryamaan1011, please provide be the input for which you are getting 120 as the answer,
also please provide me your full code link using online ide, so i can check for other mistakes

from what i can infer from the code snippet you have sent , is that, you are not handling the case where we don’t select the last item , let me explain ,
for every item we have two choices whether we select it or not but you are only consider the case in which you are selecting the item when C >= weights[N - 1]
so, the code should be something like :-

int profitKnapsack(int *weights, int *prices, int N, int C)
{
//Base case is when bag is full or when there are no items left
	if (N == 0 || C == 0)
	{
		return 0;
	}
//Recursive Case

	int profit1, profit2;
	profit1 = 0;
	profit2 = 0;
//Include item
	if (C >= weights[N - 1])
	{
        // selecting the last item 
		 profit1 = prices[N - 1] + profitKnapsack(weights, prices, N - 1, C - weights[N - 1]);
		// Not selecting the last item
         profit2 = profitKnapsack(weights, prices, N - 1, C);
	}
//Exclude item
	if (C < weights[N - 1])
	{
		profit2 = profitKnapsack(weights, prices, N - 1, C);
	}
	return max(profit1, profit2);
}