14.4 0-1 knapsack problem¶
The knapsack problem is an excellent introduction to dynamic programming and one of its most common problem families. Variants include 0-1 knapsack, unbounded knapsack, and bounded knapsack.
We will begin with the most common variant, 0-1 knapsack.
Question
Given \(n\) items, where item \(i\) has weight \(wgt[i-1]\) and value \(val[i-1]\), and a knapsack of capacity \(cap\), each item may be chosen only once. What is the maximum total value that fits within the capacity?
As shown in Figure 14-17, item numbers \(i\) start at \(1\), while array indices start at \(0\). Item \(i\) therefore has weight \(wgt[i-1]\) and value \(val[i-1]\).
Figure 14-17 Example input for 0-1 knapsack
Description of Figure 14-17: 0-1 knapsack: optimal selection at capacity 50
Selecting the weight-20 banana and weight-30 grapes from five items fills capacity 50 exactly for a maximum value of 270.
In 0-1 knapsack, each item may be chosen at most once to maximize total value without exceeding knapsack capacity. This example has 5 items and knapsack capacity cap = 50; item IDs i run from 1 to 5, mapping to array index i - 1 (written wgt[i - 1] and val[i - 1] in the figure's table header).
At the upper left, a table lists the icon, weight, and value of items 1 through 5 (full data in the table below); row 2 (banana) is shaded light orange and row 3 (grapes) is shaded light purple, each sending an arrow to the purple knapsack icon at the upper right labeled "Knapsack capacity cap = 50".
Below, the result box states "Maximum value: 270" and pairs the banana and grapes icons with "Optimal choice: pack [banana and grapes] into the knapsack using 50 units of capacity in total".
| ID | Illustrated item | Weight | Value | Included in optimal choice? |
|---|---|---|---|---|
| 1 | Apple | 10 | 50 | No |
| 2 | Banana | 20 | 120 | Yes |
| 3 | Grapes | 30 | 150 | Yes |
| 4 | Pineapple | 40 | 210 | No |
| 5 | Watermelon | 50 | 240 | No |
Computed from the input data, choosing item 2 (banana) and item 3 (grapes) gives total weight 20 + 30 = 50 and total value 120 + 150 = 270. That is the highest value among all non-overweight subsets—beating, for instance, 260 from items 1 and 4 or 240 from item 5 alone, supplied here from the input table for comparison.
We can view 0-1 knapsack as \(n\) rounds of decisions, with two choices for each item: leave it out or put it in. It therefore fits the decision tree model.
The objective is to maximize value within a capacity limit, making dynamic programming a promising approach.
Step 1: Identify each decision, define the state, and establish the \(dp\) table
Leaving an item out keeps the available capacity unchanged; putting it in reduces the capacity. The state therefore consists of the current item number \(i\) and capacity \(c\), denoted by \([i, c]\).
State \([i, c]\) represents the subproblem of finding the maximum value obtainable from the first \(i\) items with capacity \(c\), denoted by \(dp[i, c]\).
We seek \(dp[n, cap]\), so we need a two-dimensional \(dp\) table of size \((n+1) \times (cap+1)\).
Step 2: Identify optimal substructure and derive the state transition equation
After deciding what to do with item \(i\), the remaining subproblem concerns the first \(i-1\) items. There are two cases.
- Leave item \(i\) out: Capacity stays unchanged, and the remaining state is \([i-1, c]\).
- Put item \(i\) in: Capacity decreases by \(wgt[i-1]\), value increases by \(val[i-1]\), and the remaining state is \([i-1, c-wgt[i-1]]\).
This reveals the optimal substructure: the maximum value \(dp[i, c]\) is the larger value obtained by leaving item \(i\) out or putting item \(i\) in. The state transition equation is:
If the current item's weight \(wgt[i - 1]\) exceeds the remaining capacity \(c\), the only option is to leave it out.
Step 3: Determine the boundary conditions and evaluation order
With no items or capacity \(0\), the maximum value is \(0\). Thus, the first column \(dp[i, 0]\) and first row \(dp[0, c]\) are both \(0\).
The current state \([i, c]\) depends on \([i-1, c]\) above and \([i-1, c-wgt[i-1]]\) to the upper left, so two nested loops can traverse the \(dp\) table in increasing index order.
We will now implement brute-force search, memoized search, and dynamic programming in that order.
1. Method 1: Brute-force search¶
The search has the following elements.
- Parameters: The state \([i, c]\).
- Return value: The subproblem solution \(dp[i, c]\).
- Base case: If there are no items left, \(i = 0\), or the remaining capacity is \(0\), stop recursion and return value \(0\).
- Pruning: If the current item is heavier than the remaining capacity, only the choice to leave it out is allowed.
def knapsack_dfs(wgt: list[int], val: list[int], i: int, c: int) -> int:
"""0-1 knapsack: brute-force search"""
# If all items have been considered or no capacity remains, return value 0
if i == 0 or c == 0:
return 0
# If the item exceeds the remaining capacity, it must be excluded
if wgt[i - 1] > c:
return knapsack_dfs(wgt, val, i - 1, c)
# Calculate the maximum values obtained by excluding and including item i
no = knapsack_dfs(wgt, val, i - 1, c)
yes = knapsack_dfs(wgt, val, i - 1, c - wgt[i - 1]) + val[i - 1]
# Return the larger value from the two choices
return max(no, yes)
/* 0-1 knapsack: brute-force search */
int knapsackDFS(vector<int> &wgt, vector<int> &val, int i, int c) {
// If all items have been considered or no capacity remains, return value 0
if (i == 0 || c == 0) {
return 0;
}
// If the item exceeds the remaining capacity, it must be excluded
if (wgt[i - 1] > c) {
return knapsackDFS(wgt, val, i - 1, c);
}
// Calculate the maximum values obtained by excluding and including item i
int no = knapsackDFS(wgt, val, i - 1, c);
int yes = knapsackDFS(wgt, val, i - 1, c - wgt[i - 1]) + val[i - 1];
// Return the larger value from the two choices
return max(no, yes);
}
/* 0-1 knapsack: brute-force search */
int knapsackDFS(int[] wgt, int[] val, int i, int c) {
// If all items have been considered or no capacity remains, return value 0
if (i == 0 || c == 0) {
return 0;
}
// If the item exceeds the remaining capacity, it must be excluded
if (wgt[i - 1] > c) {
return knapsackDFS(wgt, val, i - 1, c);
}
// Calculate the maximum values obtained by excluding and including item i
int no = knapsackDFS(wgt, val, i - 1, c);
int yes = knapsackDFS(wgt, val, i - 1, c - wgt[i - 1]) + val[i - 1];
// Return the larger value from the two choices
return Math.max(no, yes);
}
/* 0-1 knapsack: brute-force search */
int KnapsackDFS(int[] weight, int[] val, int i, int c) {
// If all items have been considered or no capacity remains, return value 0
if (i == 0 || c == 0) {
return 0;
}
// If the item exceeds the remaining capacity, it must be excluded
if (weight[i - 1] > c) {
return KnapsackDFS(weight, val, i - 1, c);
}
// Calculate the maximum values obtained by excluding and including item i
int no = KnapsackDFS(weight, val, i - 1, c);
int yes = KnapsackDFS(weight, val, i - 1, c - weight[i - 1]) + val[i - 1];
// Return the larger value from the two choices
return Math.Max(no, yes);
}
/* 0-1 knapsack: brute-force search */
func knapsackDFS(wgt, val []int, i, c int) int {
// If all items have been considered or no capacity remains, return value 0
if i == 0 || c == 0 {
return 0
}
// If the item exceeds the remaining capacity, it must be excluded
if wgt[i-1] > c {
return knapsackDFS(wgt, val, i-1, c)
}
// Calculate the maximum values obtained by excluding and including item i
no := knapsackDFS(wgt, val, i-1, c)
yes := knapsackDFS(wgt, val, i-1, c-wgt[i-1]) + val[i-1]
// Return the larger value from the two choices
return int(math.Max(float64(no), float64(yes)))
}
/* 0-1 knapsack: brute-force search */
func knapsackDFS(wgt: [Int], val: [Int], i: Int, c: Int) -> Int {
// If all items have been considered or no capacity remains, return value 0
if i == 0 || c == 0 {
return 0
}
// If the item exceeds the remaining capacity, it must be excluded
if wgt[i - 1] > c {
return knapsackDFS(wgt: wgt, val: val, i: i - 1, c: c)
}
// Calculate the maximum values obtained by excluding and including item i
let no = knapsackDFS(wgt: wgt, val: val, i: i - 1, c: c)
let yes = knapsackDFS(wgt: wgt, val: val, i: i - 1, c: c - wgt[i - 1]) + val[i - 1]
// Return the larger value from the two choices
return max(no, yes)
}
/* 0-1 knapsack: brute-force search */
function knapsackDFS(wgt, val, i, c) {
// If all items have been considered or no capacity remains, return value 0
if (i === 0 || c === 0) {
return 0;
}
// If the item exceeds the remaining capacity, it must be excluded
if (wgt[i - 1] > c) {
return knapsackDFS(wgt, val, i - 1, c);
}
// Calculate the maximum values obtained by excluding and including item i
const no = knapsackDFS(wgt, val, i - 1, c);
const yes = knapsackDFS(wgt, val, i - 1, c - wgt[i - 1]) + val[i - 1];
// Return the larger value from the two choices
return Math.max(no, yes);
}
/* 0-1 knapsack: brute-force search */
function knapsackDFS(
wgt: Array<number>,
val: Array<number>,
i: number,
c: number
): number {
// If all items have been considered or no capacity remains, return value 0
if (i === 0 || c === 0) {
return 0;
}
// If the item exceeds the remaining capacity, it must be excluded
if (wgt[i - 1] > c) {
return knapsackDFS(wgt, val, i - 1, c);
}
// Calculate the maximum values obtained by excluding and including item i
const no = knapsackDFS(wgt, val, i - 1, c);
const yes = knapsackDFS(wgt, val, i - 1, c - wgt[i - 1]) + val[i - 1];
// Return the larger value from the two choices
return Math.max(no, yes);
}
/* 0-1 knapsack: brute-force search */
int knapsackDFS(List<int> wgt, List<int> val, int i, int c) {
// If all items have been considered or no capacity remains, return value 0
if (i == 0 || c == 0) {
return 0;
}
// If the item exceeds the remaining capacity, it must be excluded
if (wgt[i - 1] > c) {
return knapsackDFS(wgt, val, i - 1, c);
}
// Calculate the maximum values obtained by excluding and including item i
int no = knapsackDFS(wgt, val, i - 1, c);
int yes = knapsackDFS(wgt, val, i - 1, c - wgt[i - 1]) + val[i - 1];
// Return the larger value from the two choices
return max(no, yes);
}
/* 0-1 knapsack: brute-force search */
fn knapsack_dfs(wgt: &[i32], val: &[i32], i: usize, c: usize) -> i32 {
// If all items have been considered or no capacity remains, return value 0
if i == 0 || c == 0 {
return 0;
}
// If the item exceeds the remaining capacity, it must be excluded
if wgt[i - 1] > c as i32 {
return knapsack_dfs(wgt, val, i - 1, c);
}
// Calculate the maximum values obtained by excluding and including item i
let no = knapsack_dfs(wgt, val, i - 1, c);
let yes = knapsack_dfs(wgt, val, i - 1, c - wgt[i - 1] as usize) + val[i - 1];
// Return the larger value from the two choices
std::cmp::max(no, yes)
}
/* 0-1 knapsack: brute-force search */
int knapsackDFS(int wgt[], int val[], int i, int c) {
// If all items have been considered or no capacity remains, return value 0
if (i == 0 || c == 0) {
return 0;
}
// If the item exceeds the remaining capacity, it must be excluded
if (wgt[i - 1] > c) {
return knapsackDFS(wgt, val, i - 1, c);
}
// Calculate the maximum values obtained by excluding and including item i
int no = knapsackDFS(wgt, val, i - 1, c);
int yes = knapsackDFS(wgt, val, i - 1, c - wgt[i - 1]) + val[i - 1];
// Return the larger value from the two choices
return myMax(no, yes);
}
/* 0-1 knapsack: brute-force search */
fun knapsackDFS(
wgt: IntArray,
_val: IntArray,
i: Int,
c: Int
): Int {
// If all items have been considered or no capacity remains, return value 0
if (i == 0 || c == 0) {
return 0
}
// If the item exceeds the remaining capacity, it must be excluded
if (wgt[i - 1] > c) {
return knapsackDFS(wgt, _val, i - 1, c)
}
// Calculate the maximum values obtained by excluding and including item i
val no = knapsackDFS(wgt, _val, i - 1, c)
val yes = knapsackDFS(wgt, _val, i - 1, c - wgt[i - 1]) + _val[i - 1]
// Return the larger value from the two choices
return max(no, yes)
}
### 0-1 knapsack: brute-force search ###
def knapsack_dfs(wgt, val, i, c)
# If all items have been considered or no capacity remains, return value 0
return 0 if i == 0 || c == 0
# If the item exceeds the remaining capacity, it must be excluded
return knapsack_dfs(wgt, val, i - 1, c) if wgt[i - 1] > c
# Calculate the maximum values obtained by excluding and including item i
no = knapsack_dfs(wgt, val, i - 1, c)
yes = knapsack_dfs(wgt, val, i - 1, c - wgt[i - 1]) + val[i - 1]
# Return the larger value from the two choices
[no, yes].max
end
Visualize execution
As shown in Figure 14-18, each item creates two branches, excluding it or including it, so the time complexity is \(O(2^n)\).
The recursion tree contains overlapping subproblems, such as \(dp[1, 10]\). Their number grows substantially with more items and larger capacity, especially when many items share the same weight.
Figure 14-18 Brute-force recursion tree for 0-1 knapsack
Description of Figure 14-18: Repeated recursion in 0-1 knapsack
In a dedicated three-item example with capacity 30, two different decision paths reach dp[1, 10]. Each expands its subtree once, so it is expanded twice in total.
In 0-1 knapsack, each item may be chosen at most once. Note that this figure uses a separate 3-item example distinct from the earlier figure and the main driver code: knapsack capacity cap = 30, and the 3 items have weights 10, 20, 20 and values 60, 110, 120 (see the table). State dp[i, c] denotes the maximum value obtainable from the first i items with remaining capacity c; the table header in the drawing writes wgt[i] and val[i] (with item IDs i starting at 1), whereas the code in the text indexes the arrays at i - 1.
When the current item fits, compare dp[i-1, c] (excluding it) with dp[i-1, c-wgt[i-1]] + val[i-1] (including it) and take the larger value; when it does not fit, take only the exclude branch. With no items left (i = 0) or remaining capacity 0 (c = 0), return 0.
Recursion starts at the root dp[3, 30] and makes decisions in order for item 3 (pineapple, weight 20, value 120), item 2 (watermelon, weight 20, value 110), and item 1 (apple, weight 10, value 60). Because item 2 and item 3 both have weight 20, taking either "exclude item 3, then include item 2" (dp[3, 30] → dp[2, 30] → dp[1, 10]) or "include item 3, then exclude item 2" (dp[3, 30] → dp[2, 10] → dp[1, 10]) subtracts weight 20, leaves capacity 10, and leaves only item 1 to consider, so the two distinct paths converge on the same subproblem dp[1, 10].
Brute-force search does not record previously solved subproblems, so upon encountering the two occurrences of dp[1, 10], it expands each one downward separately, comparing dp[0, 10] (excluding item 1) with dp[0, 0] + 60 (including item 1) both times; thus the same subproblem dp[1, 10] is expanded twice in full, making the second expansion redundant.
At the right child dp[2, 10], the remaining capacity is 10 while item 2 has weight 20, exceeding the remaining capacity. The node dp[1, -10] drawn in the figure is labeled "Prune: item weight > knapsack capacity" solely to illustrate the excluded overweight branch; the code in the text checks whether the item weight exceeds the remaining capacity before recursing, calling only the exclude branch dp[1, 10] when overweight rather than making a call with negative capacity.
The two tables below list the dedicated input items and the complete recursion tree shown in the figure; using the decision path from the root as the row header distinguishes multiple occurrences of the same state.
| Item ID | Illustrated item | Weight | Value |
|---|---|---|---|
| 1 | Apple | 10 | 60 |
| 2 | Watermelon | 20 | 110 |
| 3 | Pineapple | 20 | 120 |
| Decision path | State | Action or return | Child states and value gain |
|---|---|---|---|
| Root | dp[3,30] | Compare total values of excluding and including | Exclude: dp[2,30]; Include: dp[2,10]+120 |
| Exclude 3 | dp[2,30] | Compare total values of excluding and including | Exclude: dp[1,30]; Include: dp[1,10]+110 |
| Exclude 3 → Exclude 2 | dp[1,30] | Compare total values of excluding and including | Exclude: dp[0,30]; Include: dp[0,20]+60 |
| Exclude 3 → Exclude 2 → Exclude 1 | dp[0,30] | Base case, return 0 | Not expanded |
| Exclude 3 → Exclude 2 → Include 1 | dp[0,20] | Base case, return 0 | Not expanded |
| Exclude 3 → Include 2 | dp[1,10] | Compare total values of excluding and including | Exclude: dp[0,10]; Include: dp[0,0]+60 |
| Exclude 3 → Include 2 → Exclude 1 | dp[0,10] | Base case, return 0 | Not expanded |
| Exclude 3 → Include 2 → Include 1 | dp[0,0] | Base case, return 0 | Not expanded |
| Include 3 | dp[2,10] | Overweight, take only the exclude branch | Exclude: dp[1,10]; Include: dp[1,-10] (excluded) |
| Include 3 → Exclude 2 | dp[1,10] | Compare total values of excluding and including | Exclude: dp[0,10]; Include: dp[0,0]+60 |
| Include 3 → Exclude 2 → Exclude 1 | dp[0,10] | Base case, return 0 | Not expanded |
| Include 3 → Exclude 2 → Include 1 | dp[0,0] | Base case, return 0 | Not expanded |
| Include 3 → Include 2 | dp[1,-10] | Illustrative overweight branch; not actually called | Not expanded |
The figure contains 13 nodes in total, including 6 base-case leaf nodes that return 0 and 1 illustrative overweight node. From the input data, choosing item 1 and item 3 gives total weight 10 + 20 = 30 and maximum value 60 + 120 = 180; the value 180 is not written directly on the tree nodes.
2. Method 2: Memoized search¶
To solve each overlapping subproblem only once, use a memoization table mem, where mem[i][c] stores \(dp[i, c]\).
With memoization, the time complexity depends on the number of subproblems, giving \(O(n \times cap)\). The code is as follows:
def knapsack_dfs_mem(
wgt: list[int], val: list[int], mem: list[list[int]], i: int, c: int
) -> int:
"""0-1 knapsack: memoized search"""
# If all items have been considered or no capacity remains, return value 0
if i == 0 or c == 0:
return 0
# If a result has already been recorded, return it directly
if mem[i][c] != -1:
return mem[i][c]
# If the item exceeds the remaining capacity, it must be excluded
if wgt[i - 1] > c:
return knapsack_dfs_mem(wgt, val, mem, i - 1, c)
# Calculate the maximum values obtained by excluding and including item i
no = knapsack_dfs_mem(wgt, val, mem, i - 1, c)
yes = knapsack_dfs_mem(wgt, val, mem, i - 1, c - wgt[i - 1]) + val[i - 1]
# Record and return the larger value from the two choices
mem[i][c] = max(no, yes)
return mem[i][c]
/* 0-1 knapsack: memoized search */
int knapsackDFSMem(vector<int> &wgt, vector<int> &val, vector<vector<int>> &mem, int i, int c) {
// If all items have been considered or no capacity remains, return value 0
if (i == 0 || c == 0) {
return 0;
}
// If a result has already been recorded, return it directly
if (mem[i][c] != -1) {
return mem[i][c];
}
// If the item exceeds the remaining capacity, it must be excluded
if (wgt[i - 1] > c) {
return knapsackDFSMem(wgt, val, mem, i - 1, c);
}
// Calculate the maximum values obtained by excluding and including item i
int no = knapsackDFSMem(wgt, val, mem, i - 1, c);
int yes = knapsackDFSMem(wgt, val, mem, i - 1, c - wgt[i - 1]) + val[i - 1];
// Record and return the larger value from the two choices
mem[i][c] = max(no, yes);
return mem[i][c];
}
/* 0-1 knapsack: memoized search */
int knapsackDFSMem(int[] wgt, int[] val, int[][] mem, int i, int c) {
// If all items have been considered or no capacity remains, return value 0
if (i == 0 || c == 0) {
return 0;
}
// If a result has already been recorded, return it directly
if (mem[i][c] != -1) {
return mem[i][c];
}
// If the item exceeds the remaining capacity, it must be excluded
if (wgt[i - 1] > c) {
return knapsackDFSMem(wgt, val, mem, i - 1, c);
}
// Calculate the maximum values obtained by excluding and including item i
int no = knapsackDFSMem(wgt, val, mem, i - 1, c);
int yes = knapsackDFSMem(wgt, val, mem, i - 1, c - wgt[i - 1]) + val[i - 1];
// Record and return the larger value from the two choices
mem[i][c] = Math.max(no, yes);
return mem[i][c];
}
/* 0-1 knapsack: memoized search */
int KnapsackDFSMem(int[] weight, int[] val, int[][] mem, int i, int c) {
// If all items have been considered or no capacity remains, return value 0
if (i == 0 || c == 0) {
return 0;
}
// If a result has already been recorded, return it directly
if (mem[i][c] != -1) {
return mem[i][c];
}
// If the item exceeds the remaining capacity, it must be excluded
if (weight[i - 1] > c) {
return KnapsackDFSMem(weight, val, mem, i - 1, c);
}
// Calculate the maximum values obtained by excluding and including item i
int no = KnapsackDFSMem(weight, val, mem, i - 1, c);
int yes = KnapsackDFSMem(weight, val, mem, i - 1, c - weight[i - 1]) + val[i - 1];
// Record and return the larger value from the two choices
mem[i][c] = Math.Max(no, yes);
return mem[i][c];
}
/* 0-1 knapsack: memoized search */
func knapsackDFSMem(wgt, val []int, mem [][]int, i, c int) int {
// If all items have been considered or no capacity remains, return value 0
if i == 0 || c == 0 {
return 0
}
// If a result has already been recorded, return it directly
if mem[i][c] != -1 {
return mem[i][c]
}
// If the item exceeds the remaining capacity, it must be excluded
if wgt[i-1] > c {
return knapsackDFSMem(wgt, val, mem, i-1, c)
}
// Calculate the maximum values obtained by excluding and including item i
no := knapsackDFSMem(wgt, val, mem, i-1, c)
yes := knapsackDFSMem(wgt, val, mem, i-1, c-wgt[i-1]) + val[i-1]
// Return the larger value from the two choices
mem[i][c] = int(math.Max(float64(no), float64(yes)))
return mem[i][c]
}
/* 0-1 knapsack: memoized search */
func knapsackDFSMem(wgt: [Int], val: [Int], mem: inout [[Int]], i: Int, c: Int) -> Int {
// If all items have been considered or no capacity remains, return value 0
if i == 0 || c == 0 {
return 0
}
// If a result has already been recorded, return it directly
if mem[i][c] != -1 {
return mem[i][c]
}
// If the item exceeds the remaining capacity, it must be excluded
if wgt[i - 1] > c {
return knapsackDFSMem(wgt: wgt, val: val, mem: &mem, i: i - 1, c: c)
}
// Calculate the maximum values obtained by excluding and including item i
let no = knapsackDFSMem(wgt: wgt, val: val, mem: &mem, i: i - 1, c: c)
let yes = knapsackDFSMem(wgt: wgt, val: val, mem: &mem, i: i - 1, c: c - wgt[i - 1]) + val[i - 1]
// Record and return the larger value from the two choices
mem[i][c] = max(no, yes)
return mem[i][c]
}
/* 0-1 knapsack: memoized search */
function knapsackDFSMem(wgt, val, mem, i, c) {
// If all items have been considered or no capacity remains, return value 0
if (i === 0 || c === 0) {
return 0;
}
// If a result has already been recorded, return it directly
if (mem[i][c] !== -1) {
return mem[i][c];
}
// If the item exceeds the remaining capacity, it must be excluded
if (wgt[i - 1] > c) {
return knapsackDFSMem(wgt, val, mem, i - 1, c);
}
// Calculate the maximum values obtained by excluding and including item i
const no = knapsackDFSMem(wgt, val, mem, i - 1, c);
const yes =
knapsackDFSMem(wgt, val, mem, i - 1, c - wgt[i - 1]) + val[i - 1];
// Record and return the larger value from the two choices
mem[i][c] = Math.max(no, yes);
return mem[i][c];
}
/* 0-1 knapsack: memoized search */
function knapsackDFSMem(
wgt: Array<number>,
val: Array<number>,
mem: Array<Array<number>>,
i: number,
c: number
): number {
// If all items have been considered or no capacity remains, return value 0
if (i === 0 || c === 0) {
return 0;
}
// If a result has already been recorded, return it directly
if (mem[i][c] !== -1) {
return mem[i][c];
}
// If the item exceeds the remaining capacity, it must be excluded
if (wgt[i - 1] > c) {
return knapsackDFSMem(wgt, val, mem, i - 1, c);
}
// Calculate the maximum values obtained by excluding and including item i
const no = knapsackDFSMem(wgt, val, mem, i - 1, c);
const yes =
knapsackDFSMem(wgt, val, mem, i - 1, c - wgt[i - 1]) + val[i - 1];
// Record and return the larger value from the two choices
mem[i][c] = Math.max(no, yes);
return mem[i][c];
}
/* 0-1 knapsack: memoized search */
int knapsackDFSMem(
List<int> wgt,
List<int> val,
List<List<int>> mem,
int i,
int c,
) {
// If all items have been considered or no capacity remains, return value 0
if (i == 0 || c == 0) {
return 0;
}
// If a result has already been recorded, return it directly
if (mem[i][c] != -1) {
return mem[i][c];
}
// If the item exceeds the remaining capacity, it must be excluded
if (wgt[i - 1] > c) {
return knapsackDFSMem(wgt, val, mem, i - 1, c);
}
// Calculate the maximum values obtained by excluding and including item i
int no = knapsackDFSMem(wgt, val, mem, i - 1, c);
int yes = knapsackDFSMem(wgt, val, mem, i - 1, c - wgt[i - 1]) + val[i - 1];
// Record and return the larger value from the two choices
mem[i][c] = max(no, yes);
return mem[i][c];
}
/* 0-1 knapsack: memoized search */
fn knapsack_dfs_mem(wgt: &[i32], val: &[i32], mem: &mut Vec<Vec<i32>>, i: usize, c: usize) -> i32 {
// If all items have been considered or no capacity remains, return value 0
if i == 0 || c == 0 {
return 0;
}
// If a result has already been recorded, return it directly
if mem[i][c] != -1 {
return mem[i][c];
}
// If the item exceeds the remaining capacity, it must be excluded
if wgt[i - 1] > c as i32 {
return knapsack_dfs_mem(wgt, val, mem, i - 1, c);
}
// Calculate the maximum values obtained by excluding and including item i
let no = knapsack_dfs_mem(wgt, val, mem, i - 1, c);
let yes = knapsack_dfs_mem(wgt, val, mem, i - 1, c - wgt[i - 1] as usize) + val[i - 1];
// Record and return the larger value from the two choices
mem[i][c] = std::cmp::max(no, yes);
mem[i][c]
}
/* 0-1 knapsack: memoized search */
int knapsackDFSMem(int wgt[], int val[], int memCols, int **mem, int i, int c) {
// If all items have been considered or no capacity remains, return value 0
if (i == 0 || c == 0) {
return 0;
}
// If a result has already been recorded, return it directly
if (mem[i][c] != -1) {
return mem[i][c];
}
// If the item exceeds the remaining capacity, it must be excluded
if (wgt[i - 1] > c) {
return knapsackDFSMem(wgt, val, memCols, mem, i - 1, c);
}
// Calculate the maximum values obtained by excluding and including item i
int no = knapsackDFSMem(wgt, val, memCols, mem, i - 1, c);
int yes = knapsackDFSMem(wgt, val, memCols, mem, i - 1, c - wgt[i - 1]) + val[i - 1];
// Record and return the larger value from the two choices
mem[i][c] = myMax(no, yes);
return mem[i][c];
}
/* 0-1 knapsack: memoized search */
fun knapsackDFSMem(
wgt: IntArray,
_val: IntArray,
mem: Array<IntArray>,
i: Int,
c: Int
): Int {
// If all items have been considered or no capacity remains, return value 0
if (i == 0 || c == 0) {
return 0
}
// If a result has already been recorded, return it directly
if (mem[i][c] != -1) {
return mem[i][c]
}
// If the item exceeds the remaining capacity, it must be excluded
if (wgt[i - 1] > c) {
return knapsackDFSMem(wgt, _val, mem, i - 1, c)
}
// Calculate the maximum values obtained by excluding and including item i
val no = knapsackDFSMem(wgt, _val, mem, i - 1, c)
val yes = knapsackDFSMem(wgt, _val, mem, i - 1, c - wgt[i - 1]) + _val[i - 1]
// Record and return the larger value from the two choices
mem[i][c] = max(no, yes)
return mem[i][c]
}
### 0-1 knapsack: memoized search ###
def knapsack_dfs_mem(wgt, val, mem, i, c)
# If all items have been considered or no capacity remains, return value 0
return 0 if i == 0 || c == 0
# If a result has already been recorded, return it directly
return mem[i][c] if mem[i][c] != -1
# If the item exceeds the remaining capacity, it must be excluded
return knapsack_dfs_mem(wgt, val, mem, i - 1, c) if wgt[i - 1] > c
# Calculate the maximum values obtained by excluding and including item i
no = knapsack_dfs_mem(wgt, val, mem, i - 1, c)
yes = knapsack_dfs_mem(wgt, val, mem, i - 1, c - wgt[i - 1]) + val[i - 1]
# Record and return the larger value from the two choices
mem[i][c] = [no, yes].max
end
Visualize execution
Figure 14-19 shows the branches pruned by memoized search.
Figure 14-19 Memoized recursion tree for 0-1 knapsack
Description of Figure 14-19: Memoized search for 0-1 knapsack
When reaching dp[1, 10] again along the path that includes item 3, the search returns the cached result directly and skips the duplicate subtree; this differs in meaning from overweight pruning.
In 0-1 knapsack, each item may be chosen at most once. This figure uses the same dedicated 3-item example with capacity cap = 30 as the preceding figure: weights 10, 20, 20 and values 60, 110, 120 (see the table). State dp[i, c] denotes the maximum value obtainable from the first i items with available capacity c; the table header in the drawing writes wgt[i] and val[i] (with i from 1 to 3), whereas the code in the text indexes the arrays at i - 1.
When the current item fits, compare dp[i-1, c] (excluding it) with dp[i-1, c-wgt[i-1]] + val[i-1] (including it) and take the larger value; when it does not fit, take only the exclude branch. With no items left (i = 0) or remaining capacity 0 (c = 0), return 0.
Decisions proceed from the root dp[3, 30] for items 3, 2, and 1 in turn. Because item 2 (watermelon) and item 3 (pineapple) both weigh 20, either "exclude item 3, then include item 2" or "include item 3, then exclude item 2" leaves capacity 10 with only item 1 (apple, weight 10, value 60) remaining, so both paths converge on the same state dp[1, 10].
When the left subtree first visits dp[1, 10] (path "Exclude 3 → Include 2"), it expands to compare dp[0, 10] with dp[0, 0] + 60 and stores the result in the cache; when the right subtree under dp[2, 10] chooses to exclude item 2 and encounters dp[1, 10] again (path "Include 3 → Exclude 2"), it triggers "Prune: cached result found" and returns the cached value directly without expanding the two leaf nodes again. From item 1's weight 10 and value 60, that cached return value is 60—derived from the input table rather than written on the node.
Under the right child dp[2, 10], both branches carry scissors icons, yet they stop for completely different reasons: the left branch dp[1, 10] is a cache hit that directly returns the valid subproblem solution 60, whereas the right branch dp[1, -10] ("Prune: item weight > knapsack capacity") is an invalid illustrative node excluded because item 2's weight 20 exceeds the remaining capacity 10; the code checks for overweight before recursing and calls only the exclude branch dp[1, 10], never actually calling dp[1, -10].
The two tables below list the dedicated input items and the complete recursion tree shown in the figure; using the decision path from the root as the row header distinguishes multiple occurrences of the same state.
| Item ID | Illustrated item | Weight | Value |
|---|---|---|---|
| 1 | Apple | 10 | 60 |
| 2 | Watermelon | 20 | 110 |
| 3 | Pineapple | 20 | 120 |
| Decision path | State | Action or return | Child states and value gain |
|---|---|---|---|
| Root | dp[3,30] | Compare total values of excluding and including | Exclude: dp[2,30]; Include: dp[2,10]+120 |
| Exclude 3 | dp[2,30] | Compare total values of excluding and including | Exclude: dp[1,30]; Include: dp[1,10]+110 |
| Exclude 3 → Exclude 2 | dp[1,30] | Compare total values of excluding and including | Exclude: dp[0,30]; Include: dp[0,20]+60 |
| Exclude 3 → Exclude 2 → Exclude 1 | dp[0,30] | Base case, return 0 | Not expanded |
| Exclude 3 → Exclude 2 → Include 1 | dp[0,20] | Base case, return 0 | Not expanded |
| Exclude 3 → Include 2 | dp[1,10] | Compare total values of excluding and including | Exclude: dp[0,10]; Include: dp[0,0]+60 |
| Exclude 3 → Include 2 → Exclude 1 | dp[0,10] | Base case, return 0 | Not expanded |
| Exclude 3 → Include 2 → Include 1 | dp[0,0] | Base case, return 0 | Not expanded |
| Include 3 | dp[2,10] | Overweight, take only the exclude branch | Exclude: dp[1,10]; Include: dp[1,-10] (excluded) |
| Include 3 → Exclude 2 | dp[1,10] | Cache hit, return 60 (derived from input) | Not expanded |
| Include 3 → Include 2 | dp[1,-10] | Illustrative overweight branch; not actually called | Not expanded |
The figure contains 11 nodes in total, reducing the base-case leaf nodes from 6 in the brute-force tree to 4; the global maximum value remains 180 from choosing item 1 and item 3. Both the cached value 60 and the maximum value 180 are derived from the input data rather than printed on the tree nodes.
3. Method 3: Dynamic programming¶
Dynamic programming essentially fills the \(dp\) table using state transitions, as shown in the code below:
def knapsack_dp(wgt: list[int], val: list[int], cap: int) -> int:
"""0-1 knapsack: dynamic programming"""
n = len(wgt)
# Initialize the dp table
dp = [[0] * (cap + 1) for _ in range(n + 1)]
# State transitions
for i in range(1, n + 1):
for c in range(1, cap + 1):
if wgt[i - 1] > c:
# If item i exceeds the remaining capacity, do not choose it
dp[i][c] = dp[i - 1][c]
else:
# Take the larger value obtained by excluding and including item i
dp[i][c] = max(dp[i - 1][c], dp[i - 1][c - wgt[i - 1]] + val[i - 1])
return dp[n][cap]
/* 0-1 knapsack: dynamic programming */
int knapsackDP(vector<int> &wgt, vector<int> &val, int cap) {
int n = wgt.size();
// Initialize the dp table
vector<vector<int>> dp(n + 1, vector<int>(cap + 1, 0));
// State transitions
for (int i = 1; i <= n; i++) {
for (int c = 1; c <= cap; c++) {
if (wgt[i - 1] > c) {
// If item i exceeds the remaining capacity, do not choose it
dp[i][c] = dp[i - 1][c];
} else {
// Take the larger value obtained by excluding and including item i
dp[i][c] = max(dp[i - 1][c], dp[i - 1][c - wgt[i - 1]] + val[i - 1]);
}
}
}
return dp[n][cap];
}
/* 0-1 knapsack: dynamic programming */
int knapsackDP(int[] wgt, int[] val, int cap) {
int n = wgt.length;
// Initialize the dp table
int[][] dp = new int[n + 1][cap + 1];
// State transitions
for (int i = 1; i <= n; i++) {
for (int c = 1; c <= cap; c++) {
if (wgt[i - 1] > c) {
// If item i exceeds the remaining capacity, do not choose it
dp[i][c] = dp[i - 1][c];
} else {
// Take the larger value obtained by excluding and including item i
dp[i][c] = Math.max(dp[i - 1][c], dp[i - 1][c - wgt[i - 1]] + val[i - 1]);
}
}
}
return dp[n][cap];
}
/* 0-1 knapsack: dynamic programming */
int KnapsackDP(int[] weight, int[] val, int cap) {
int n = weight.Length;
// Initialize the dp table
int[,] dp = new int[n + 1, cap + 1];
// State transitions
for (int i = 1; i <= n; i++) {
for (int c = 1; c <= cap; c++) {
if (weight[i - 1] > c) {
// If item i exceeds the remaining capacity, do not choose it
dp[i, c] = dp[i - 1, c];
} else {
// Take the larger value obtained by excluding and including item i
dp[i, c] = Math.Max(dp[i - 1, c - weight[i - 1]] + val[i - 1], dp[i - 1, c]);
}
}
}
return dp[n, cap];
}
/* 0-1 knapsack: dynamic programming */
func knapsackDP(wgt, val []int, cap int) int {
n := len(wgt)
// Initialize the dp table
dp := make([][]int, n+1)
for i := 0; i <= n; i++ {
dp[i] = make([]int, cap+1)
}
// State transitions
for i := 1; i <= n; i++ {
for c := 1; c <= cap; c++ {
if wgt[i-1] > c {
// If item i exceeds the remaining capacity, do not choose it
dp[i][c] = dp[i-1][c]
} else {
// Take the larger value obtained by excluding and including item i
dp[i][c] = int(math.Max(float64(dp[i-1][c]), float64(dp[i-1][c-wgt[i-1]]+val[i-1])))
}
}
}
return dp[n][cap]
}
/* 0-1 knapsack: dynamic programming */
func knapsackDP(wgt: [Int], val: [Int], cap: Int) -> Int {
let n = wgt.count
// Initialize the dp table
var dp = Array(repeating: Array(repeating: 0, count: cap + 1), count: n + 1)
// State transitions
for i in 1 ... n {
for c in 1 ... cap {
if wgt[i - 1] > c {
// If item i exceeds the remaining capacity, do not choose it
dp[i][c] = dp[i - 1][c]
} else {
// Take the larger value obtained by excluding and including item i
dp[i][c] = max(dp[i - 1][c], dp[i - 1][c - wgt[i - 1]] + val[i - 1])
}
}
}
return dp[n][cap]
}
/* 0-1 knapsack: dynamic programming */
function knapsackDP(wgt, val, cap) {
const n = wgt.length;
// Initialize the dp table
const dp = Array(n + 1)
.fill(0)
.map(() => Array(cap + 1).fill(0));
// State transitions
for (let i = 1; i <= n; i++) {
for (let c = 1; c <= cap; c++) {
if (wgt[i - 1] > c) {
// If item i exceeds the remaining capacity, do not choose it
dp[i][c] = dp[i - 1][c];
} else {
// Take the larger value obtained by excluding and including item i
dp[i][c] = Math.max(
dp[i - 1][c],
dp[i - 1][c - wgt[i - 1]] + val[i - 1]
);
}
}
}
return dp[n][cap];
}
/* 0-1 knapsack: dynamic programming */
function knapsackDP(
wgt: Array<number>,
val: Array<number>,
cap: number
): number {
const n = wgt.length;
// Initialize the dp table
const dp = Array.from({ length: n + 1 }, () =>
Array.from({ length: cap + 1 }, () => 0)
);
// State transitions
for (let i = 1; i <= n; i++) {
for (let c = 1; c <= cap; c++) {
if (wgt[i - 1] > c) {
// If item i exceeds the remaining capacity, do not choose it
dp[i][c] = dp[i - 1][c];
} else {
// Take the larger value obtained by excluding and including item i
dp[i][c] = Math.max(
dp[i - 1][c],
dp[i - 1][c - wgt[i - 1]] + val[i - 1]
);
}
}
}
return dp[n][cap];
}
/* 0-1 knapsack: dynamic programming */
int knapsackDP(List<int> wgt, List<int> val, int cap) {
int n = wgt.length;
// Initialize the dp table
List<List<int>> dp = List.generate(n + 1, (index) => List.filled(cap + 1, 0));
// State transitions
for (int i = 1; i <= n; i++) {
for (int c = 1; c <= cap; c++) {
if (wgt[i - 1] > c) {
// If item i exceeds the remaining capacity, do not choose it
dp[i][c] = dp[i - 1][c];
} else {
// Take the larger value obtained by excluding and including item i
dp[i][c] = max(dp[i - 1][c], dp[i - 1][c - wgt[i - 1]] + val[i - 1]);
}
}
}
return dp[n][cap];
}
/* 0-1 knapsack: dynamic programming */
fn knapsack_dp(wgt: &[i32], val: &[i32], cap: usize) -> i32 {
let n = wgt.len();
// Initialize the dp table
let mut dp = vec![vec![0; cap + 1]; n + 1];
// State transitions
for i in 1..=n {
for c in 1..=cap {
if wgt[i - 1] > c as i32 {
// If item i exceeds the remaining capacity, do not choose it
dp[i][c] = dp[i - 1][c];
} else {
// Take the larger value obtained by excluding and including item i
dp[i][c] = std::cmp::max(
dp[i - 1][c],
dp[i - 1][c - wgt[i - 1] as usize] + val[i - 1],
);
}
}
}
dp[n][cap]
}
/* 0-1 knapsack: dynamic programming */
int knapsackDP(int wgt[], int val[], int cap, int wgtSize) {
int n = wgtSize;
// Initialize the dp table
int **dp = malloc((n + 1) * sizeof(int *));
for (int i = 0; i <= n; i++) {
dp[i] = calloc(cap + 1, sizeof(int));
}
// State transitions
for (int i = 1; i <= n; i++) {
for (int c = 1; c <= cap; c++) {
if (wgt[i - 1] > c) {
// If item i exceeds the remaining capacity, do not choose it
dp[i][c] = dp[i - 1][c];
} else {
// Take the larger value obtained by excluding and including item i
dp[i][c] = myMax(dp[i - 1][c], dp[i - 1][c - wgt[i - 1]] + val[i - 1]);
}
}
}
int res = dp[n][cap];
// Free memory
for (int i = 0; i <= n; i++) {
free(dp[i]);
}
return res;
}
/* 0-1 knapsack: dynamic programming */
fun knapsackDP(wgt: IntArray, _val: IntArray, cap: Int): Int {
val n = wgt.size
// Initialize the dp table
val dp = Array(n + 1) { IntArray(cap + 1) }
// State transitions
for (i in 1..n) {
for (c in 1..cap) {
if (wgt[i - 1] > c) {
// If item i exceeds the remaining capacity, do not choose it
dp[i][c] = dp[i - 1][c]
} else {
// Take the larger value obtained by excluding and including item i
dp[i][c] = max(dp[i - 1][c], dp[i - 1][c - wgt[i - 1]] + _val[i - 1])
}
}
}
return dp[n][cap]
}
### 0-1 knapsack: dynamic programming ###
def knapsack_dp(wgt, val, cap)
n = wgt.length
# Initialize the dp table
dp = Array.new(n + 1) { Array.new(cap + 1, 0) }
# State transitions
for i in 1...(n + 1)
for c in 1...(cap + 1)
if wgt[i - 1] > c
# If item i exceeds the remaining capacity, do not choose it
dp[i][c] = dp[i - 1][c]
else
# Take the larger value obtained by excluding and including item i
dp[i][c] = [dp[i - 1][c], dp[i - 1][c - wgt[i - 1]] + val[i - 1]].max
end
end
end
dp[n][cap]
end
Visualize execution
As shown in Figure 14-20, both time and space complexity are determined by the size of dp: \(O(n \times cap)\).
Figure 14-20 Dynamic programming for 0-1 knapsack
Description of Figure 14-20: Dynamic programming for 0-1 knapsack
With three items that may each be chosen at most once, this example steps cell by cell through the 0-1 knapsack recurrence and finds a maximum total value of 20 at capacity 4.
There are 3 candidate items (n = 3), whose IDs, names, weights, and values are given in the input table. With knapsack capacity cap = 4, the goal is to maximize total value without exceeding capacity; the knapsack need not be filled completely.
State dp[i, c] denotes the maximum value obtainable from the first i items with total weight at most capacity c. Row index i runs from 0 to 3 and column index c runs from 0 to 4, forming a 4-row by 5-column state table; item IDs i start at 1 and correspond to array weight wgt[i-1] and value val[i-1].
Step 1 initializes the table; steps 2 to 5, 6 to 9, and 10 to 13 compute rows 1, 2, and 3 across capacities c = 1 to 4; step 14 returns the answer. Each non-boundary cell is computed once and never modified afterward. Cells in the final table include the step number at which they are first computed: before that step, a cell holds the uncomputed initial value 0; from that step onward, it holds the final value shown in the table.
For item i, write w for its weight and v for its value. If w > c, the item does not fit and must be excluded, inheriting dp[i-1, c] directly above; otherwise compare dp[i-1, c] (excluding it) with dp[i-1, c-w] + v (including it), found in the previous row shifted w columns to the left. Both sources come from the previous row, which has not yet included item i, ensuring each item is chosen at most once.
| Item ID i | Item | Weight wgt[i - 1] | Value val[i - 1] |
|---|---|---|---|
| 1 | Apple | 1 | 5 |
| 2 | Pineapple | 2 | 11 |
| 3 | Watermelon | 3 | 15 |
Initialize the 4×5 state matrix
Create a 4-row by 5-column dp table filled initially with 0. Row 0 (no items) and column 0 (zero capacity) hold settled boundary values of 0, shown in dark text in the figure; the remaining 12 cells hold uncomputed initial values of 0, shown in faint text, and must not be read as computed optimal values.
Compute dp[1, 1], getting 5
Consider only the first item at capacity 1, where the current item is the apple (weight 1, value 5). Excluding it gives dp[0, 1] = 0 from the previous row; including it leaves capacity 1 - 1 = 0, looks up dp[0, 0] = 0 in the previous row (the first 0 items), and adds value 5 to get 5. Take the larger value 5 and write it to dp[1, 1]. Before this cell lie only the initialized boundary cells, and later non-boundary cells still hold uncomputed initial values of 0.
Compute dp[1, 2], getting 5
Consider only the first item at capacity 2, where the current item is the apple (weight 1, value 5). Excluding it gives dp[0, 2] = 0 from the previous row; including it leaves capacity 2 - 1 = 1, looks up dp[0, 1] = 0 in the previous row (the first 0 items), and adds value 5 to get 5. Take the larger value 5 and write it to dp[1, 2]. Earlier cells are already computed, and later non-boundary cells still hold uncomputed initial values of 0.
Compute dp[1, 3], getting 5
Consider only the first item at capacity 3, where the current item is the apple (weight 1, value 5). Excluding it gives dp[0, 3] = 0 from the previous row; including it leaves capacity 3 - 1 = 2, looks up dp[0, 2] = 0 in the previous row (the first 0 items), and adds value 5 to get 5. Take the larger value 5 and write it to dp[1, 3]. Earlier cells are already computed, and later non-boundary cells still hold uncomputed initial values of 0.
Compute dp[1, 4], getting 5
Consider only the first item at capacity 4, where the current item is the apple (weight 1, value 5). Excluding it gives dp[0, 4] = 0 from the previous row; including it leaves capacity 4 - 1 = 3, looks up dp[0, 3] = 0 in the previous row (the first 0 items), and adds value 5 to get 5. Take the larger value 5 and write it to dp[1, 4]. Earlier cells are already computed, and later non-boundary cells still hold uncomputed initial values of 0.
Compute dp[2, 1], getting 5
Consider the first 2 items at capacity 1, where the current item is the pineapple (weight 2, value 11). Since weight 2 exceeds capacity 1, it does not fit and must be excluded; inherit dp[1, 1] = 5 from the previous row and write dp[2, 1] = 5. Earlier cells are already computed, and later non-boundary cells still hold uncomputed initial values of 0.
Compute dp[2, 2], getting 11
Consider the first 2 items at capacity 2, where the current item is the pineapple (weight 2, value 11). Excluding it gives dp[1, 2] = 5 from the previous row; including it leaves capacity 2 - 2 = 0, looks up dp[1, 0] = 0 in the previous row (the first item only), and adds value 11 to get 11. Take the larger value 11 and write it to dp[2, 2]. Earlier cells are already computed, and later non-boundary cells still hold uncomputed initial values of 0.
Compute dp[2, 3], getting 16
Consider the first 2 items at capacity 3, where the current item is the pineapple (weight 2, value 11). Excluding it gives dp[1, 3] = 5 from the previous row; including it leaves capacity 3 - 2 = 1, looks up dp[1, 1] = 5 in the previous row (the first item only), and adds value 11 to get 16. Take the larger value 16 and write it to dp[2, 3]. Earlier cells are already computed, and later non-boundary cells still hold uncomputed initial values of 0.
Compute dp[2, 4], getting 16
Consider the first 2 items at capacity 4, where the current item is the pineapple (weight 2, value 11). Excluding it gives dp[1, 4] = 5 from the previous row; including it leaves capacity 4 - 2 = 2, looks up dp[1, 2] = 5 in the previous row (the first item only), and adds value 11 to get 16. Take the larger value 16 and write it to dp[2, 4]. Earlier cells are already computed, and later non-boundary cells still hold uncomputed initial values of 0.
Compute dp[3, 1], getting 5
Consider the first 3 items at capacity 1, where the current item is the watermelon (weight 3, value 15). Since weight 3 exceeds capacity 1, it does not fit and must be excluded; inherit dp[2, 1] = 5 from the previous row and write dp[3, 1] = 5. Earlier cells are already computed, and later non-boundary cells still hold uncomputed initial values of 0.
Compute dp[3, 2], getting 11
Consider the first 3 items at capacity 2, where the current item is the watermelon (weight 3, value 15). Since weight 3 exceeds capacity 2, it does not fit and must be excluded; inherit dp[2, 2] = 11 from the previous row and write dp[3, 2] = 11. Earlier cells are already computed, and later non-boundary cells still hold uncomputed initial values of 0.
Compute dp[3, 3], getting 16
Consider the first 3 items at capacity 3, where the current item is the watermelon (weight 3, value 15). Excluding it gives dp[2, 3] = 16 from the previous row; including it leaves capacity 3 - 3 = 0, looks up dp[2, 0] = 0 in the previous row (the first 2 items), and adds value 15 to get 15. Take the larger value 16 and write it to dp[3, 3]. Earlier cells are already computed, and later non-boundary cells still hold uncomputed initial values of 0.
Compute dp[3, 4], getting 20
Consider the first 3 items at capacity 4, where the current item is the watermelon (weight 3, value 15). Excluding it gives dp[2, 4] = 16 from the previous row; including it leaves capacity 4 - 3 = 1, looks up dp[2, 1] = 5 in the previous row (the first 2 items), and adds value 15 to get 20. Take the larger value 20 and write it to dp[3, 4]. All 12 non-boundary cells have now been computed.
Return maximum value 20 for capacity 4
Read bottom-right dp[3, 4] = 20, choosing the apple and the watermelon: total weight 1 + 3 = 4, total value 5 + 15 = 20. The final frame's note "Return the maximum achievable knapsack value after considering all items: 20" means the optimal subset chosen from all three candidate items; packing all three would weigh 6, exceeding capacity 4.
| Available items (first i) | Capacity c=0 | Capacity c=1 | Capacity c=2 | Capacity c=3 | Capacity c=4 |
|---|---|---|---|---|---|
| No items (i=0) | 0 (valid boundary) | 0 (valid boundary) | 0 (valid boundary) | 0 (valid boundary) | 0 (valid boundary) |
| Apple (i=1) | 0 (valid boundary) | 5 (step 2) | 5 (step 3) | 5 (step 4) | 5 (step 5) |
| Apple, pineapple (i=2) | 0 (valid boundary) | 5 (step 6) | 11 (step 7) | 16 (step 8) | 16 (step 9) |
| Apple, pineapple, watermelon (i=3) | 0 (valid boundary) | 5 (step 10) | 11 (step 11) | 16 (step 12) | 20 (step 13) |
4. Space optimization¶
Each state depends only on the previous row, so two rolling arrays reduce space complexity from \(O(n \times cap)\) to \(O(cap)\).
Can we go further and use just one array? Each state depends on entries directly above or to the upper left. With one array, when we begin processing row \(i\), it still holds the states from row \(i-1\).
- With forward iteration, by the time we reach \(dp[i, j]\), the upper-left values \(dp[i-1, 1]\) ~ \(dp[i-1, j-1]\) may have been overwritten, making the transition incorrect.
- With backward iteration, these values are not overwritten before they are needed, so transitions remain correct.
Figure 14-21 shows one array changing from row \(i = 1\) to row \(i = 2\). Consider how forward and backward iteration differ.
Figure 14-21 Space-optimized dynamic programming for 0-1 knapsack
Description of Figure 14-21: Single-row space optimization for 0-1 knapsack
Store states in a single one-dimensional array and update capacities in reverse order from high to low so transitions read old values from the previous item's round rather than reusing the same item.
There are three items—item 1 apple (weight 1, value 5), item 2 pineapple (weight 2, value 11), and item 3 watermelon (weight 3, value 15)—with maximum knapsack capacity 4, and each item may be chosen at most once. Item IDs i start at 1. The weight and value of item i are stored in wgt[i - 1] and val[i - 1].
The 6 steps demonstrate only the reverse-order update round for outer loop i = 2 (item 2, pineapple). Before this round begins, the one-dimensional array dp[0..4] holds the results [0, 5, 5, 5, 5] for item 1 alone (apple, i = 1); item 3 (watermelon, i = 3) remains unprocessed throughout this figure. Entry dp[c] gives the maximum value within capacity c using items considered so far without requiring the knapsack to be completely full.
When processing the pineapple (weight 2, value 11) at capacity c ≥ 2, compare excluding the pineapple (keeping previous-round value dp[c]) with including it (reading previous-round smaller-capacity value dp[c - 2] + 11), writing the larger value back to dp[c]. Traversing capacities c = 4, 3, 2, 1 in reverse order guarantees that dp[c - 2] to the left has not yet been overwritten in this round and still holds its old state from round i = 1 (apple only).
Conversely, updating capacities in forward order from low to high would first update capacity 2 to dp[2] = 11 (already packing one pineapple); evaluating capacity 4 afterward would read dp[2] + 11 = 22, packing the same pineapple twice inside capacity 4 and violating the at-most-once rule of 0-1 knapsack. Reverse-order updates evaluate capacity 4 while dp[2] still holds its old value 5, yielding the correct 5 + 11 = 16.
Each frame shows the 4×5 two-dimensional reference table above and the active single-row array dp[0..4] below. In the single row, blue cells indicate retained old states from the previous round (i = 1) and green cells indicate states already updated in the current round (i = 2); at the end of the round, the entire row turns blue to serve as the old states for processing the watermelon next, with no further numeric changes.
At each step, the single-row table has separate columns for each capacity's value and the round it represents: i = 1 considers only the apple, i = 2 considers the apple and pineapple, and capacity 0 is always boundary 0. Each step also includes the full two-dimensional reference table, where rows for the first 0, first 1, and first 3 items stay unchanged and zeros at capacities 1 to 4 in row 3 remain uncomputed initial values. Both table captions include the step number for direct lookup by step, capacity, and available items.
| Item ID i | Item | Weight wgt[i - 1] | Value val[i - 1] |
|---|---|---|---|
| 1 | Apple | 1 | 5 |
| 2 | Pineapple | 2 | 11 |
| 3 | Watermelon | 3 | 15 |
Begin processing the pineapple
Before round i = 2 (pineapple, weight 2, value 11) starts, single-row dp[0..4] already holds the valid round i = 1 results [0, 5, 5, 5, 5] (apple only) rather than an all-zero table. Capacity 0 is fixed boundary 0, and capacities 1 through 4 hold old round i = 1 states ready for reverse-order updates starting at maximum capacity c = 4.
Knapsack space optimization step 1 (begin processing pineapple): single-row dp values and rounds Capacity c Current value Round and status 0 0 Boundary shared across rounds 1 5 i = 1, previous round, not yet overwritten 2 5 i = 1, previous round, not yet overwritten 3 5 i = 1, previous round, not yet overwritten 4 5 i = 1, previous round, not yet overwritten Knapsack space optimization step 1 (begin processing pineapple): full two-dimensional reference table Available items Capacity 0 Capacity 1 Capacity 2 Capacity 3 Capacity 4 First 0 items 0, valid boundary 0, valid boundary 0, valid boundary 0, valid boundary 0, valid boundary First item only 0, valid boundary 5, computed 5, computed 5, computed 5, computed First 2 items 0, valid boundary 0, uncomputed initial value 0, uncomputed initial value 0, uncomputed initial value 0, uncomputed initial value First 3 items 0, valid boundary 0, uncomputed initial value 0, uncomputed initial value 0, uncomputed initial value 0, uncomputed initial value Update capacity 4 in reverse order
Process maximum capacity c = 4 first: excluding the pineapple keeps old value dp[4] = 5; including it reads previous-round old value dp[4 - 2] = dp[2] = 5 (not yet overwritten in this round) plus pineapple value 11 to get 16. Take the larger value to update dp[4] to 16 (round i = 2), while capacities 1, 2, and 3 retain old value 5 from round i = 1. Current single-row dp = [0, 5, 5, 5, 16].
Knapsack space optimization step 2 (update capacity 4 in reverse): single-row dp values and rounds Capacity c Current value Round and status 0 0 Boundary shared across rounds 1 5 i = 1, previous round, not yet overwritten 2 5 i = 1, previous round, not yet overwritten 3 5 i = 1, previous round, not yet overwritten 4 16 i = 2, processed in this round Knapsack space optimization step 2 (update capacity 4 in reverse): full two-dimensional reference table Available items Capacity 0 Capacity 1 Capacity 2 Capacity 3 Capacity 4 First 0 items 0, valid boundary 0, valid boundary 0, valid boundary 0, valid boundary 0, valid boundary First item only 0, valid boundary 5, computed 5, computed 5, computed 5, computed First 2 items 0, valid boundary 0, uncomputed initial value 0, uncomputed initial value 0, uncomputed initial value 16, computed First 3 items 0, valid boundary 0, uncomputed initial value 0, uncomputed initial value 0, uncomputed initial value 0, uncomputed initial value Update capacity 3 in reverse order
Continue in reverse to capacity c = 3: excluding the pineapple keeps old value dp[3] = 5; including it reads old value dp[3 - 2] = dp[1] = 5 from round i = 1 plus 11 to get 16. Update dp[3] to 16 (round i = 2), while capacities 1 and 2 keep old state 5 from round i = 1. Current single-row dp = [0, 5, 5, 16, 16].
Knapsack space optimization step 3 (update capacity 3 in reverse): single-row dp values and rounds Capacity c Current value Round and status 0 0 Boundary shared across rounds 1 5 i = 1, previous round, not yet overwritten 2 5 i = 1, previous round, not yet overwritten 3 16 i = 2, processed in this round 4 16 i = 2, processed in this round Knapsack space optimization step 3 (update capacity 3 in reverse): full two-dimensional reference table Available items Capacity 0 Capacity 1 Capacity 2 Capacity 3 Capacity 4 First 0 items 0, valid boundary 0, valid boundary 0, valid boundary 0, valid boundary 0, valid boundary First item only 0, valid boundary 5, computed 5, computed 5, computed 5, computed First 2 items 0, valid boundary 0, uncomputed initial value 0, uncomputed initial value 16, computed 16, computed First 3 items 0, valid boundary 0, uncomputed initial value 0, uncomputed initial value 0, uncomputed initial value 0, uncomputed initial value Update capacity 2 in reverse order
Continue in reverse to capacity c = 2: excluding the pineapple keeps old value dp[2] = 5; including it reads boundary dp[2 - 2] = dp[0] = 0 plus 11 to get 11. Update dp[2] to 11 (round i = 2). Because reverse order overwrites dp[2] only now, capacity 4 earlier was able to read the unoverwritten old value dp[2] = 5; only capacity 1 still belongs to round i = 1. Current single-row dp = [0, 5, 11, 16, 16].
Knapsack space optimization step 4 (update capacity 2 in reverse): single-row dp values and rounds Capacity c Current value Round and status 0 0 Boundary shared across rounds 1 5 i = 1, previous round, not yet overwritten 2 11 i = 2, processed in this round 3 16 i = 2, processed in this round 4 16 i = 2, processed in this round Knapsack space optimization step 4 (update capacity 2 in reverse): full two-dimensional reference table Available items Capacity 0 Capacity 1 Capacity 2 Capacity 3 Capacity 4 First 0 items 0, valid boundary 0, valid boundary 0, valid boundary 0, valid boundary 0, valid boundary First item only 0, valid boundary 5, computed 5, computed 5, computed 5, computed First 2 items 0, valid boundary 0, uncomputed initial value 11, computed 16, computed 16, computed First 3 items 0, valid boundary 0, uncomputed initial value 0, uncomputed initial value 0, uncomputed initial value 0, uncomputed initial value Process capacity 1 where the pineapple does not fit
Finally process capacity c = 1: because the pineapple weighs 2, exceeding capacity 1, it cannot fit, so the algorithm retains the previous-round value dp[1] = 5. Although dp[1] keeps numeric value 5, capacity 1 has now completed its round 2 (i = 2) check and represents round i = 2 rather than i = 1 (an unchanged number does not mean an unchanged round). Current single-row dp = [0, 5, 11, 16, 16].
Knapsack space optimization step 5 (process capacity 1 where pineapple cannot fit): single-row dp values and rounds Capacity c Current value Round and status 0 0 Boundary shared across rounds 1 5 i = 2, processed in this round 2 11 i = 2, processed in this round 3 16 i = 2, processed in this round 4 16 i = 2, processed in this round Knapsack space optimization step 5 (process capacity 1 where pineapple cannot fit): full two-dimensional reference table Available items Capacity 0 Capacity 1 Capacity 2 Capacity 3 Capacity 4 First 0 items 0, valid boundary 0, valid boundary 0, valid boundary 0, valid boundary 0, valid boundary First item only 0, valid boundary 5, computed 5, computed 5, computed 5, computed First 2 items 0, valid boundary 5, computed 11, computed 16, computed 16, computed First 3 items 0, valid boundary 0, uncomputed initial value 0, uncomputed initial value 0, uncomputed initial value 0, uncomputed initial value Finish the round and prepare for the next round
All capacities in round 2 (i = 2, pineapple) have been updated, and single-row dp[0..4] = [0, 5, 11, 16, 16] holds all solutions for the first two items. Performing no new calculation, this frame recolors capacities 1 through 4 from green to blue so the entire row is uniformly blue, indicating these round i = 2 results will serve as the old states when round i = 3 processes item 3 (watermelon), which has not yet started.
Knapsack space optimization step 6 (round complete, ready for next round): single-row dp values and rounds Capacity c Current value Round and status 0 0 Boundary shared across rounds 1 5 i = 2, processed in this round; serves as old state for next round 2 11 i = 2, processed in this round; serves as old state for next round 3 16 i = 2, processed in this round; serves as old state for next round 4 16 i = 2, processed in this round; serves as old state for next round Knapsack space optimization step 6 (round complete, ready for next round): full two-dimensional reference table Available items Capacity 0 Capacity 1 Capacity 2 Capacity 3 Capacity 4 First 0 items 0, valid boundary 0, valid boundary 0, valid boundary 0, valid boundary 0, valid boundary First item only 0, valid boundary 5, computed 5, computed 5, computed 5, computed First 2 items 0, valid boundary 5, computed 11, computed 16, computed 16, computed First 3 items 0, valid boundary 0, uncomputed initial value 0, uncomputed initial value 0, uncomputed initial value 0, uncomputed initial value
After round 2 (i = 2, pineapple) finishes updating in reverse order, the single-row array is dp = [0, 5, 11, 16, 16], where dp[4] = 16 is only the intermediate maximum value at capacity 4 for the first two items (apple and pineapple); item 3 (watermelon, weight 3, value 15) has not yet been processed, so 16 must not be mistaken for the three-item final answer 20. Derived from the input, choosing the apple and watermelon gives weight 1 + 3 = 4 and value 5 + 15 = 20, which is not drawn in this figure.
In the implementation, simply remove the first dimension \(i\) from dp and reverse the inner loop:
def knapsack_dp_comp(wgt: list[int], val: list[int], cap: int) -> int:
"""0-1 knapsack: space-optimized dynamic programming"""
n = len(wgt)
# Initialize the dp table
dp = [0] * (cap + 1)
# State transitions
for i in range(1, n + 1):
# Traverse in decreasing order
for c in range(cap, 0, -1):
if wgt[i - 1] > c:
# If item i exceeds the remaining capacity, do not choose it
dp[c] = dp[c]
else:
# Take the larger value obtained by excluding and including item i
dp[c] = max(dp[c], dp[c - wgt[i - 1]] + val[i - 1])
return dp[cap]
/* 0-1 knapsack: space-optimized dynamic programming */
int knapsackDPComp(vector<int> &wgt, vector<int> &val, int cap) {
int n = wgt.size();
// Initialize the dp table
vector<int> dp(cap + 1, 0);
// State transitions
for (int i = 1; i <= n; i++) {
// Traverse in decreasing order
for (int c = cap; c >= 1; c--) {
if (wgt[i - 1] <= c) {
// Take the larger value obtained by excluding and including item i
dp[c] = max(dp[c], dp[c - wgt[i - 1]] + val[i - 1]);
}
}
}
return dp[cap];
}
/* 0-1 knapsack: space-optimized dynamic programming */
int knapsackDPComp(int[] wgt, int[] val, int cap) {
int n = wgt.length;
// Initialize the dp table
int[] dp = new int[cap + 1];
// State transitions
for (int i = 1; i <= n; i++) {
// Traverse in decreasing order
for (int c = cap; c >= 1; c--) {
if (wgt[i - 1] <= c) {
// Take the larger value obtained by excluding and including item i
dp[c] = Math.max(dp[c], dp[c - wgt[i - 1]] + val[i - 1]);
}
}
}
return dp[cap];
}
/* 0-1 knapsack: space-optimized dynamic programming */
int KnapsackDPComp(int[] weight, int[] val, int cap) {
int n = weight.Length;
// Initialize the dp table
int[] dp = new int[cap + 1];
// State transitions
for (int i = 1; i <= n; i++) {
// Traverse in decreasing order
for (int c = cap; c > 0; c--) {
if (weight[i - 1] > c) {
// If item i exceeds the remaining capacity, do not choose it
dp[c] = dp[c];
} else {
// Take the larger value obtained by excluding and including item i
dp[c] = Math.Max(dp[c], dp[c - weight[i - 1]] + val[i - 1]);
}
}
}
return dp[cap];
}
/* 0-1 knapsack: space-optimized dynamic programming */
func knapsackDPComp(wgt, val []int, cap int) int {
n := len(wgt)
// Initialize the dp table
dp := make([]int, cap+1)
// State transitions
for i := 1; i <= n; i++ {
// Traverse in decreasing order
for c := cap; c >= 1; c-- {
if wgt[i-1] <= c {
// Take the larger value obtained by excluding and including item i
dp[c] = int(math.Max(float64(dp[c]), float64(dp[c-wgt[i-1]]+val[i-1])))
}
}
}
return dp[cap]
}
/* 0-1 knapsack: space-optimized dynamic programming */
func knapsackDPComp(wgt: [Int], val: [Int], cap: Int) -> Int {
let n = wgt.count
// Initialize the dp table
var dp = Array(repeating: 0, count: cap + 1)
// State transitions
for i in 1 ... n {
// Traverse in decreasing order
for c in (1 ... cap).reversed() {
if wgt[i - 1] <= c {
// Take the larger value obtained by excluding and including item i
dp[c] = max(dp[c], dp[c - wgt[i - 1]] + val[i - 1])
}
}
}
return dp[cap]
}
/* 0-1 knapsack: space-optimized dynamic programming */
function knapsackDPComp(wgt, val, cap) {
const n = wgt.length;
// Initialize the dp table
const dp = Array(cap + 1).fill(0);
// State transitions
for (let i = 1; i <= n; i++) {
// Traverse in decreasing order
for (let c = cap; c >= 1; c--) {
if (wgt[i - 1] <= c) {
// Take the larger value obtained by excluding and including item i
dp[c] = Math.max(dp[c], dp[c - wgt[i - 1]] + val[i - 1]);
}
}
}
return dp[cap];
}
/* 0-1 knapsack: space-optimized dynamic programming */
function knapsackDPComp(
wgt: Array<number>,
val: Array<number>,
cap: number
): number {
const n = wgt.length;
// Initialize the dp table
const dp = Array(cap + 1).fill(0);
// State transitions
for (let i = 1; i <= n; i++) {
// Traverse in decreasing order
for (let c = cap; c >= 1; c--) {
if (wgt[i - 1] <= c) {
// Take the larger value obtained by excluding and including item i
dp[c] = Math.max(dp[c], dp[c - wgt[i - 1]] + val[i - 1]);
}
}
}
return dp[cap];
}
/* 0-1 knapsack: space-optimized dynamic programming */
int knapsackDPComp(List<int> wgt, List<int> val, int cap) {
int n = wgt.length;
// Initialize the dp table
List<int> dp = List.filled(cap + 1, 0);
// State transitions
for (int i = 1; i <= n; i++) {
// Traverse in decreasing order
for (int c = cap; c >= 1; c--) {
if (wgt[i - 1] <= c) {
// Take the larger value obtained by excluding and including item i
dp[c] = max(dp[c], dp[c - wgt[i - 1]] + val[i - 1]);
}
}
}
return dp[cap];
}
/* 0-1 knapsack: space-optimized dynamic programming */
fn knapsack_dp_comp(wgt: &[i32], val: &[i32], cap: usize) -> i32 {
let n = wgt.len();
// Initialize the dp table
let mut dp = vec![0; cap + 1];
// State transitions
for i in 1..=n {
// Traverse in decreasing order
for c in (1..=cap).rev() {
if wgt[i - 1] <= c as i32 {
// Take the larger value obtained by excluding and including item i
dp[c] = std::cmp::max(dp[c], dp[c - wgt[i - 1] as usize] + val[i - 1]);
}
}
}
dp[cap]
}
/* 0-1 knapsack: space-optimized dynamic programming */
int knapsackDPComp(int wgt[], int val[], int cap, int wgtSize) {
int n = wgtSize;
// Initialize the dp table
int *dp = calloc(cap + 1, sizeof(int));
// State transitions
for (int i = 1; i <= n; i++) {
// Traverse in decreasing order
for (int c = cap; c >= 1; c--) {
if (wgt[i - 1] <= c) {
// Take the larger value obtained by excluding and including item i
dp[c] = myMax(dp[c], dp[c - wgt[i - 1]] + val[i - 1]);
}
}
}
int res = dp[cap];
// Free memory
free(dp);
return res;
}
/* 0-1 knapsack: space-optimized dynamic programming */
fun knapsackDPComp(wgt: IntArray, _val: IntArray, cap: Int): Int {
val n = wgt.size
// Initialize the dp table
val dp = IntArray(cap + 1)
// State transitions
for (i in 1..n) {
// Traverse in decreasing order
for (c in cap downTo 1) {
if (wgt[i - 1] <= c) {
// Take the larger value obtained by excluding and including item i
dp[c] = max(dp[c], dp[c - wgt[i - 1]] + _val[i - 1])
}
}
}
return dp[cap]
}
### 0-1 knapsack: space-optimized dynamic programming ###
def knapsack_dp_comp(wgt, val, cap)
n = wgt.length
# Initialize the dp table
dp = Array.new(cap + 1, 0)
# State transitions
for i in 1...(n + 1)
# Traverse in decreasing order
for c in cap.downto(1)
if wgt[i - 1] > c
# If item i exceeds the remaining capacity, do not choose it
dp[c] = dp[c]
else
# Take the larger value obtained by excluding and including item i
dp[c] = [dp[c], dp[c - wgt[i - 1]] + val[i - 1]].max
end
end
end
dp[cap]
end