Loading learning content...
Read aloud is unavailable in this browser.
Imagine you're a treasure hunter standing before a chest of valuables, but your backpack has limited capacity. Each item has a weight and a value. You cannot exceed your capacity, and you cannot take fractions of items—it's all or nothing for each piece. How do you maximize the total value you carry away?
This seemingly simple scenario is the 0/1 Knapsack Problem, and it stands as one of the most important problems in algorithm design and optimization theory. The "0/1" refers to the binary decision for each item: either you take it (1) or you leave it (0). No partial selections allowed.
The 0/1 Knapsack problem is not merely an academic curiosity—it models countless real-world optimization scenarios: investment portfolio selection with capital constraints, cargo loading with weight limits, task scheduling with resource budgets, and even cutting-stock problems in manufacturing. Mastering this problem provides a template for attacking an entire class of constrained optimization challenges.
By the end of this page, you will understand the 0/1 Knapsack problem at a deep, structural level. You will learn to formalize the problem mathematically, understand why greedy approaches fail, develop the recurrence relation that enables dynamic programming, and implement both memoized and tabulated solutions. You'll also learn to reconstruct the optimal item selection, not just compute the optimal value.
Let's establish a rigorous definition of the 0/1 Knapsack problem before diving into solutions.
Given:
n items, where item i has:
w[i] (positive integer)v[i] (positive integer or real number)W (positive integer)Find: A subset S of items that maximizes the total value:
$$\text{maximize } \sum_{i \in S} v[i]$$
Subject to: $$\sum_{i \in S} w[i] \leq W$$
The key constraint is the binary decision for each item—each item is either fully included or fully excluded. This binary constraint is what distinguishes 0/1 Knapsack from its fractional counterpart, and it's precisely this constraint that makes the problem NP-hard in general.
| Item | Weight | Value | Value/Weight Ratio |
|---|---|---|---|
| Item 1 | 2 | 12 | 6.0 |
| Item 2 | 1 | 10 | 10.0 |
| Item 3 | 3 | 20 | 6.67 |
| Item 4 | 2 | 15 | 7.5 |
Knapsack Capacity: W = 5
With these items and capacity, what's the optimal selection? This is the question we'll answer through dynamic programming, but first let's understand why simpler approaches fail.
Before committing to the complexity of dynamic programming, a natural question arises: can we solve this greedily? After all, if we could sort items by some criterion and greedily select them, we'd have an O(n log n) algorithm instead of the O(nW) dynamic programming solution.
Let's examine the three most intuitive greedy strategies and understand why each fails:
Strategy 1: Greedy by Value Select items in decreasing order of value until the knapsack is full.
Strategy 2: Greedy by Weight Select items in increasing order of weight (lightest first) until full.
Strategy 3: Greedy by Value-to-Weight Ratio Select items in decreasing order of value-per-unit-weight.
Let's test these on our example with W = 5:
| Strategy | Items Selected | Total Weight | Total Value | Optimal? |
|---|---|---|---|---|
| By Value (highest first) | Item 3 (20), Item 4 (15) | 5 | 35 | ✓ |
| By Weight (lightest first) | Item 2 (10), Item 1 (12), Item 4 (15) | 5 | 37 | ✓ |
| By Ratio | Item 2 (10), Item 4 (15), Item 3 ✗ | 3 (Item 3 doesn't fit) | 25 + ... | ✗ |
In this particular instance, some greedy strategies happen to find good solutions. But this is coincidental—greedy approaches can fail spectacularly on carefully constructed instances.
A Counterexample for All Greedy Strategies:
| Item | Weight | Value | Ratio |
|---|---|---|---|
| A | 6 | 30 | 5.0 |
| B | 5 | 24 | 4.8 |
| C | 5 | 24 | 4.8 |
Greedy by ratio: Selects A (value 30, weight 6). Remaining capacity 4, nothing else fits. Total: 30.
Greedy by value: Same result—A first, nothing else fits. Total: 30.
Optimal solution: Select B + C. Weight: 5 + 5 = 10. Value: 24 + 24 = 48.
Every greedy strategy yields 30, but the optimal is 48—a 60% improvement! This demonstrates that no simple greedy criterion guarantees optimality for 0/1 Knapsack.
The Fundamental Issue:
Greedy algorithms make irrevocable decisions at each step. For 0/1 Knapsack, selecting a high-value item early might consume capacity that could have been better used by a combination of smaller items. The problem lacks the greedy choice property—a locally optimal choice may foreclose globally optimal solutions.
This is precisely why we need dynamic programming: to consider all possible combinations systematically while avoiding the exponential blowup of brute-force enumeration.
The key insight for solving 0/1 Knapsack via dynamic programming is recognizing the binary decision structure inherent in the problem.
For each item, we face exactly two choices:
This binary fork creates a decision tree. For n items, there are 2^n possible subsets to consider—brute force would take exponential time. But here's the crucial observation: many subproblems recur.
Consider deciding whether to include item i. Regardless of which items we selected from {1, 2, ..., i-1}, the decision for item i depends only on:
1 through i contribute to an optimal solutionThis structure enables us to define subproblems in terms of:
If we have an optimal solution that includes item i, then the remaining items must form an optimal solution for the remaining capacity. Similarly, if item i is excluded from an optimal solution considering items 1 to i, then the optimal solution for items 1 to (i-1) with the same capacity is also optimal for items 1 to i. This is optimal substructure.
Visualizing the Decision:
At each item, we branch:
[Item i, Capacity c]
|
+---------------+---------------+
| |
[Exclude item i] [Include item i]
| (if w[i] <= c)
v v
[Item i-1, Capacity c] [Item i-1, Capacity c - w[i]]
+ v[i]
The recursive structure is now clear:
i leaves us with the subproblem of items 1..i-1 with unchanged capacityi (if it fits) gives us v[i] plus the optimal solution for items 1..i-1 with reduced capacityWe take the maximum of these two choices.
Let's formalize the recursive structure into a precise recurrence relation. This is the heart of the dynamic programming solution.
Define:
dp[i][c] = Maximum value achievable using items 1, 2, ..., i with knapsack capacity exactly c.
Recurrence:
123456789101112131415
// For all items i from 1 to n, and all capacities c from 0 to W: dp[i][c] = { // Base case: No items to choose from 0 if i == 0 // Case 1: Item i is too heavy to include dp[i-1][c] if w[i] > c // Case 2: Item i fits; choose maximum of exclude vs include max(dp[i-1][c], otherwise dp[i-1][c - w[i]] + v[i])} // Final answer: dp[n][W]Breaking Down the Recurrence:
Base Case (i == 0):
With zero items available, the maximum value we can achieve is zero, regardless of capacity. This provides the foundation for building up solutions.
Item Too Heavy (w[i] > c):
If item i weighs more than our current capacity c, we cannot include it. The optimal solution for items 1..i with capacity c is simply the optimal solution for items 1..i-1 with the same capacity.
Item Fits (w[i] <= c):
We have a genuine choice:
dp[i-1][c] — the best we can do without item idp[i-1][c - w[i]] + v[i] — the value of item i plus the best we can do with the remaining capacity and remaining itemsWe take the maximum because we want the optimal solution.
The recurrence is correct because:
Every valid subset can be characterized by decisions on each item. The recurrence systematically explores all decisions.
The most natural implementation directly translates the recurrence into recursive code with memoization. This approach starts from the original problem and recursively breaks it down, caching results to avoid recomputation.
Memoization Strategy:
memo[i][c] to store computed values1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071
def knapsack_memo(weights: list[int], values: list[int], capacity: int) -> int: """ Solve 0/1 Knapsack using top-down memoization. Args: weights: List of item weights values: List of item values (same length as weights) capacity: Maximum knapsack capacity Returns: Maximum value achievable without exceeding capacity """ n = len(weights) # Memoization cache: -1 indicates uncomputed # memo[i][c] = max value using items 0..i-1 with capacity c memo = [[-1] * (capacity + 1) for _ in range(n + 1)] def solve(item_index: int, remaining_capacity: int) -> int: """ Recursive helper with memoization. Args: item_index: Number of items to consider (1-indexed conceptually) remaining_capacity: Current available capacity Returns: Maximum value for this subproblem """ # Base case: no items left to consider if item_index == 0: return 0 # Base case: no capacity left if remaining_capacity == 0: return 0 # Check memo cache if memo[item_index][remaining_capacity] != -1: return memo[item_index][remaining_capacity] # Current item (0-indexed in our arrays) i = item_index - 1 weight_i = weights[i] value_i = values[i] # Case 1: Exclude current item exclude = solve(item_index - 1, remaining_capacity) # Case 2: Include current item (if it fits) include = 0 if weight_i <= remaining_capacity: include = value_i + solve(item_index - 1, remaining_capacity - weight_i) # Take maximum and cache result = max(exclude, include) memo[item_index][remaining_capacity] = result return result return solve(n, capacity) # Example usageif __name__ == "__main__": weights = [2, 1, 3, 2] values = [12, 10, 20, 15] capacity = 5 max_value = knapsack_memo(weights, values, capacity) print(f"Maximum value: {max_value}") # Output: 37Time Complexity: O(n × W)
Space Complexity: O(n × W) for the memoization table, plus O(n) for the recursion stack.
The memoization approach is intuitive because it directly mirrors the recurrence, computing only the subproblems actually needed (on-demand).
The tabulation approach builds the solution iteratively from the ground up, filling a table in dependency order. This eliminates recursion overhead and provides better cache locality.
Table Structure:
dp[i][c] = Maximum value using first i items with capacity c
Fill Order:
We fill row by row (increasing i), and within each row, left to right (increasing c). This ensures that when we compute dp[i][c], we've already computed dp[i-1][c] and dp[i-1][c-w[i]].
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071
def knapsack_tabulation(weights: list[int], values: list[int], capacity: int) -> int: """ Solve 0/1 Knapsack using bottom-up tabulation. Args: weights: List of item weights values: List of item values (same length as weights) capacity: Maximum knapsack capacity Returns: Maximum value achievable without exceeding capacity """ n = len(weights) # Create DP table # dp[i][c] = max value using items 0..i-1 with capacity c dp = [[0] * (capacity + 1) for _ in range(n + 1)] # Base case: dp[0][c] = 0 for all c (already initialized to 0) # Fill the table row by row for i in range(1, n + 1): # Current item (0-indexed in arrays) weight_i = weights[i - 1] value_i = values[i - 1] for c in range(capacity + 1): # Case 1: Exclude current item dp[i][c] = dp[i - 1][c] # Case 2: Include current item (if it fits) if weight_i <= c: include_value = dp[i - 1][c - weight_i] + value_i dp[i][c] = max(dp[i][c], include_value) return dp[n][capacity] # Visualization helperdef knapsack_with_table(weights: list[int], values: list[int], capacity: int): """Returns both the max value and the complete DP table for visualization.""" n = len(weights) dp = [[0] * (capacity + 1) for _ in range(n + 1)] for i in range(1, n + 1): weight_i = weights[i - 1] value_i = values[i - 1] for c in range(capacity + 1): dp[i][c] = dp[i - 1][c] if weight_i <= c: dp[i][c] = max(dp[i][c], dp[i - 1][c - weight_i] + value_i) return dp[n][capacity], dp # Example with table visualizationif __name__ == "__main__": weights = [2, 1, 3, 2] values = [12, 10, 20, 15] capacity = 5 max_value, table = knapsack_with_table(weights, values, capacity) print("DP Table:") print(" ", " ".join(f"c={c}" for c in range(capacity + 1))) for i, row in enumerate(table): item_info = f"Item {i}" if i > 0 else "No items" print(f"{item_info:9}", row) print(f"Maximum value: {max_value}")Tracing Through the Example:
Let's trace through our example with items [(w=2, v=12), (w=1, v=10), (w=3, v=20), (w=2, v=15)] and capacity W=5:
| c=0 | c=1 | c=2 | c=3 | c=4 | c=5 | |
|---|---|---|---|---|---|---|
| No items (i=0) | 0 | 0 | 0 | 0 | 0 | 0 |
| Item 1 (w=2,v=12) | 0 | 0 | 12 | 12 | 12 | 12 |
| Item 2 (w=1,v=10) | 0 | 10 | 12 | 22 | 22 | 22 |
| Item 3 (w=3,v=20) | 0 | 10 | 12 | 22 | 30 | 32 |
| Item 4 (w=2,v=15) | 0 | 10 | 15 | 25 | 30 | 37 |
Reading the Table:
dp[4][5] = 37 is our answer—the maximum value with all 4 items and capacity 5dp[4][5] = max(dp[3][5], dp[3][3] + 15) = max(32, 22 + 15) = 37This tells us that including Item 4 is beneficial—we get 37 instead of the 32 we'd get without it.
Finding the maximum value is often insufficient—we need to know which items to select. The DP table contains all the information needed to reconstruct the solution by tracing back through our decisions.
Backtracking Logic:
Starting from dp[n][W], for each item i from n down to 1:
dp[i][c] != dp[i-1][c], item i was included (the value changed)w[i] from the remaining capacity and record item idp[i][c] == dp[i-1][c], item i was excluded; move up without changing capacity123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960
def knapsack_with_items(weights: list[int], values: list[int], capacity: int) -> tuple[int, list[int]]: """ Solve 0/1 Knapsack and return both the max value and the selected items. Args: weights: List of item weights values: List of item values capacity: Maximum knapsack capacity Returns: Tuple of (max_value, list of selected item indices) """ n = len(weights) # Build the DP table dp = [[0] * (capacity + 1) for _ in range(n + 1)] for i in range(1, n + 1): weight_i = weights[i - 1] value_i = values[i - 1] for c in range(capacity + 1): dp[i][c] = dp[i - 1][c] if weight_i <= c: dp[i][c] = max(dp[i][c], dp[i - 1][c - weight_i] + value_i) # Backtrack to find selected items selected_items = [] remaining_capacity = capacity for i in range(n, 0, -1): # If value changed from previous row, item i was included if dp[i][remaining_capacity] != dp[i - 1][remaining_capacity]: selected_items.append(i - 1) # Convert to 0-indexed remaining_capacity -= weights[i - 1] # Reverse to get items in original order selected_items.reverse() return dp[n][capacity], selected_items # Example usageif __name__ == "__main__": weights = [2, 1, 3, 2] values = [12, 10, 20, 15] capacity = 5 max_value, selected = knapsack_with_items(weights, values, capacity) print(f"Maximum value: {max_value}") print(f"Selected items (0-indexed): {selected}") print("Selected item details:") for idx in selected: print(f" Item {idx}: weight={weights[idx]}, value={values[idx]}") total_weight = sum(weights[i] for i in selected) print(f"Total weight: {total_weight} / {capacity}")For our example:
Selected Items: 1, 2, 4 (0-indexed: 0, 1, 3) Total Value: 12 + 10 + 15 = 37 ✓
We've established a comprehensive understanding of the 0/1 Knapsack problem—the foundational problem of the knapsack family and a paradigmatic example of dynamic programming.
What's Next:
In the next page, we'll dive deeper into the state representation—understanding why we track "capacity remaining" as our state variable, and how this seemingly simple choice enables the entire dynamic programming approach. We'll also explore alternative state formulations and their implications.
You now understand the 0/1 Knapsack problem at a foundational level—from problem formulation through recurrence development to complete implementation with solution reconstruction. This forms the basis for all knapsack variants we'll explore in this module.