# The 0-1 Knapsack Problem

Updated: Apr 10, 2021

We are given an array of values values and an array of weights weights:

values[i] corresponds to the value of the i'th item

weights[i] corresponds to the weight of the i'th item

Given these two lists and an integer W, find a subset of the items in this "knapsack" that has maximal overall value, yet stays <= maxWeight in total weight.

**Example 1**:

**Input**:
values = [60, 50, 70, 30]
weights = [5, 3, 4, 2]
maxWeight = 8
**Output**: 120
**Explanation**: We take items 1 and 2 (zero-indexed) for a total value of 120 and a total weight of 7.

**Example 2**:

**Input**:
values = [60, 100, 120, 80, 30]
weights = [10, 20, 30, 40, 50]
maxWeight = 400
**Output**: 390
**Explanation**: We take all items for a total value of 390 and a total weight of 150, still below 400.

**Constraints**:

You

**can not**split an itemOnce you select an item you

**can not**select it again

**Solution:**

```
public class Knapsack
{
public static void main(String args[])
{
int W = 5;
int[] values = {40, 30, 20, 10};
int[] weights = {3, 2, 1, 4};
int[][] dp = new int[values.length + 1][W + 1];
for (int i = 0; i <= values.length; i++)
{
for (int j = 0; j <= W; j++)
{
if (i == 0 || j == 0) dp[i][j] = 0;
else if (weights[i-1] > j) dp[i][i] = dp[i - 1][j];
else dp[i][j] = Math.max(values[i-1] + dp[i - 1][j - weights[i-1]], dp[i - 1][j]);
}
}
System.out.println(dp[values.length][W]);
System.out.println(Arrays.deepToString(dp));
}
}
```