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.

Dark Mode

230 views

0 votes

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[0]);

printf("%d", knapSack(W, wt, val, n));

return 0;

}

Hello Folks, can you please help me to understand the below snippet of code?

“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?

// 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[0]);

printf("%d", knapSack(W, wt, val, n));

return 0;

}

Hello Folks, can you please help me to understand the below snippet of code?

“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?

1 vote

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.

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.