0/1 Knapsack Problem: DP Solution with Space Optimization

By /

The 0/1 Knapsack problem is one of the most important DP patterns. Unlike coin change (unbounded knapsack), each item can only be used once. This “take it or leave it” decision structure appears in dozens of interview problems.

Problem

Given a list of items with weights and values, and a knapsack with maximum capacity W, find the maximum total value you can carry. Each item can be used at most once.

weights = [1, 3, 4, 5]
values  = [1, 4, 5, 7]
capacity = 7

Maximum value = 9 (items with weight 3 and 4: values 4+5=9)

2D DP Solution

def knapsack_2d(weights: list[int], values: list[int], capacity: int) -> int:
    """
    dp[i][w] = max value using first i items with capacity w.
    For each item i:
        - Skip item: dp[i][w] = dp[i-1][w]
        - Take item: dp[i][w] = dp[i-1][w - weight[i]] + value[i]  (if weight[i] <= w)
    Time: O(n * W), Space: O(n * W)
    """
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        w_i = weights[i - 1]
        v_i = values[i - 1]
        for w in range(capacity + 1):
            # Skip this item
            dp[i][w] = dp[i - 1][w]
            # Take this item (if it fits)
            if w_i  int:
    """
    Space-optimized 0/1 knapsack. dp[w] = max value with capacity w.
    Reverse iteration prevents using the same item twice within one pass.
    Time: O(n * W), Space: O(W)
    """
    dp = [0] * (capacity + 1)

    for i in range(len(weights)):
        w_i, v_i = weights[i], values[i]
        # Reverse order: ensures we use dp[w - w_i] from the PREVIOUS item's row
        for w in range(capacity, w_i - 1, -1):
            dp[w] = max(dp[w], dp[w - w_i] + v_i)

    return dp[capacity]

weights = [1, 3, 4, 5]
values  = [1, 4, 5, 7]
print(knapsack_1d(weights, values, 7))  # 9

Why Reverse Order Matters

In the 1D version, if you iterate forward (left to right), when you compute dp[w], dp[w - weight[i]] has already been updated in this pass — meaning you could use item i multiple times. Reverse iteration ensures you see the previous row’s values.

# Wrong (unbounded): would allow using same item multiple times
for i in range(len(weights)):
    for w in range(weights[i], capacity + 1):  # forward
        dp[w] = max(dp[w], dp[w - weights[i]] + values[i])

# Correct (0/1): each item used at most once
for i in range(len(weights)):
    for w in range(capacity, weights[i] - 1, -1):  # reverse
        dp[w] = max(dp[w], dp[w - weights[i]] + values[i])

Common Interview Problems Using 0/1 Knapsack

Problem Mapping
LeetCode 416: Partition Equal Subset Sum Can we pick items with total = sum/2? Items are the numbers, capacity = target
LeetCode 494: Target Sum Assign +/- to each number; equivalent to subset sum with target
LeetCode 1049: Last Stone Weight II Split stones into two groups; minimize difference = maximize subset sum 
def can_partition(nums: list[int]) -> bool:
    """
    LeetCode 416: Can we partition into two equal-sum subsets?
    Equivalent to: can we find a subset with sum = total/2?
    """
    total = sum(nums)
    if total % 2 != 0:
        return False

    target = total // 2
    dp = [False] * (target + 1)
    dp[0] = True  # Empty subset sums to 0

    for num in nums:
        for w in range(target, num - 1, -1):  # Reverse for 0/1 knapsack
            dp[w] = dp[w] or dp[w - num]

    return dp[target]

Knapsack vs Coin Change Comparison

Property 0/1 Knapsack Unbounded Knapsack (Coin Change)
Item use At most once Unlimited
Inner loop direction Reverse (capacity → 0) Forward (0 → capacity)
Classic problem Partition Equal Subset Sum Coin Change, Coin Change 2

Related DP Problems

  • Coin Change — unbounded knapsack variant: iterate forward to allow reuse; vs 0/1 knapsack reverse iteration to prevent reuse
  • Longest Common Subsequence — both use 2D DP with the “take it or leave it” framing for each element; understand both tables
Scroll to Top