LeetCode Visualizer
How it worksAll visualizations

Step by step · Python

0/1 knapsack with dynamic programming, visualized

Given items with weights and values and a bag with a weight limit, which items give the most value? Each item is either taken whole or left behind — hence 0/1.

How it works
Python
weights = [1, 3, 4]
values = [15, 20, 30]
capacity = 5
n = len(weights)

dp = [[0] * (capacity + 1) for _ in range(n + 1)]

for i in range(1, n + 1):
    for w in range(1, capacity + 1):
        if weights[i - 1] <= w:
            dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1])
        else:
            dp[i][w] = dp[i - 1][w]

print(dp[n][capacity])

How the 0/1 knapsack works

dp[i][w] is the best value you can get from the first i items with capacity w. If item i does not fit, the answer is the same as without it: dp[i − 1][w]. If it fits, take the better of skipping it, dp[i − 1][w], and taking it, dp[i − 1][w − weight] + value. Fill the table row by row; the last cell is the answer.

The example has weights [1, 3, 4], values [15, 20, 30] and capacity 5. The best choice is the first and third items: weight 5, value 45.

What to watch for when it runs

  1. The table is drawn as a grid, and each new cell reads only from the row above it.
  2. Taking an item reads the row above, shifted back by that item’s weight.
  3. The bottom-right cell is the answer.

Time and space complexity

Time
O(n × W)
Space
O(n × W), or O(W) with a single row

n is the number of items and W the capacity. That is pseudo-polynomial: fast for small capacities, but it grows with the value of W, not its number of digits.

Related visualizations

Stuck on your own version?

Paste it into the visualizer and watch your own code run, line by line — bugs included.