0/1 Knapsack Problem
The 0/1 Knapsack Problem maximizes total value of selected items without exceeding weight capacity W using pseudo-polynomial Dynamic Programming in O(n * W) time and O(W) space.
Difficulty: Medium · Interactive Visualizer · C++ / Python / Java / JS Code
0/1 Knapsack Problem
Given $n$ items—each with weight $w_i$ and value $v_i$—and a knapsack of capacity $W$, choose a subset of items (each item taken at most once) to maximize total value without exceeding weight $W$. The 0/1 Knapsack pattern is one of the most versatile DP templates in computer science, underpinning Subset Sum, Partition Equal Subset Sum, and Unbounded Knapsack.
At a Glance
| Property | Value |
| :--- | :--- |
| Time Complexity | $O(n \cdot W)$ (pseudo-polynomial) |
| Auxiliary Space | $O(W)$ (1D rolling array) / $O(n \cdot W)$ (to reconstruct chosen items) |
| 0/1 vs. Unbounded Loop Order | 0/1: loop capacity w backward (W down to wt); Unbounded: loop forward |
| Best Used When | Budget/capacity-constrained selection, subset sum, equal-sum partitioning |
---
How It Works (1D Space-Optimized DP)
Let dp[c] be the maximum value achievable with capacity c.
1. Initialize dp[0..W] = 0.
2. For each item (wt, val):
- Iterate
cfromWdown towt:
$dp[c] = \max(dp[c],\ dp[c - wt] + val)$
3. Return dp[W].
procedure knapsack01(weights, values, W):
dp = array of size W + 1 filled with 0
for i = 0 to n - 1:
for c = W down to weights[i]:
dp[c] = max(dp[c], dp[c - weights[i]] + values[i])
return dp[W]
Step-by-Step Trace
Items (wt, val): (2, 3), (3, 4), (4, 5), capacity $W = 5$:
- Init:
dp = [0, 0, 0, 0, 0, 0] - Item
(2, 3):dp = [0, 0, 3, 3, 3, 3] - Item
(3, 4):dp[5] = max(3, dp[2]+4) = 7,dp[4] = max(3, dp[1]+4) = 4,dp[3] = max(3, dp[0]+4) = 4→dp = [0, 0, 3, 4, 4, 7] - Item
(4, 5):dp[5] = max(7, dp[1]+5) = 7,dp[4] = max(4, dp[0]+5) = 5→dp = [0, 0, 3, 4, 5, 7] - Result:
dp[5] = 7(items(2, 3)and(3, 4)).
---
Complexity & Key Insights
- Why Backward Loop for 0/1 Knapsack: Looping
cfromWdown towtguaranteesdp[c - wt]still holds the result from the previous item (so the current item is used at most once). Looping forward lets the current item be reused multiple times—which is Unbounded Knapsack! - When $W$ Is Huge ($W \le 10^9$) but Total Value $V$ Is Small ($V \le 10^5$): Flip the DP! Define
minWeight[v]= minimum weight needed to achieve exact valuev, giving $O(n \cdot V)$ time instead of $O(n \cdot W)$. - Fractional vs. 0/1 Knapsack: If items can be split fractionally, a greedy sort by
val / wtworks in $O(n \log n)$. For indivisible 0/1 items, greedy fails (e.g.,W = 50, items(10, 60), (20, 100), (30, 120)→ greedy takes 10+20=160, optimal is 20+30=220).
---
Practice Problems
Easy
1. Classic 0/1 Knapsack ($O(W)$ Space)
Given item weights, values, and capacity W, return the maximum achievable value.
Approach: 1D backward-loop 0/1 Knapsack DP. Time: $O(nW)$. Space: $O(W)$.
<details>
<summary>Show C++ Solution</summary>
#include <algorithm>
#include <iostream>
#include <vector>
int knapsack01(const std::vector<int>& wt, const std::vector<int>& val, int W) {
std::vector<int> dp(W + 1, 0);
for (size_t i = 0; i < wt.size(); ++i) {
for (int c = W; c >= wt[i]; --c) {
dp[c] = std::max(dp[c], dp[c - wt[i]] + val[i]);
}
}
return dp[W];
}
int main() {
std::cout << knapsack01({10, 20, 30}, {60, 100, 120}, 50) << "\n"; // 220
return 0;
}
</details>
2. Partition Equal Subset Sum (LeetCode 416)
Given positive integers nums, determine whether the array can be partitioned into two subsets with equal sum.
Approach: If sum is odd, return false. Otherwise, check whether a subset sums to target = sum / 2 using 0/1 boolean DP (dp[s] = dp[s] || dp[s - x] looping backward). Time: $O(n \cdot \text{sum})$. Space: $O(\text{sum})$.
<details>
<summary>Show C++ Solution</summary>
#include <iostream>
#include <numeric>
#include <vector>
bool canPartition(const std::vector<int>& nums) {
int total = std::accumulate(nums.begin(), nums.end(), 0);
if (total % 2 != 0) return false;
int target = total / 2;
std::vector<bool> dp(target + 1, false);
dp[0] = true;
for (int x : nums) {
for (int s = target; s >= x; --s) {
if (dp[s - x]) dp[s] = true;
}
}
return dp[target];
}
int main() {
std::cout << std::boolalpha << canPartition({1, 5, 11, 5}) << " "
<< canPartition({1, 2, 3, 5}) << "\n";
return 0;
}
</details>
---
Intermediate
3. Target Sum (Count Ways with + / -, LeetCode 494)
Assign + or - to each element of nums so the expression evaluates to target. Return the number of distinct assignments.
Approach: Let $P$ be the sum of + elements and $N$ the sum of - elements. Then $P - N = \text{target}$ and $P + N = \text{total}$, so $P = (\text{total} + \text{target}) / 2$. Count subsets summing to $P$ with 0/1 Knapsack! Time: $O(n \cdot P)$. Space: $O(P)$.
<details>
<summary>Show C++ Solution</summary>
#include <cmath>
#include <iostream>
#include <numeric>
#include <vector>
int findTargetSumWays(const std::vector<int>& nums, int target) {
int total = std::accumulate(nums.begin(), nums.end(), 0);
if (std::abs(target) > total || (total + target) % 2 != 0) return 0;
int P = (total + target) / 2;
std::vector<int> dp(P + 1, 0);
dp[0] = 1;
for (int x : nums) {
for (int s = P; s >= x; --s) {
dp[s] += dp[s - x];
}
}
return dp[P];
}
int main() {
std::cout << findTargetSumWays({1, 1, 1, 1, 1}, 3) << "\n"; // 5
return 0;
}
</details>
4. Unbounded Knapsack (Unlimited Copies of Each Item)
Same as 0/1 Knapsack, except each item can be chosen any number of times.
Approach: Simply reverse the inner capacity loop direction to go forward (c = wt[i] up to W) so dp[c - wt[i]] already includes the current item! Time: $O(nW)$. Space: $O(W)$.
<details>
<summary>Show C++ Solution</summary>
#include <algorithm>
#include <iostream>
#include <vector>
int unboundedKnapsack(const std::vector<int>& wt, const std::vector<int>& val, int W) {
std::vector<int> dp(W + 1, 0);
for (size_t i = 0; i < wt.size(); ++i) {
for (int c = wt[i]; c <= W; ++c) {
dp[c] = std::max(dp[c], dp[c - wt[i]] + val[i]);
}
}
return dp[W];
}
int main() {
std::cout << unboundedKnapsack({2, 3, 4}, {3, 5, 6}, 7) << "\n"; // 2+2+3 -> 3+3+5 = 11
return 0;
}
</details>
---
Hard
5. Bounded Knapsack with Binary Splitting
Each item i has weight wt[i], value val[i], and a maximum count cnt[i]. Maximize value within capacity W.
Approach: Splitting cnt[i] into powers of 2 ($1, 2, 4, \dots, \text{remainder}$) represents every quantity in $[0, \text{cnt}[i]]$ using only $O(\log(\text{cnt}[i]))$ virtual 0/1 items! Time: $O(W \sum \log(\text{cnt}_i))$ instead of $O(W \sum \text{cnt}_i)$. Space: $O(W)$.
<details>
<summary>Show C++ Solution</summary>
#include <algorithm>
#include <iostream>
#include <vector>
int boundedKnapsack(const std::vector<int>& wt, const std::vector<int>& val,
const std::vector<int>& cnt, int W) {
std::vector<int> dp(W + 1, 0);
for (size_t i = 0; i < wt.size(); ++i) {
int rem = cnt[i];
for (int k = 1; rem > 0; k *= 2) {
int take = std::min(k, rem);
rem -= take;
int w = wt[i] * take;
int v = val[i] * take;
for (int c = W; c >= w; --c) {
dp[c] = std::max(dp[c], dp[c - w] + v);
}
}
}
return dp[W];
}
int main() {
std::cout << boundedKnapsack({2, 3}, {4, 5}, {3, 2}, 7) << "\n"; // 2*2 + 3*1 -> 8+5 = 13
return 0;
}
</details>
---
Related Algorithms
- Coin Change — Unbounded Knapsack specialized to counting/minimizing coins.
- Bitmask DP — handles small-$n$ subset optimization when capacity isn't a single scalar.