0/1 knapsack DP

Build a DP table for 0/1 knapsack.

0/1 knapsack DP

We build a 2D DP table for 0/1 knapsack. dp[i][w] is the max value using the first i items with capacity w.

The table is (n+1) × (W+1); the first row and column are zero.

Each cell stores the best of take-or-skip for that item.

Cell recurrence

If weights[i-1] ≤ w then dp[i][w] = max(dp[i-1][w], values[i-1] + dp[i-1][w-weights[i-1]]). Else dp[i][w] = dp[i-1][w].

This recurrence clearly encodes the take-or-skip decision for each item.

The result is in dp[n][W]; the bottom-right corner of the table.

Exercise Knapsack DP

Write knap_dp(W, weights, values, n). 0/1 knapsack with a 2D DP table. Print 220 with print(knap_dp(50, [10, 20, 30], [60, 100, 120], 3)).

Show example solution

def knap_dp(W, weights, values, n):
    # Knapsack DP
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for w in range(1, W + 1):
            if weights[i - 1] <= w:
                dp[i][w] = max(dp[i - 1][w], values[i - 1] + dp[i - 1][w - weights[i - 1]])
            else:
                dp[i][w] = dp[i - 1][w]
    return dp[n][W]
print(knap_dp(50, [10, 20, 30], [60, 100, 120], 3))

Test yourself

Take recurrence

take = values[i - 1] + dp[____][w - weights[i - 1]]

Show answer

take = values[i - 1] + dp[i - 1][w - weights[i - 1]]

0/1 knapsack DP: match the terms

dp[i][w]

Cell
take

Take
skip

Skip
max

Max
What is 0/1 knapsack DP's time complexity?
- O(n^2)
- O(nW)
- O(W^2)
- O(n + W)
Show answer

O(nW) — O(nW).

Next lesson: Decision table

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies