0/1 Knapsack

    DSA · Intermediate

    Definition

    Choose items with weights and values to maximize value without exceeding capacity; each item used at most once.

    The template for many subset-choice DP problems.

    Diagram

    items (w,v): (1,1) …cap 4 → 5

    Flowchart

    dp[c] = best value with capacity cFor each itemLoop capacity backwardsdp[c] = max(dp[c], dp[c−w] + v)

    Example: 1D knapsack

    items, cap = [(1, 1), (3, 4), (4, 5)], 4
dp = [0] * (cap + 1)
for w, v in items:
    for c in range(cap, w - 1, -1):
        dp[c] = max(dp[c], dp[c - w] + v)
print(dp[cap])

    Output: 5

    Complexity

    O(n × W) time · O(W) space

    Key points

    • Backward loop prevents reuse
    • Forward loop = unbounded knapsack

    Interview questions

    Why loop capacity backwards?

    So each item's update uses values from before it was considered.

    More DSA topics

    ArraysLinked ListStackQueue