# 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));
}
``````