Skip to content

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".

Five items for capacity 50; IDs start at 1
IDIllustrated itemWeightValueIncluded in optimal choice?
1Apple1050No
2Banana20120Yes
3Grapes30150Yes
4Pineapple40210No
5Watermelon50240No

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:

\[ dp[i, c] = \max(dp[i-1, c], dp[i-1, c - wgt[i-1]] + val[i-1]) \]

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.

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.
knapsack.py
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)
knapsack.cpp
/* 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);
}
knapsack.java
/* 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);
}
knapsack.cs
/* 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);
}
knapsack.go
/* 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)))
}
knapsack.swift
/* 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)
}
knapsack.js
/* 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);
}
knapsack.ts
/* 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);
}
knapsack.dart
/* 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);
}
knapsack.rs
/* 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)
}
knapsack.c
/* 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);
}
knapsack.kt
/* 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)
}
knapsack.rb
### 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.

Three items used in the recursion tree; capacity 30
Item IDIllustrated itemWeightValue
1Apple1060
2Watermelon20110
3Pineapple20120
Complete recursion tree; paths start at the root and include the excluded negative-capacity node
Decision pathStateAction or returnChild states and value gain
Rootdp[3,30]Compare total values of excluding and includingExclude: dp[2,30]; Include: dp[2,10]+120
Exclude 3dp[2,30]Compare total values of excluding and includingExclude: dp[1,30]; Include: dp[1,10]+110
Exclude 3 → Exclude 2dp[1,30]Compare total values of excluding and includingExclude: dp[0,30]; Include: dp[0,20]+60
Exclude 3 → Exclude 2 → Exclude 1dp[0,30]Base case, return 0Not expanded
Exclude 3 → Exclude 2 → Include 1dp[0,20]Base case, return 0Not expanded
Exclude 3 → Include 2dp[1,10]Compare total values of excluding and includingExclude: dp[0,10]; Include: dp[0,0]+60
Exclude 3 → Include 2 → Exclude 1dp[0,10]Base case, return 0Not expanded
Exclude 3 → Include 2 → Include 1dp[0,0]Base case, return 0Not expanded
Include 3dp[2,10]Overweight, take only the exclude branchExclude: dp[1,10]; Include: dp[1,-10] (excluded)
Include 3 → Exclude 2dp[1,10]Compare total values of excluding and includingExclude: dp[0,10]; Include: dp[0,0]+60
Include 3 → Exclude 2 → Exclude 1dp[0,10]Base case, return 0Not expanded
Include 3 → Exclude 2 → Include 1dp[0,0]Base case, return 0Not expanded
Include 3 → Include 2dp[1,-10]Illustrative overweight branch; not actually calledNot 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.

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:

knapsack.py
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]
knapsack.cpp
/* 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];
}
knapsack.java
/* 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];
}
knapsack.cs
/* 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];
}
knapsack.go
/* 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]
}
knapsack.swift
/* 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]
}
knapsack.js
/* 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];
}
knapsack.ts
/* 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];
}
knapsack.dart
/* 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];
}
knapsack.rs
/* 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]
}
knapsack.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];
}
knapsack.kt
/* 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]
}
knapsack.rb
### 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.

Three items used in the recursion tree; capacity 30
Item IDIllustrated itemWeightValue
1Apple1060
2Watermelon20110
3Pineapple20120
Complete recursion tree; paths start at the root and include the excluded negative-capacity node
Decision pathStateAction or returnChild states and value gain
Rootdp[3,30]Compare total values of excluding and includingExclude: dp[2,30]; Include: dp[2,10]+120
Exclude 3dp[2,30]Compare total values of excluding and includingExclude: dp[1,30]; Include: dp[1,10]+110
Exclude 3 → Exclude 2dp[1,30]Compare total values of excluding and includingExclude: dp[0,30]; Include: dp[0,20]+60
Exclude 3 → Exclude 2 → Exclude 1dp[0,30]Base case, return 0Not expanded
Exclude 3 → Exclude 2 → Include 1dp[0,20]Base case, return 0Not expanded
Exclude 3 → Include 2dp[1,10]Compare total values of excluding and includingExclude: dp[0,10]; Include: dp[0,0]+60
Exclude 3 → Include 2 → Exclude 1dp[0,10]Base case, return 0Not expanded
Exclude 3 → Include 2 → Include 1dp[0,0]Base case, return 0Not expanded
Include 3dp[2,10]Overweight, take only the exclude branchExclude: dp[1,10]; Include: dp[1,-10] (excluded)
Include 3 → Exclude 2dp[1,10]Cache hit, return 60 (derived from input)Not expanded
Include 3 → Include 2dp[1,-10]Illustrative overweight branch; not actually calledNot 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:

knapsack.py
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]
knapsack.cpp
/* 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];
}
knapsack.java
/* 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];
}
knapsack.cs
/* 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];
}
knapsack.go
/* 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]
}
knapsack.swift
/* 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]
}
knapsack.js
/* 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];
}
knapsack.ts
/* 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];
}
knapsack.dart
/* 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];
}
knapsack.rs
/* 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]
}
knapsack.c
/* 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;
}
knapsack.kt
/* 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]
}
knapsack.rb
### 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 input data for this figure
Item ID iItemWeight wgt[i - 1]Value val[i - 1]
1Apple15
2Pineapple211
3Watermelon315
  1. 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.

  2. 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.

  3. 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.

  4. 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.

  5. 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.

  6. 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.

  7. 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.

  8. 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.

  9. 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.

  10. 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.

  11. 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.

  12. 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.

  13. 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.

  14. 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.

Completed dp maximum values and first-computed steps
Available items (first i)Capacity c=0Capacity c=1Capacity c=2Capacity c=3Capacity 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.

Single-row optimization example: three items with capacity 4
Item ID iItemWeight wgt[i - 1]Value val[i - 1]
1Apple15
2Pineapple211
3Watermelon315
  1. 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 cCurrent valueRound and status
    00Boundary shared across rounds
    15i = 1, previous round, not yet overwritten
    25i = 1, previous round, not yet overwritten
    35i = 1, previous round, not yet overwritten
    45i = 1, previous round, not yet overwritten
    Knapsack space optimization step 1 (begin processing pineapple): full two-dimensional reference table
    Available itemsCapacity 0Capacity 1Capacity 2Capacity 3Capacity 4
    First 0 items0, valid boundary0, valid boundary0, valid boundary0, valid boundary0, valid boundary
    First item only0, valid boundary5, computed5, computed5, computed5, computed
    First 2 items0, valid boundary0, uncomputed initial value0, uncomputed initial value0, uncomputed initial value0, uncomputed initial value
    First 3 items0, valid boundary0, uncomputed initial value0, uncomputed initial value0, uncomputed initial value0, uncomputed initial value
  2. 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 cCurrent valueRound and status
    00Boundary shared across rounds
    15i = 1, previous round, not yet overwritten
    25i = 1, previous round, not yet overwritten
    35i = 1, previous round, not yet overwritten
    416i = 2, processed in this round
    Knapsack space optimization step 2 (update capacity 4 in reverse): full two-dimensional reference table
    Available itemsCapacity 0Capacity 1Capacity 2Capacity 3Capacity 4
    First 0 items0, valid boundary0, valid boundary0, valid boundary0, valid boundary0, valid boundary
    First item only0, valid boundary5, computed5, computed5, computed5, computed
    First 2 items0, valid boundary0, uncomputed initial value0, uncomputed initial value0, uncomputed initial value16, computed
    First 3 items0, valid boundary0, uncomputed initial value0, uncomputed initial value0, uncomputed initial value0, uncomputed initial value
  3. 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 cCurrent valueRound and status
    00Boundary shared across rounds
    15i = 1, previous round, not yet overwritten
    25i = 1, previous round, not yet overwritten
    316i = 2, processed in this round
    416i = 2, processed in this round
    Knapsack space optimization step 3 (update capacity 3 in reverse): full two-dimensional reference table
    Available itemsCapacity 0Capacity 1Capacity 2Capacity 3Capacity 4
    First 0 items0, valid boundary0, valid boundary0, valid boundary0, valid boundary0, valid boundary
    First item only0, valid boundary5, computed5, computed5, computed5, computed
    First 2 items0, valid boundary0, uncomputed initial value0, uncomputed initial value16, computed16, computed
    First 3 items0, valid boundary0, uncomputed initial value0, uncomputed initial value0, uncomputed initial value0, uncomputed initial value
  4. 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 cCurrent valueRound and status
    00Boundary shared across rounds
    15i = 1, previous round, not yet overwritten
    211i = 2, processed in this round
    316i = 2, processed in this round
    416i = 2, processed in this round
    Knapsack space optimization step 4 (update capacity 2 in reverse): full two-dimensional reference table
    Available itemsCapacity 0Capacity 1Capacity 2Capacity 3Capacity 4
    First 0 items0, valid boundary0, valid boundary0, valid boundary0, valid boundary0, valid boundary
    First item only0, valid boundary5, computed5, computed5, computed5, computed
    First 2 items0, valid boundary0, uncomputed initial value11, computed16, computed16, computed
    First 3 items0, valid boundary0, uncomputed initial value0, uncomputed initial value0, uncomputed initial value0, uncomputed initial value
  5. 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 cCurrent valueRound and status
    00Boundary shared across rounds
    15i = 2, processed in this round
    211i = 2, processed in this round
    316i = 2, processed in this round
    416i = 2, processed in this round
    Knapsack space optimization step 5 (process capacity 1 where pineapple cannot fit): full two-dimensional reference table
    Available itemsCapacity 0Capacity 1Capacity 2Capacity 3Capacity 4
    First 0 items0, valid boundary0, valid boundary0, valid boundary0, valid boundary0, valid boundary
    First item only0, valid boundary5, computed5, computed5, computed5, computed
    First 2 items0, valid boundary5, computed11, computed16, computed16, computed
    First 3 items0, valid boundary0, uncomputed initial value0, uncomputed initial value0, uncomputed initial value0, uncomputed initial value
  6. 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 cCurrent valueRound and status
    00Boundary shared across rounds
    15i = 2, processed in this round; serves as old state for next round
    211i = 2, processed in this round; serves as old state for next round
    316i = 2, processed in this round; serves as old state for next round
    416i = 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 itemsCapacity 0Capacity 1Capacity 2Capacity 3Capacity 4
    First 0 items0, valid boundary0, valid boundary0, valid boundary0, valid boundary0, valid boundary
    First item only0, valid boundary5, computed5, computed5, computed5, computed
    First 2 items0, valid boundary5, computed11, computed16, computed16, computed
    First 3 items0, valid boundary0, uncomputed initial value0, uncomputed initial value0, uncomputed initial value0, 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:

knapsack.py
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]
knapsack.cpp
/* 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];
}
knapsack.java
/* 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];
}
knapsack.cs
/* 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];
}
knapsack.go
/* 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]
}
knapsack.swift
/* 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]
}
knapsack.js
/* 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];
}
knapsack.ts
/* 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];
}
knapsack.dart
/* 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];
}
knapsack.rs
/* 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]
}
knapsack.c
/* 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;
}
knapsack.kt
/* 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]
}
knapsack.rb
### 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
Visualize execution

Share your insights, questions, or suggestions in the comments