Solve 0-1 knapsack problem

Given weights and values of n items, put these items in a sack of capacity W to get the maximum total value in the Sack. In other words, given two integer arrays val[0..n-1] and wt[0..n-1] which represent values and weights associated with n items respectively. Also given an integer W which represents knapsack capacity, find out the maximum value subset of val[] such that sum of the weights of this subset is smaller than or equal to W. You cannot break an item, either pick the complete item, or don’t pick it (0-1 property).

value[] = {15,5,25}
wt[] = {10,20,30}
W = 40
possible combination
w = {10} val = {15}
w = {20} val = {5}
w = {30} val = {25}
w = {10+20} val = {15+5} = 20
w = {10+30} val = {15+25} = 40
w = {20+30} not valid
Ans = 40

This problem can be solved by dynamic programming

To consider all the possible combinations there are two choices can be made

  • Either select the weight to the optimal set
  • Not to select the weight

The equation can be formed as follows

Initial Settings
V[i,w] = 0 <= w <= W and 0 <= i <=items(n)
V[0,w] = 0
V[i,w] = max (val[i-1] + V[i-1,w - w[i]], V[i-1, w)	
for 0<=i<=n and 0 < w <= W 

At V[i,w] either w[i] can be selected or ignored. If weight is select then its value val[i] is select and then V[i-1,w-w[i]] is selecting weight when w[i] is deducted from w. If the weight is not selected then previous value V[i-1, w] is selected

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

The above code is not completely optimized as function computes same subproblems multiple times.To store the computed state we can use two dimensional array V[i,w] where value at V[i,w] is optimized weight for weight w with i items.

public knapsack(int W, int wt[], int val[], int n) {
 int i, w;
 int K[][] = new int[n+1][W+1];      
 // Build table K[][] in bottom up manner
 for (i = 0; i <= n; i++) {
     for (w = 0; w <= W; w++) {
         if (i==0 || w==0)
              K[i][w] = 0;
         else if (wt[i-1] <= w)
               K[i][w] = Math.max(val[i-1] + K[i-1][w-wt[i-1]],  K[i-1][w]);
         else
               K[i][w] = K[i-1][w];
     }
  }  
  return K[n][W];
}

public static void main(String args[]) {
    int val[] = new int[]{60, 100, 120};
	int wt[] = new int[]{10, 20, 30};
	int  W = 50;
	int n = val.length;
	System.out.println(knapSack(W, wt, val, n));
}