0/1 Knapsack Problem
Software Engineer path · lesson 35 of 99A combinatorial optimization problem: Given a set of items, each with a weight and a value, determine which items to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.
Up to 5 items; weights 1–10, values 0–30. Greedy trap: best value-per-weight first loses.
Row 0: with no items, every capacity is worth 0.
- 1dp[0][c] = 0 for every capacity c
- 2for i in 1..n, for c in 0..W:
- 3 skip = dp[i-1][c]
- 4 take = dp[i-1][c - w_i] + v_i (only if w_i <= c)
- 5 dp[i][c] = max(skip, take)
- 6walk back from dp[n][W]: a changed row means item i was taken
- Cells filled
- 0 / 32
- Take wins
- 0 / 17
Tap any element in the diagram to inspect its state at this step.
Keys: ← → step, Space play/pause. Predict mode pauses before key steps and asks what happens next.
Fill the knapsack table
Order the steps of the 0/1 knapsack DP.
Tap a piece, then tap where it goes — or drag it. Tap the tray to take one back.
- 1Drop a step here
- 2Drop a step here
- 3Drop a step here
- 4Drop a step here
- 5Drop a step here
Test your knowledge
What does dp[i][w] represent?
The short version
Think of a thief robbing a store with a small backpack. He can't take everything. He must choose a combination of items that fits in the bag but has the highest total resale value.
In more depth
The Choice Diagram
The Knapsack problem represents the classic Constraint Optimization pattern. For every item, you have a choice:
We take the maximum of these two choices.
0/1 vs Unbounded:
When to reach for this
- Maximize value given a capacity constraint
- Find if a subset sums to a Detailed Target
- Min/Max number of ways to reach a target using elements
Interview Questions
References & Further Reading
Love this visualization?
Sign up to track your progress, earn achievements, use the AI assistant, and access your personal learning dashboard.
100% free • No credit card required