top of page
Search

# 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 item

• Once 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));
}
}

```