234. Zero-One Knapsack

Why this mechanism works

For each item and capacity, compare skipping it with taking it plus the best smaller-capacity result from before this item. A one-dimensional table can preserve that older layer by scanning capacities downward. Ascending order would read a value already improved by the same item and permit repeated use.

State and boundaries

Before an item pass, dp[c] is the best value using earlier items within capacity c. Descending updates keep dp[c-weight] in that previous-item layer.

Protocol

1. Initialize every capacity to zero.
2. For each item scan capacity down to its weight.
3. Set dp[c]=max(dp[c],dp[c-weight]+value).
4. Return dp[capacity].

Visualization

one item weight 2,value 3; capacity 4
descending: dp[4] reads old dp[2]=0 -> 3
ascending would make dp[2]=3, then dp[4]=6 illegally

Python implementation

def zero_one_knapsack(weights, values, capacity):
    dp = [0] * (capacity + 1)
    for weight, value in zip(weights, values):
        for c in range(capacity, weight - 1, -1):
            dp[c] = max(dp[c], dp[c - weight] + value)
    return dp[capacity]

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L2 zero_one_knapsack: dp = [0] * (capacity + 1)
weights=[2, 3, 4]; values=[3, 4, 5]; capacity=5; dp=[0, 0, 0, 0, 0, 0]

L3 zero_one_knapsack: for weight, value in zip(weights, values):
weights=[2, 3, 4]; values=[3, 4, 5]; capacity=5; dp=[0, 0, 0, 0, 0, 0]; weight=2; value=3

L4 zero_one_knapsack: for c in range(capacity, weight - 1, -1):
weights=[2, 3, 4]; values=[3, 4, 5]; capacity=5; dp=[0, 0, 0, 0, 0, 0]; weight=2; value=3; c=5

L5 zero_one_knapsack: dp[c] = max(dp[c], dp[c - weight] + value)
weights=[2, 3, 4]; values=[3, 4, 5]; capacity=5; dp=[0, 0, 0, 0, 0, 3]; weight=2; value=3; c=5

L4 zero_one_knapsack: for c in range(capacity, weight - 1, -1):
weights=[2, 3, 4]; values=[3, 4, 5]; capacity=5; dp=[0, 0, 0, 0, 0, 3]; weight=2; value=3; c=4

L5 zero_one_knapsack: dp[c] = max(dp[c], dp[c - weight] + value)
weights=[2, 3, 4]; values=[3, 4, 5]; capacity=5; dp=[0, 0, 0, 0, 3, 3]; weight=2; value=3; c=4

L4 zero_one_knapsack: for c in range(capacity, weight - 1, -1):
weights=[2, 3, 4]; values=[3, 4, 5]; capacity=5; dp=[0, 0, 0, 0, 3, 3]; weight=2; value=3; c=3

L5 zero_one_knapsack: dp[c] = max(dp[c], dp[c - weight] + value)
weights=[2, 3, 4]; values=[3, 4, 5]; capacity=5; dp=[0, 0, 0, 3, 3, 3]; weight=2; value=3; c=3

... 9 intermediate state changes omitted ...

L3 zero_one_knapsack: for weight, value in zip(weights, values):
weights=[2, 3, 4]; values=[3, 4, 5]; capacity=5; dp=[0, 0, 3, 4, 4, 7]; weight=4; value=5; c=3

L4 zero_one_knapsack: for c in range(capacity, weight - 1, -1):
weights=[2, 3, 4]; values=[3, 4, 5]; capacity=5; dp=[0, 0, 3, 4, 4, 7]; weight=4; value=5; c=5

L4 zero_one_knapsack: for c in range(capacity, weight - 1, -1):
weights=[2, 3, 4]; values=[3, 4, 5]; capacity=5; dp=[0, 0, 3, 4, 4, 7]; weight=4; value=5; c=4

L5 zero_one_knapsack: dp[c] = max(dp[c], dp[c - weight] + value)
weights=[2, 3, 4]; values=[3, 4, 5]; capacity=5; dp=[0, 0, 3, 4, 5, 7]; weight=4; value=5; c=4

L2 zero_one_knapsack: dp = [0] * (capacity + 1)
weights=[2]; values=[3]; capacity=4; dp=[0, 0, 0, 0, 0]

L3 zero_one_knapsack: for weight, value in zip(weights, values):
weights=[2]; values=[3]; capacity=4; dp=[0, 0, 0, 0, 0]; weight=2; value=3

L4 zero_one_knapsack: for c in range(capacity, weight - 1, -1):
weights=[2]; values=[3]; capacity=4; dp=[0, 0, 0, 0, 0]; weight=2; value=3; c=4

L5 zero_one_knapsack: dp[c] = max(dp[c], dp[c - weight] + value)
weights=[2]; values=[3]; capacity=4; dp=[0, 0, 0, 0, 3]; weight=2; value=3; c=4

L4 zero_one_knapsack: for c in range(capacity, weight - 1, -1):
weights=[2]; values=[3]; capacity=4; dp=[0, 0, 0, 0, 3]; weight=2; value=3; c=3

L5 zero_one_knapsack: dp[c] = max(dp[c], dp[c - weight] + value)
weights=[2]; values=[3]; capacity=4; dp=[0, 0, 0, 3, 3]; weight=2; value=3; c=3

L4 zero_one_knapsack: for c in range(capacity, weight - 1, -1):
weights=[2]; values=[3]; capacity=4; dp=[0, 0, 0, 3, 3]; weight=2; value=3; c=2

L5 zero_one_knapsack: dp[c] = max(dp[c], dp[c - weight] + value)
weights=[2]; values=[3]; capacity=4; dp=[0, 0, 3, 3, 3]; weight=2; value=3; c=2

Why the solution is correct

A legal optimum either excludes the current item or includes it once with an earlier-item solution fitting the remaining capacity. The recurrence compares exactly those cases. Descending iteration ensures the take branch reads a state that cannot already contain this item, preserving zero-one usage.

Time and space

O(N*C) time and O(C) auxiliary storage for N items and capacity C. This is pseudopolynomial in capacity, not polynomial in its bit length.

Common mistakes

Ascending capacities change the problem to unlimited item reuse. Initializing unreachable exact weights is unnecessary here because states mean at-most capacity, not exact fill.

Reasoning card

Transfer exercise

Require exact total weight rather than at-most capacity and revise unreachable-state initialization accordingly.