Skip to main content

Knapsack Variants and State Design

What This Concept Is​

Given $n$ items with weights $w_i$ and values $v_i$, and a knapsack of capacity $W$, choose a subset (or multiset, depending on variant) with total weight $\le W$ maximizing total value. Three canonical variants and one frequent cousin cover almost all real instances.

0/1 knapsack. Each item is taken at most once.

$$dp[i][c] = \begin{cases} \max\big(dp[i-1][c],\ dp[i-1][c - w_i] + v_i\big) & w_i \le c \ dp[i-1][c] & w_i > c \end{cases}$$

Space-reduced single array (descending $c$):

for each item (w, v):
    for c from W down to w:
        dp[c] = max(dp[c], dp[c - w] + v)

Unbounded knapsack. Each item can be taken any number of times.

$$dp[c] = \max_{,i,:,w_i \le c} \big( dp[c - w_i] + v_i \big).$$

Space-reduced single array (ascending $c$):

for c from 1 to W:
    for each item (w, v):
        if w <= c: dp[c] = max(dp[c], dp[c - w] + v)

Bounded knapsack. Each item $i$ can be taken up to $k_i$ times. Handled either by direct DP (an extra $k_i$ loop) or by binary splitting: decompose $k_i$ copies into groups of sizes $1, 2, 4, 8, \ldots, r$ and treat as a 0/1 knapsack over the groups. Runtime $O(n W \log k_{\max})$.

Subset sum / partition / coin change. These are knapsacks with value = weight (or with "count ways / min count" instead of "max value"); the state design is the same.

All variants are pseudo-polynomial: runtime is $O(nW)$ (or $O(nW \log k_{\max})$ for binary-split bounded), polynomial in $W$ but not in the bit length of $W$.

Why It Matters Here​

Knapsack is the cleanest example of state design driven by a capacity dimension. Most real optimization problems with a budget, weight, time, or resource constraint reduce to some knapsack variant -- and picking the right variant is half the battle.

The 0/1 vs unbounded distinction is also where most students first meet the fill-direction trick: iterating $c$ in descending order prevents reusing an item in the current iteration; iterating $c$ in ascending order deliberately allows reuse. That one-line change is the difference between two entirely different problems.

Knapsack is also where "pseudo-polynomial" bites for the first time. If $W$ is given in binary as a 64-bit integer, $O(nW)$ is exponential in input size. This is why "subset sum with large numbers" is NP-hard, while "subset sum with small numbers" has a DP -- a subtlety worth understanding before you ship.

Concrete Examples​

Example 1: 0/1 knapsack, small instance. Items (weight, value): $(2, 3), (3, 4), (4, 5), (5, 6)$. Capacity $W = 5$.

Single-array trace after each item:

  • after $(2,3)$: dp = [0,0,3,3,3,3]
  • after $(3,4)$: dp = [0,0,3,4,4,7]
  • after $(4,5)$: dp = [0,0,3,4,5,7]
  • after $(5,6)$: dp = [0,0,3,4,5,7]

Answer: $7$ (take items $(2,3)$ and $(3,4)$).

Example 2: Unbounded coin change -- minimum coins. Denominations ${1, 3, 4}$, target $A = 6$. Recurrence:

$$\mathrm{coins}[c] = 1 + \min_{,d,:,d \le c} \mathrm{coins}[c - d], \quad \mathrm{coins}[0] = 0.$$

Trace:

$c$0123456
coins0121122

Minimum coins for $6$ is $2$ (i.e., $3 + 3$). Greedy-largest-first would return $3$ ($4 + 1 + 1$) -- a classic DP-beats-greedy case.

Example 3: Bounded knapsack via binary splitting. Item $i$ with $k_i = 13$ copies: split as $1 + 2 + 4 + 6$ ($1 + 2 + 4 = 7$, remainder $13 - 7 = 6$). Now 0/1 knapsack over these $4$ pseudo-items. General formula: $\lfloor \log_2(k_i + 1) \rfloor$ pseudo-items per real item.

Common Confusion / Misconceptions​

"Wrong loop direction." The most frequent bug: iterating $c$ in the wrong direction gets unbounded behavior when you wanted 0/1 (or vice versa). Mental model:

  • descending $c$ (0/1): $dp[c - w_i]$ still holds the previous item's value, so adding me extends "without me."
  • ascending $c$ (unbounded): $dp[c - w_i]$ may already reflect "with me," so you can stack me again.

"Pseudo-polynomial is the same as polynomial." It is not. If $W$ is given in binary, "polynomial in $W$" is exponential in the input size. "Can I make change for amount $A = 10^{18}$?" looks like knapsack but kills the naive DP.

"Greedy works for coin change." Only for canonical currency systems ({1, 5, 10, 25, …} in USD, for example). On arbitrary denominations like ${1, 3, 4}$, greedy fails. The safe move is DP unless you can prove the currency is canonical.

"Fractional and 0/1 knapsack are the same." Fractional knapsack allows arbitrary fractions and does admit a greedy algorithm (take items in decreasing value/weight ratio). 0/1 knapsack does not -- the same greedy rule fails.

"Knapsack always means maximizing value." The same state design covers subset sum (is any sum equal to $S$?), partition (split into two equal-sum halves), and count-ways variants. Change the combining operation (max -> or -> +) and you change the problem, not the state.

How To Use It​

Decide the variant first:

  1. "Each item at most once" -> 0/1, single-array descending loop.
  2. "Each item unlimited" -> unbounded, single-array ascending loop.
  3. "Each item bounded by $k_i$" -> bounded, binary-split to 0/1, or triple loop if $k$ is small.
  4. "Count the number of ways" -> replace max with +, initialize $dp[0] = 1$.
  5. "Minimize count / coins" -> replace max with min, initialize $dp[0] = 0$, others $+\infty$.

Then:

  1. Write dp, choose rolled vs full table (rolled works unless you need reconstruction), and confirm complexity $O(nW)$ or $O(nW \log k_{\max})$.
  2. If $W$ is astronomical, knapsack may not fit at all -- pivot to FPTAS approximation for 0/1 knapsack, or to linear programming for fractional-friendly variants.

Transfer / Where This Shows Up Later​

  • S3 Software Design. Feature-flag rollout plans with per-flag risk budget reduce to 0/1 knapsack: fit as many high-value features as possible under the risk cap.
  • S5 Networking. Packet-scheduling under MTU or bandwidth constraints ("which subset of packets to transmit this window?") is a knapsack with latency-weighted value.
  • S6 Databases. Buffer-pool admission policies pick which pages to cache under a memory budget -- unbounded/0-1 knapsack with access-frequency value.
  • S7 Architecture. "Select a subset of ADRs to review given a finite review budget, maximizing risk reduction" is exactly 0/1 knapsack. This is also how RCDA prioritization (S7 M5) is formalized.
  • Phase 7 AI. Feature selection under compute budget, hyperparameter pruning, and multi-armed bandit exploration all use knapsack-flavored DPs with expected value.

Check Yourself​

  1. Why does descending-$c$ order prevent double-counting an item in 0/1 knapsack?
  2. What exactly does "pseudo-polynomial" mean, and why does it matter for knapsack with 64-bit $W$?
  3. How does binary splitting reduce bounded knapsack to 0/1, and why is the new number of items $O!\left(\sum_i \log k_i\right)$?
  4. Give an instance where the greedy "value/weight ratio" heuristic on 0/1 knapsack is arbitrarily bad.
  5. State the recurrence for "number of ways to make change for $A$" using unbounded coin denominations.
  6. How would you add a "must include at least one item of type X" constraint? What extra state dimension is needed?

Mini Drill or Application​

  1. Implement 0/1 knapsack with the rolled array and verify with at least two hand-computed examples.
  2. Add reconstruction (list chosen items). Rolling loses enough information; either keep the full 2D table or log choices per $c$.
  3. Implement unbounded knapsack using the single-array ascending loop. Solve "coin change: minimum coins for amount $A$" as an instance.
  4. Implement bounded knapsack via binary splitting. Verify on 20 random instances against a brute-force enumeration for $n \le 15$.
  5. Generate a random small instance and confirm all three variants agree on their appropriate reductions (e.g., bounded with $k_i = 1$ equals 0/1; unbounded with $k_i = \lfloor W / w_i \rfloor$ equals the bounded DP at that cap).
  6. Implement partition: given an array, decide if it can be split into two equal-sum subsets. Reduce to subset-sum with target = total/2.

Read This Only If Stuck​