CODEWITHSUNDEEP
javarecursionknapsack-problem
Andy897
Andy897

Reputation: 7133

Recursive solution for Knapsack in Java

HERE recursive solution is given for Knapsack problem, but I am not able to understand it. Why there is no check on W? Shall we not return if W (leftover weight) goes below 0? What is the point it going a step ahead in a particular recursive call is W is already less than 0 ?

// 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)
                  );
}

Upvotes: 1

Views: 4545

Answers (2)

Walt
Walt

Reputation: 1426

Notice that in every recursive call value of W is also getting updated. And we subtract a new weight from leftover weight W only if it is less than W. Otherwise that weight can not be included. This logic is captured here

if (wt[n-1] > W)
       return knapSack(W, wt, val, n-1);

As you can see above, if new weight is more than leftover we do not include it by reducing value of n by 1. Had it been lesser than W, we would have returned Max of Knapsack including and not including it.

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

Upvotes: 3

kraskevich
kraskevich

Reputation: 18556

The weight cannot become negative. The weight of the currect item is subtracted only if it is less than or equal to the total remaining weight.

Upvotes: 2

Related Questions