0/1 Knapsack and Unbounded Knapsack: Complete Formulation, 1D Memory Optimization & Bounded Variants

The Knapsack family represents the foundational archetype of Dynamic Programming. Understanding the exact state transitions, boundary conditions, and memory compression techniques transforms complex combinatorial optimization problems into deterministic polynomial-time algorithms.

1. 0/1 Knapsack Problem Formulation

Given $N$ items, each with weight $w_i$ and value $v_i$, and a knapsack with maximum weight capacity $W$, determine the maximum value that can be placed in the knapsack such that each item can be selected at most once.

State Space & Recurrence Relation

Let dp[i][w] represent the maximum value obtainable using a subset of the first i items with a weight constraint of w:

// 2D State Transition Recurrence
if (w < w[i]) {
    dp[i][w] = dp[i - 1][w];
} else {
    dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - w[i]] + v[i]);
}

Knapsack Variant	Item Constraint	Iteration Direction	Time Complexity	Space Complexity
0/1 Knapsack	At most 1 of each item	Reverse: $W o w_i$	$O(N cdot W)$	$O(W)$ with 1D array
Unbounded Knapsack	Unlimited copies of each item	Forward: $w_i o W$	$O(N cdot W)$	$O(W)$ with 1D array
Bounded Knapsack	$c_i$ copies of item $i$	Binary Splitting + Reverse	$O(W sum log c_i)$	$O(W)$ with 1D array

2. 1D Memory Compression (Rolling Array)

Notice that computing dp[i][w] only requires the values from row i - 1. By iterating backward from capacity $W$ down to $w_i$, we can compress the 2D matrix into a single 1D array without overwriting the states needed for subsequent updates:

// C++20 1D Space Optimized 0/1 Knapsack
int solve01Knapsack(const vector<int>& weights, const vector<int>& values, int W) {
    int n = weights.size();
    vector<int> dp(W + 1, 0);
    
    for (int i = 0; i < n; ++i) {
        for (int w = W; w >= weights[i]; --w) {
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i]);
        }
    }
    return dp[W];
}

3. Unbounded Knapsack: Forward Iteration

In the Unbounded Knapsack problem, an item can be chosen infinitely many times. Consequently, dp[w] depends on the current row's updated state dp[w - weights[i]] rather than the previous row's state. Simply reversing the inner loop direction from backward to forward ($w_i o W$) solves the problem.