0/1 Knapsack, Unbounded Knapsack & Bounded Knapsack: Formulations, Memory Optimizations & Monotonic Deques

The Knapsack Problem family represents the foundational archetype of combinatorial optimization and Dynamic Programming. From resource allocation in cloud scheduling to capital budgeting and payload packing, understanding the recurrence relations, state space geometries, and memory compression techniques transforms quadratic NP-hard abstractions into hyper-efficient, sub-millisecond algorithms.

1. The 0/1 Knapsack Formulation: Optimal Substructure & 2D Recurrence

In the classical 0/1 Knapsack problem, an algorithm is given N distinct items, where each item i possesses an integer weight w[i] and integer value v[i], alongside a container with maximum weight capacity W. The objective is to maximize total accumulated value without exceeding capacity W, constrained by the condition that each item may be selected at most once (x[i] ∈ {0, 1}).

The problem satisfies Bellman's Principle of Optimality: an optimal solution contains optimal solutions to its subproblems. We define the 2D state dp[i][w] as the maximum value achievable considering only the first i items with a weight budget of w:

    dp[i][w] = dp[i - 1][w]                                             (if w < w[i])

    dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - w[i]] + v[i])                (if w ≥ w[i])

The base condition is initialized as dp[0][w] = 0 for all w ∈ [0, W] and dp[i][0] = 0 for all i ∈ [0, N]. Evaluating this full grid requires O(N × W) time and O(N × W) space. While pseudo-polynomial, practical applications require strict memory reduction.

2. 1D Memory Compression & The Directionality Invariant

Inspecting the 2D recurrence demonstrates that calculating row i depends exclusively on elements from row i - 1. Naively, this permits space reduction to O(2W) by alternating between two row buffers. However, we can collapse the entire state into a single 1D array of length W + 1:

The Reverse Loop Invariant (0/1 Knapsack)

When computing dp[w] = max(dp[w], dp[w - w[i]] + v[i]) in-place, the capacity loop must iterate backwards from W down to w[i]:

vector<int> dp(W + 1, 0);
for (int i = 0; i < N; ++i) {
    for (int w = W; w >= weight[i]; --w) {
        dp[w] = max(dp[w], dp[w - weight[i]] + value[i]);
    }
}

Because w is processed in descending order, when calculating dp[w], the value at dp[w - weight[i]] has not yet been overwritten in the current item iteration. It reliably retains the value from item i - 1, preventing any item from being selected more than once.

3. Unbounded Knapsack: Forward Iteration & Infinite Multiplicities

In the Unbounded Knapsack (Complete Knapsack) problem, an unlimited supply of each item is available (x[i] ≥ 0). The recurrence relation reflects this by allowing transitions from the current item's own updated row:

    dp[i][w] = max(dp[i - 1][w], dp[i][w - w[i]] + v[i])
  

When compressing Unbounded Knapsack into a 1D array, the loop direction is deliberately flipped to forward iteration from w[i] up to W:

vector<int> dp(W + 1, 0);
for (int i = 0; i < N; ++i) {
    for (int w = weight[i]; w <= W; ++w) {
        dp[w] = max(dp[w], dp[w - weight[i]] + value[i]);
    }
}

By traversing forwards, dp[w - weight[i]] represents the already-updated optimal state for the current item i, seamlessly allowing the item to be selected repeatedly to maximize density.

4. Bounded Knapsack: Binary Decomposition vs. Monotonic Queue Optimization

In the Bounded Knapsack problem, each item i has a maximum finite quantity c[i]. Naively treating this as c[i] separate 0/1 items results in unacceptable runtime complexity O(W × ∑ c[i]). Two primary paradigms optimize this bounded search space:

Binary Splitting (Power of 2 Bundling)

Any positive integer c can be uniquely partitioned into powers of two {1, 2, 4, 8, ..., 2^(k-1), R} where R = c - (2^k - 1).

By creating bundled composite items with weights 2^k × w[i] and values 2^k × v[i], the item count shrinks to O(∑ log2(c[i])), yielding an overall complexity of O(W × ∑ log2(c[i])).

Monotonic Queue (Sliding Window DP)

By expressing capacity as w = q × w[i] + r where 0 ≤ r < w[i], the state transitions decouple into w[i] independent sliding windows over quotient q.

Using a monotonic double-ended queue (deque), candidate states enter and exit the queue at most once per remainder class, achieving optimal O(N × W) time without logarithmic overhead.

5. Algorithmic Comparison: Knapsack Paradigms Matrix

Variant	Multiplicity x[i]	Time Complexity	Space Complexity	Loop Direction (1D)
0/1 Knapsack	x[i] ∈ {0, 1}	O(NW)	O(W)	Reverse (W → w[i])
Unbounded Knapsack	x[i] ≥ 0 (∞)	O(NW)	O(W)	Forward (w[i] → W)
Bounded (Binary Split)	0 ≤ x[i] ≤ c[i]	O(W ∑ log2(c[i]))	O(W)	Reverse on bundles
Bounded (Monotonic Queue)	0 ≤ x[i] ≤ c[i]	O(NW)	O(W)	Deque per remainder

6. Engineering Takeaways & Production Implementation Runbook

Capacity Bounds Check: When capacity W is massive (e.g., W > 10^7) but values v[i] are small (e.g., ∑ v[i] ≤ 10^5), invert the DP state: let dp[v] denote the minimum weight required to achieve value v.
Bitset Acceleration: In 0/1 Subset Sum existence queries, accelerate transitions by up to 64x using std::bitset<MAX_W>: dp |= (dp << w[i]).
Cache Locality: 1D flat arrays fit completely inside CPU L1/L2 data caches, providing orders-of-magnitude lower cycle latency compared to multidimensional heap pointer vectors.