dp[c] describes capacity/sum c. For 0/1 items (w,v), iterate c from C down to w and set dp[c]=Agg(dp[c],dp[c-w]⊕v). For unbounded use, iterate c upward.
Recognition signals
Each object has a weight/cost and possibly a value.
The target is a capacity, exact sum, partition, or coin total.
Each item presents a choose/skip branch and many subsets reach one capacity.
The bound supports O(nC) pseudo-polynomial work.
Items are explicitly single-use, unbounded, or bounded-use.
False friends
Signal
Why it is different
Huge capacity with few items
O(nC) is infeasible; consider meet-in-the-middle, sparse reachable sets, or DP by value.
Order is part of the outcome
Item-outer loops deduplicate combination order; ordered sequence counting needs a different loop structure.
Greedy value density
Density is valid for divisible items, not indivisible 0/1 choices.
Core invariant
After the first i item types, dp[c] contains exactly the allowed answers using those types. Descending 0/1 capacity prevents the current item from reading its own update.
State, transition, and processing order
Item
Definition
State
Feasibility, optimum, or count for capacity/sum c, with False, -infinity, or infinity for unreachable states.
Transition
Combine skipping at old dp[c] with taking the item from dp[c-w]. Direction decides whether dp[c-w] belongs to the previous item layer or current layer.
Frontier / order
Item layers advance forward; capacity runs backward for 0/1 and forward for unbounded reuse.
Python skeleton
def zero_one_max_value(items, capacity):
dp = [0] * (capacity + 1)
for weight, value in items:
for c in range(capacity, weight - 1, -1):
dp[c] = max(dp[c], dp[c - weight] + value)
return dp[capacity]
Correctness sketch
Initially, choosing no items satisfies the base interpretation.
For item i, any optimum either skips it and keeps old dp[c], or takes it and extends a solution at c-w that excludes i.
Descending capacity keeps c-w on the prior layer, enforcing at-most-once use; induction gives the 0/1 optimum.
Complexity
Time
Space
Parameters
O(nC)
O(C) compressed
n is item count and C the numeric capacity/target; the bound is pseudo-polynomial.
Edge cases
zero capacity
zero-weight items
unreachable sentinel
negative values
modular counts
exact fill versus at-most capacity
Error patterns
Pattern
Why it fails / fix
Ascending capacity for 0/1
It reads dp[c-w] updated by the same item and silently becomes unbounded knapsack.
Confusing combinations and permutations
Item-outer loops usually count unordered combinations; capacity-outer loops may count different orders separately.
Initializing unreachable states to zero
For exact-capacity maximization, nonexistent constructions become falsely feasible; use negative infinity.
Ignoring pseudo-polynomial scale
Runtime depends on numeric C rather than its bit length and can be enormous.
Selection and exclusion rules
State how many times each item may be used.
Distinguish an upper-bound capacity from an exact target.