ZERO / HERO
Packing a bag with a weight limit

0/1 Knapsack

The analogy

You have a bag that holds 10kg and a pile of items with weights and values. Each item you either take or leave — no halves. For every item and every possible remaining capacity, you ask one question: am I better off taking this or skipping it?

Visualizer

Take it or skip it

step 1 / 8
012345678
no items000000000
w2 v3
w3 v4
w4 v5
w5 v6

Four items (weight/value) and a bag holding 8. Columns are remaining capacity; rows add one item at a time.dp[i][w] = best value using first i items within capacity w

def knapsack(weights, values, W):
    dp = [0] * (W + 1)
    for wt, val in zip(weights, values):
        for w in range(W, wt - 1, -1):     # DESCENDING!
            dp[w] = max(dp[w], dp[w - wt] + val)
    return dp[W]

# ascending would allow reusing the same item
# => that is the UNBOUNDED knapsack

def knapsack_2d(weights, values, W):       # keeps choices
    n = len(weights)
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        wt, val = weights[i-1], values[i-1]
        for w in range(W + 1):
            dp[i][w] = dp[i-1][w]                       # skip
            if w >= wt:
                dp[i][w] = max(dp[i][w],
                               dp[i-1][w - wt] + val)   # take
    return dp

# O(nW) — pseudo-polynomial, NOT polynomial in input size
Check yourself

In the 1D version you loop capacity ASCENDING. What have you built?