0/1 Knapsack in Java: Explanation & Practice

Maximum value with limited weight capacity

Problem summary

Given items with weights and values, and a knapsack capacity, find the maximum value you can carry. Each item can only be taken once.

Starter code

public class Main {
    public static void main(String[] args) {
        int[] weights = {1, 3, 4, 5};
        int[] values = {1, 4, 5, 7};
        int capacity = 7;
        
        // dp[i][w] = max value using first i items with capacity w
        // Take item: values[i] + dp[i-1][w-weights[i]]
        // Skip item: dp[i-1][w]
        // Print: Max value: 9
    }
}

Expected output and test cases

capacity=7, take items with weight 3,4 → value 4+5
```
Max value: 9
```
weights=[2,3,4], values=[3,4,5], capacity=5
```
Max value: 8
```
capacity=0 → can't take anything
```
Max value: 0
```

Hints

Use 2D DP: dp[i][w] = max value with first i items and capacity w
For each item: either take it or leave it
Take: values[i-1] + dp[i-1][w-weights[i-1]] (if weight fits)
Leave: dp[i-1][w]

Related Data Structures & Algorithms exercises

Practice all Data Structures & Algorithms exercises · Run this idea in the Java compiler