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