Given a list of integers representing weights and a target number representing maximum capacity of knapsack, return the maximum weight the knapsack can hold.
example: inputs --> wt: [1,3,5], W= 7
output -> 6
example: inputs --> wt: [4,8,5,9], W= 20
output -> 18
static int knapSack(int W, List<Integer> wt)
{
int n = wt.size();
// 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.get(n-1) > W)
return knapSack(W, wt.subList(0,n-1));
// Return the maximum of two cases:
// (1) nth item included
// (2) not included
else
return Math.max(wt.get(n-1) + knapSack(W - wt.get(n-1), wt.subList(0,n-1)),
knapSack(W,wt.subList(0,n-1))
);
}