Algorithms / Knapsack Family
Least You Need to Know: Knapsack Family, Capacity States, and Reuse vs One-Time Choice
Knapsack questions are about resource budgets. The main design choice is whether each item may be used once, infinitely often, or only for feasibility, because that determines the state meaning and the update order that keeps the recurrence honest.
The least you need to know
- A classic 0/1 knapsack state uses a prefix of items and a remaining or used capacity.
- Subset sum is a feasibility-style knapsack where values and weights align.
- Complete knapsack differs from 0/1 knapsack because items may be reused.
- One-dimensional DP updates must iterate capacity in the right direction to respect reuse rules.
- The recurrence is only as correct as the meaning you assign to each state.
Key notation
dp[c]
best value or feasibility summary at capacity `c`
0/1
each item usable at most once
complete
an item may be taken repeatedly
Tiny worked example
- In 0/1 knapsack, after considering an item of weight `w`, updating capacities from high to low prevents the same item from being counted twice.
- In complete knapsack, low-to-high updates are appropriate because reusing the current item is allowed.
Common mistakes
- Students often memorize loops without tying them to the one-use versus reusable-item invariant.
- Feasibility problems like subset sum use the same shape as value-maximization knapsack, but the state stores booleans instead of scores.
- The most common bug is an update order that accidentally reuses a supposedly one-time item.
How to recognize this kind of problem
- The prompt asks for the best value under a capacity limit, or whether an exact sum can be formed.
- Each decision is take-or-skip, but the item-reuse rule matters.
- A greedy ratio argument feels tempting, but the small integer budget hints at dynamic programming.