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