230 views
int max(int a, int b) { return (a > b) ? a : b; }

// Returns the maximum value that can be
// put in a knapsack of capacity W
int knapSack(int W, int wt[], int val[], int n)
{
// Base Case
if (n == 0 || W == 0)
return 0;

// If weight of the nth item is more than
// Knapsack capacity W, then this item cannot
// be included in the optimal solution
if (wt[n - 1] > W)
return knapSack(W, wt, val, n - 1);

// Return the maximum of two cases:
// (1) nth item included
// (2) not included
else
return max(
val[n - 1]
+ knapSack(W - wt[n - 1],
wt, val, n - 1),
knapSack(W, wt, val, n - 1));
}

// Driver program to test above function
int main()
{
int val[] = { 60, 100, 120 };
int wt[] = { 10, 20, 30 };
int W = 50;
int n = sizeof(val) / sizeof(val);
printf("%d", knapSack(W, wt, val, n));
return 0;
}

“return max(
val[n - 1]
+ knapSack(W - wt[n - 1],
wt, val, n - 1),
knapSack(W, wt, val, n - 1));

}” This statement implies that the max value return by the two different recursive problems right?

The $knapSack(W, wt[ ], val[ ], n)$ returns maximum value that can be put into $sack$ of maximum weight capacity of $W$ from $n$ items.

The code snippet that you mentioned only runs when $wt[n] \le W$ ie you get to choose whether to take $n^{th}$ item or not.

Now, if you choose to take $n^{th}$ item then the value that you'll get is $val[n] + knapSack(W-wt[n], wt[ ], val[ ], n-1)$ ie if you choose to take $n^{th}$ item your sack will have value of this $n^{th}$ item plus whatever value you get from remaining $n-1$ items.

Now, if you choose not to take $n^{th}$ item then the value that you'll get is $knapSack(W, wt[ ], val[ ], n-1)$ ie if you choose not to take $n^{th}$ item your sack will have whatever value you get from remaining $n-1$ items.

At last, you return whichever choice gives you maximum value as that was the original goal.

### 1 comment

For the sake of reference, you can apply the brute force method by taking sample weight and profit. Here we will be using a 2-D array to store a maximum value keeping in mind that value<=weight.