跳转至

14.4   0-1 背包问题

背包问题是一个非常好的动态规划入门题目,是动态规划中最常见的问题形式。其具有很多变种,例如 0-1 背包问题、完全背包问题、多重背包问题等。

在本节中,我们先来求解最常见的 0-1 背包问题。

Question

给定 \(n\) 个物品,第 \(i\) 个物品的重量为 \(wgt[i-1]\)、价值为 \(val[i-1]\) ,和一个容量为 \(cap\) 的背包。每个物品只能选择一次,问在限定背包容量下能放入物品的最大价值。

观察图 14-17 ,由于物品编号 \(i\) 从 \(1\) 开始计数,数组索引从 \(0\) 开始计数,因此物品 \(i\) 对应重量 \(wgt[i-1]\) 和价值 \(val[i-1]\) 。

图 14-17   0-1 背包的示例数据

图解 14-17:0-1 背包:容量 50 的最优选择

从五件物品中选择重量 20 的香蕉和重量 30 的葡萄,恰好装满容量 50,获得最大价值 270。

0-1 背包问题规定每件物品最多只能选一次,要求在所选物品总重量不超过背包容量的前提下最大化总价值。本图的输入共有 5 件物品,背包容量 cap=50;图中物品编号 i 从 1 到 5,对应数组下标 i-1(源图表头写为 wgt[i-1] 与 val[i-1])。

左上方表格按编号 1 至 5 列出五件物品的图标、重量与价值(完整数据见表),其中编号 2 的香蕉行与编号 3 的葡萄行分别以浅橙色与浅紫色底色突出,并各引出一条箭头指向右上方的紫色背包图标(旁注“背包容量 cap = 50”)。

下方结论框写出“最大价值:270”,并配合香蕉和葡萄图标说明“最优方案:将香蕉、葡萄放入背包,共占用 50 背包容量”。

容量 50 的五件物品;编号从 1 开始
编号图示物品重量价值最优方案是否选入
1苹果1050否
2香蕉20120是
3葡萄30150是
4菠萝40210否
5西瓜50240否

按输入数据计算,选 2 号香蕉和 3 号葡萄的重量为 20+30=50,价值为 120+150=270。这是在所有不超重组合中的最大值,例如高于选 1 号与 4 号的 260,也高于单选 5 号的 240;这些算式与比较是根据图中输入补充的对照示例。

我们可以将 0-1 背包问题看作一个由 \(n\) 轮决策组成的过程,对于每个物体都有不放入和放入两种决策,因此该问题满足决策树模型。

该问题的目标是求解“在限定背包容量下能放入物品的最大价值”,因此较大概率是一个动态规划问题。

第一步:思考每轮的决策,定义状态,从而得到 \(dp\) 表

对于每个物品来说,不放入背包,背包容量不变;放入背包,背包容量减小。由此可得状态定义:当前物品编号 \(i\) 和背包容量 \(c\) ,记为 \([i, c]\) 。

状态 \([i, c]\) 对应的子问题为:前 \(i\) 个物品在容量为 \(c\) 的背包中的最大价值,记为 \(dp[i, c]\) 。

待求解的是 \(dp[n, cap]\) ,因此需要一个尺寸为 \((n+1) \times (cap+1)\) 的二维 \(dp\) 表。

第二步:找出最优子结构,进而推导出状态转移方程

当我们做出物品 \(i\) 的决策后,剩余的是前 \(i-1\) 个物品决策的子问题,可分为以下两种情况。

  • 不放入物品 \(i\) :背包容量不变,状态变化为 \([i-1, c]\) 。
  • 放入物品 \(i\) :背包容量减少 \(wgt[i-1]\) ,价值增加 \(val[i-1]\) ,状态变化为 \([i-1, c-wgt[i-1]]\) 。

上述分析向我们揭示了本题的最优子结构:最大价值 \(dp[i, c]\) 等于不放入物品 \(i\) 和放入物品 \(i\) 两种方案中价值更大的那一个。由此可推导出状态转移方程:

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

需要注意的是,若当前物品重量 \(wgt[i - 1]\) 超出剩余背包容量 \(c\) ,则只能选择不放入背包。

第三步:确定边界条件和状态转移顺序

当无物品或背包容量为 \(0\) 时最大价值为 \(0\) ,即首列 \(dp[i, 0]\) 和首行 \(dp[0, c]\) 都等于 \(0\) 。

当前状态 \([i, c]\) 从上方的状态 \([i-1, c]\) 和左上方的状态 \([i-1, c-wgt[i-1]]\) 转移而来,因此通过两层循环正序遍历整个 \(dp\) 表即可。

根据以上分析,我们接下来按顺序实现暴力搜索、记忆化搜索、动态规划解法。

1.   方法一:暴力搜索

搜索代码包含以下要素。

  • 递归参数:状态 \([i, c]\) 。
  • 返回值:子问题的解 \(dp[i, c]\) 。
  • 终止条件:当物品编号越界 \(i = 0\) 或背包剩余容量为 \(0\) 时,终止递归并返回价值 \(0\) 。
  • 剪枝:若当前物品重量超出背包剩余容量,则只能选择不放入背包。
knapsack.py
def knapsack_dfs(wgt: list[int], val: list[int], i: int, c: int) -> int:
    """0-1 背包:暴力搜索"""
    # 若已选完所有物品或背包无剩余容量,则返回价值 0
    if i == 0 or c == 0:
        return 0
    # 若超过背包容量,则只能选择不放入背包
    if wgt[i - 1] > c:
        return knapsack_dfs(wgt, val, i - 1, c)
    # 计算不放入和放入物品 i 的最大价值
    no = knapsack_dfs(wgt, val, i - 1, c)
    yes = knapsack_dfs(wgt, val, i - 1, c - wgt[i - 1]) + val[i - 1]
    # 返回两种方案中价值更大的那一个
    return max(no, yes)
knapsack.cpp
/* 0-1 背包:暴力搜索 */
int knapsackDFS(vector<int> &wgt, vector<int> &val, int i, int c) {
    // 若已选完所有物品或背包无剩余容量,则返回价值 0
    if (i == 0 || c == 0) {
        return 0;
    }
    // 若超过背包容量,则只能选择不放入背包
    if (wgt[i - 1] > c) {
        return knapsackDFS(wgt, val, i - 1, c);
    }
    // 计算不放入和放入物品 i 的最大价值
    int no = knapsackDFS(wgt, val, i - 1, c);
    int yes = knapsackDFS(wgt, val, i - 1, c - wgt[i - 1]) + val[i - 1];
    // 返回两种方案中价值更大的那一个
    return max(no, yes);
}
knapsack.java
/* 0-1 背包:暴力搜索 */
int knapsackDFS(int[] wgt, int[] val, int i, int c) {
    // 若已选完所有物品或背包无剩余容量,则返回价值 0
    if (i == 0 || c == 0) {
        return 0;
    }
    // 若超过背包容量,则只能选择不放入背包
    if (wgt[i - 1] > c) {
        return knapsackDFS(wgt, val, i - 1, c);
    }
    // 计算不放入和放入物品 i 的最大价值
    int no = knapsackDFS(wgt, val, i - 1, c);
    int yes = knapsackDFS(wgt, val, i - 1, c - wgt[i - 1]) + val[i - 1];
    // 返回两种方案中价值更大的那一个
    return Math.max(no, yes);
}
knapsack.cs
/* 0-1 背包:暴力搜索 */
int KnapsackDFS(int[] weight, int[] val, int i, int c) {
    // 若已选完所有物品或背包无剩余容量,则返回价值 0
    if (i == 0 || c == 0) {
        return 0;
    }
    // 若超过背包容量,则只能选择不放入背包
    if (weight[i - 1] > c) {
        return KnapsackDFS(weight, val, i - 1, c);
    }
    // 计算不放入和放入物品 i 的最大价值
    int no = KnapsackDFS(weight, val, i - 1, c);
    int yes = KnapsackDFS(weight, val, i - 1, c - weight[i - 1]) + val[i - 1];
    // 返回两种方案中价值更大的那一个
    return Math.Max(no, yes);
}
knapsack.go
/* 0-1 背包:暴力搜索 */
func knapsackDFS(wgt, val []int, i, c int) int {
    // 若已选完所有物品或背包无剩余容量,则返回价值 0
    if i == 0 || c == 0 {
        return 0
    }
    // 若超过背包容量,则只能选择不放入背包
    if wgt[i-1] > c {
        return knapsackDFS(wgt, val, i-1, c)
    }
    // 计算不放入和放入物品 i 的最大价值
    no := knapsackDFS(wgt, val, i-1, c)
    yes := knapsackDFS(wgt, val, i-1, c-wgt[i-1]) + val[i-1]
    // 返回两种方案中价值更大的那一个
    return int(math.Max(float64(no), float64(yes)))
}
knapsack.swift
/* 0-1 背包:暴力搜索 */
func knapsackDFS(wgt: [Int], val: [Int], i: Int, c: Int) -> Int {
    // 若已选完所有物品或背包无剩余容量,则返回价值 0
    if i == 0 || c == 0 {
        return 0
    }
    // 若超过背包容量,则只能选择不放入背包
    if wgt[i - 1] > c {
        return knapsackDFS(wgt: wgt, val: val, i: i - 1, c: c)
    }
    // 计算不放入和放入物品 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 max(no, yes)
}
knapsack.js
/* 0-1 背包:暴力搜索 */
function knapsackDFS(wgt, val, i, c) {
    // 若已选完所有物品或背包无剩余容量,则返回价值 0
    if (i === 0 || c === 0) {
        return 0;
    }
    // 若超过背包容量,则只能选择不放入背包
    if (wgt[i - 1] > c) {
        return knapsackDFS(wgt, val, i - 1, c);
    }
    // 计算不放入和放入物品 i 的最大价值
    const no = knapsackDFS(wgt, val, i - 1, c);
    const yes = knapsackDFS(wgt, val, i - 1, c - wgt[i - 1]) + val[i - 1];
    // 返回两种方案中价值更大的那一个
    return Math.max(no, yes);
}
knapsack.ts
/* 0-1 背包:暴力搜索 */
function knapsackDFS(
    wgt: Array<number>,
    val: Array<number>,
    i: number,
    c: number
): number {
    // 若已选完所有物品或背包无剩余容量,则返回价值 0
    if (i === 0 || c === 0) {
        return 0;
    }
    // 若超过背包容量,则只能选择不放入背包
    if (wgt[i - 1] > c) {
        return knapsackDFS(wgt, val, i - 1, c);
    }
    // 计算不放入和放入物品 i 的最大价值
    const no = knapsackDFS(wgt, val, i - 1, c);
    const yes = knapsackDFS(wgt, val, i - 1, c - wgt[i - 1]) + val[i - 1];
    // 返回两种方案中价值更大的那一个
    return Math.max(no, yes);
}
knapsack.dart
/* 0-1 背包:暴力搜索 */
int knapsackDFS(List<int> wgt, List<int> val, int i, int c) {
  // 若已选完所有物品或背包无剩余容量,则返回价值 0
  if (i == 0 || c == 0) {
    return 0;
  }
  // 若超过背包容量,则只能选择不放入背包
  if (wgt[i - 1] > c) {
    return knapsackDFS(wgt, val, i - 1, c);
  }
  // 计算不放入和放入物品 i 的最大价值
  int no = knapsackDFS(wgt, val, i - 1, c);
  int yes = knapsackDFS(wgt, val, i - 1, c - wgt[i - 1]) + val[i - 1];
  // 返回两种方案中价值更大的那一个
  return max(no, yes);
}
knapsack.rs
/* 0-1 背包:暴力搜索 */
fn knapsack_dfs(wgt: &[i32], val: &[i32], i: usize, c: usize) -> i32 {
    // 若已选完所有物品或背包无剩余容量,则返回价值 0
    if i == 0 || c == 0 {
        return 0;
    }
    // 若超过背包容量,则只能选择不放入背包
    if wgt[i - 1] > c as i32 {
        return knapsack_dfs(wgt, val, i - 1, c);
    }
    // 计算不放入和放入物品 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];
    // 返回两种方案中价值更大的那一个
    std::cmp::max(no, yes)
}
knapsack.c
/* 0-1 背包:暴力搜索 */
int knapsackDFS(int wgt[], int val[], int i, int c) {
    // 若已选完所有物品或背包无剩余容量,则返回价值 0
    if (i == 0 || c == 0) {
        return 0;
    }
    // 若超过背包容量,则只能选择不放入背包
    if (wgt[i - 1] > c) {
        return knapsackDFS(wgt, val, i - 1, c);
    }
    // 计算不放入和放入物品 i 的最大价值
    int no = knapsackDFS(wgt, val, i - 1, c);
    int yes = knapsackDFS(wgt, val, i - 1, c - wgt[i - 1]) + val[i - 1];
    // 返回两种方案中价值更大的那一个
    return myMax(no, yes);
}
knapsack.kt
/* 0-1 背包:暴力搜索 */
fun knapsackDFS(
    wgt: IntArray,
    _val: IntArray,
    i: Int,
    c: Int
): Int {
    // 若已选完所有物品或背包无剩余容量,则返回价值 0
    if (i == 0 || c == 0) {
        return 0
    }
    // 若超过背包容量,则只能选择不放入背包
    if (wgt[i - 1] > c) {
        return knapsackDFS(wgt, _val, i - 1, c)
    }
    // 计算不放入和放入物品 i 的最大价值
    val no = knapsackDFS(wgt, _val, i - 1, c)
    val yes = knapsackDFS(wgt, _val, i - 1, c - wgt[i - 1]) + _val[i - 1]
    // 返回两种方案中价值更大的那一个
    return max(no, yes)
}
knapsack.rb
### 0-1 背包:暴力搜索 ###
def knapsack_dfs(wgt, val, i, c)
  # 若已选完所有物品或背包无剩余容量,则返回价值 0
  return 0 if i == 0 || c == 0
  # 若超过背包容量,则只能选择不放入背包
  return knapsack_dfs(wgt, val, i - 1, c) if wgt[i - 1] > c
  # 计算不放入和放入物品 i 的最大价值
  no = knapsack_dfs(wgt, val, i - 1, c)
  yes = knapsack_dfs(wgt, val, i - 1, c - wgt[i - 1]) + val[i - 1]
  # 返回两种方案中价值更大的那一个
  [no, yes].max
end
可视化运行

如图 14-18 所示,由于每个物品都会产生不选和选两条搜索分支,因此时间复杂度为 \(O(2^n)\) 。

观察递归树,容易发现其中存在重叠子问题,例如 \(dp[1, 10]\) 等。而当物品较多、背包容量较大,尤其是相同重量的物品较多时,重叠子问题的数量将会大幅增多。

图 14-18   0-1 背包问题的暴力搜索递归树

图解 14-18:0-1 背包的重复递归

在容量 30 的专用三物品示例中,两条不同选择路线都会进入状态 dp[1, 10] 并重复展开其子树。

0-1 背包中每件物品最多选一次。注意本图采用与前图及代码主程序不同的独立 3 物品示例:背包容量 cap = 30,3 件物品的重量依次为 10、20、20,价值依次为 60、110、120(见表)。状态 dp[i, c] 表示在前 i 件物品中做选择、剩余可用容量为 c 时的最大价值;图中表头写为 wgt[i]、val[i](编号 i 从 1 开始),而正文代码访问数组时使用下标 i-1。

当当前物品装得下时,比较不选它的 dp[i-1, c] 与选它的 dp[i-1, c-wgt[i-1]] + val[i-1],取较大值;装不下时只取不选分支。无物品(i = 0)或容量为 0(c = 0)时返回 0。

递归从根 dp[3, 30] 出发,按物品 3(菠萝,重 20、价值 120)、物品 2(西瓜,重 20、价值 110)、物品 1(苹果,重 10、价值 60)的顺序决策。由于物品 2 和物品 3 的重量同为 20,无论走“不选物品 3、再选物品 2”(dp[3, 30] → dp[2, 30] → dp[1, 10])还是“选物品 3、再不选物品 2”(dp[3, 30] → dp[2, 10] → dp[1, 10]),都会扣减重量 20、剩下容量 10,且待选范围只剩物品 1,因此两条不同路径汇合到同一个子问题 dp[1, 10]。

暴力搜索不会记录已算出的子问题,遇到两处 dp[1, 10] 时会分别向下展开,各自比较不选物品 1 的 dp[0, 10] 与选物品 1 的 dp[0, 0] + 60,因此同一子问题 dp[1, 10] 被完整展开两次,第二次是重复计算。

在右子树 dp[2, 10] 处,当前剩余容量为 10,而物品 2 的重量为 20,超过剩余容量。图中画出的 dp[1, -10] 标注“剪枝:物品重量 > 背包容量”,仅用于示意被排除的超重分支;正文代码在递归前先判断物品重量是否大于剩余容量,超重时只调用不选分支 dp[1, 10],不会实际发起负容量调用。

下方两表分别列出专用输入数据和完整图示递归树;递归树以从根出发的选择路线作为行标题,可区分同一状态的不同出现位置。

递归树使用的三件物品;容量 30
编号图示物品重量价值
1苹果1060
2西瓜20110
3菠萝20120
完整递归树;路线从根开始,包括被排除的负容量示意
选择路线状态处理或返回子节点与价值增量
根dp[3,30]比较不选与选的总价值不选:dp[2,30];选:dp[2,10]+120
不选3dp[2,30]比较不选与选的总价值不选:dp[1,30];选:dp[1,10]+110
不选3→不选2dp[1,30]比较不选与选的总价值不选:dp[0,30];选:dp[0,20]+60
不选3→不选2→不选1dp[0,30]基例,返回 0不展开
不选3→不选2→选1dp[0,20]基例,返回 0不展开
不选3→选2dp[1,10]比较不选与选的总价值不选:dp[0,10];选:dp[0,0]+60
不选3→选2→不选1dp[0,10]基例,返回 0不展开
不选3→选2→选1dp[0,0]基例,返回 0不展开
选3dp[2,10]超重,只执行不选分支不选:dp[1,10];选:dp[1,-10](被排除)
选3→不选2dp[1,10]比较不选与选的总价值不选:dp[0,10];选:dp[0,0]+60
选3→不选2→不选1dp[0,10]基例,返回 0不展开
选3→不选2→选1dp[0,0]基例,返回 0不展开
选3→选2dp[1,-10]超重分支示意;不实际调用不展开

图中共 13 个节点,其中 6 个是返回 0 的基例叶节点,另有 1 个超重示意节点。根据输入数据推算,选物品 1 和物品 3 的总重量为 10 + 20 = 30,最大价值为 60 + 120 = 180;180 未直接标在树节点上。

2.   方法二:记忆化搜索

为了保证重叠子问题只被计算一次,我们借助记忆列表 mem 来记录子问题的解,其中 mem[i][c] 对应 \(dp[i, c]\) 。

引入记忆化之后,时间复杂度取决于子问题数量,也就是 \(O(n \times cap)\) 。实现代码如下:

knapsack.py
def knapsack_dfs_mem(
    wgt: list[int], val: list[int], mem: list[list[int]], i: int, c: int
) -> int:
    """0-1 背包:记忆化搜索"""
    # 若已选完所有物品或背包无剩余容量,则返回价值 0
    if i == 0 or c == 0:
        return 0
    # 若已有记录,则直接返回
    if mem[i][c] != -1:
        return mem[i][c]
    # 若超过背包容量,则只能选择不放入背包
    if wgt[i - 1] > c:
        return knapsack_dfs_mem(wgt, val, mem, i - 1, c)
    # 计算不放入和放入物品 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]
    # 记录并返回两种方案中价值更大的那一个
    mem[i][c] = max(no, yes)
    return mem[i][c]
knapsack.cpp
/* 0-1 背包:记忆化搜索 */
int knapsackDFSMem(vector<int> &wgt, vector<int> &val, vector<vector<int>> &mem, int i, int c) {
    // 若已选完所有物品或背包无剩余容量,则返回价值 0
    if (i == 0 || c == 0) {
        return 0;
    }
    // 若已有记录,则直接返回
    if (mem[i][c] != -1) {
        return mem[i][c];
    }
    // 若超过背包容量,则只能选择不放入背包
    if (wgt[i - 1] > c) {
        return knapsackDFSMem(wgt, val, mem, i - 1, c);
    }
    // 计算不放入和放入物品 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];
    // 记录并返回两种方案中价值更大的那一个
    mem[i][c] = max(no, yes);
    return mem[i][c];
}
knapsack.java
/* 0-1 背包:记忆化搜索 */
int knapsackDFSMem(int[] wgt, int[] val, int[][] mem, int i, int c) {
    // 若已选完所有物品或背包无剩余容量,则返回价值 0
    if (i == 0 || c == 0) {
        return 0;
    }
    // 若已有记录,则直接返回
    if (mem[i][c] != -1) {
        return mem[i][c];
    }
    // 若超过背包容量,则只能选择不放入背包
    if (wgt[i - 1] > c) {
        return knapsackDFSMem(wgt, val, mem, i - 1, c);
    }
    // 计算不放入和放入物品 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];
    // 记录并返回两种方案中价值更大的那一个
    mem[i][c] = Math.max(no, yes);
    return mem[i][c];
}
knapsack.cs
/* 0-1 背包:记忆化搜索 */
int KnapsackDFSMem(int[] weight, int[] val, int[][] mem, int i, int c) {
    // 若已选完所有物品或背包无剩余容量,则返回价值 0
    if (i == 0 || c == 0) {
        return 0;
    }
    // 若已有记录,则直接返回
    if (mem[i][c] != -1) {
        return mem[i][c];
    }
    // 若超过背包容量,则只能选择不放入背包
    if (weight[i - 1] > c) {
        return KnapsackDFSMem(weight, val, mem, i - 1, c);
    }
    // 计算不放入和放入物品 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];
    // 记录并返回两种方案中价值更大的那一个
    mem[i][c] = Math.Max(no, yes);
    return mem[i][c];
}
knapsack.go
/* 0-1 背包:记忆化搜索 */
func knapsackDFSMem(wgt, val []int, mem [][]int, i, c int) int {
    // 若已选完所有物品或背包无剩余容量,则返回价值 0
    if i == 0 || c == 0 {
        return 0
    }
    // 若已有记录,则直接返回
    if mem[i][c] != -1 {
        return mem[i][c]
    }
    // 若超过背包容量,则只能选择不放入背包
    if wgt[i-1] > c {
        return knapsackDFSMem(wgt, val, mem, i-1, c)
    }
    // 计算不放入和放入物品 i 的最大价值
    no := knapsackDFSMem(wgt, val, mem, i-1, c)
    yes := knapsackDFSMem(wgt, val, mem, i-1, c-wgt[i-1]) + val[i-1]
    // 返回两种方案中价值更大的那一个
    mem[i][c] = int(math.Max(float64(no), float64(yes)))
    return mem[i][c]
}
knapsack.swift
/* 0-1 背包:记忆化搜索 */
func knapsackDFSMem(wgt: [Int], val: [Int], mem: inout [[Int]], i: Int, c: Int) -> Int {
    // 若已选完所有物品或背包无剩余容量,则返回价值 0
    if i == 0 || c == 0 {
        return 0
    }
    // 若已有记录,则直接返回
    if mem[i][c] != -1 {
        return mem[i][c]
    }
    // 若超过背包容量,则只能选择不放入背包
    if wgt[i - 1] > c {
        return knapsackDFSMem(wgt: wgt, val: val, mem: &mem, i: i - 1, c: c)
    }
    // 计算不放入和放入物品 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]
    // 记录并返回两种方案中价值更大的那一个
    mem[i][c] = max(no, yes)
    return mem[i][c]
}
knapsack.js
/* 0-1 背包:记忆化搜索 */
function knapsackDFSMem(wgt, val, mem, i, c) {
    // 若已选完所有物品或背包无剩余容量,则返回价值 0
    if (i === 0 || c === 0) {
        return 0;
    }
    // 若已有记录,则直接返回
    if (mem[i][c] !== -1) {
        return mem[i][c];
    }
    // 若超过背包容量,则只能选择不放入背包
    if (wgt[i - 1] > c) {
        return knapsackDFSMem(wgt, val, mem, i - 1, c);
    }
    // 计算不放入和放入物品 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];
    // 记录并返回两种方案中价值更大的那一个
    mem[i][c] = Math.max(no, yes);
    return mem[i][c];
}
knapsack.ts
/* 0-1 背包:记忆化搜索 */
function knapsackDFSMem(
    wgt: Array<number>,
    val: Array<number>,
    mem: Array<Array<number>>,
    i: number,
    c: number
): number {
    // 若已选完所有物品或背包无剩余容量,则返回价值 0
    if (i === 0 || c === 0) {
        return 0;
    }
    // 若已有记录,则直接返回
    if (mem[i][c] !== -1) {
        return mem[i][c];
    }
    // 若超过背包容量,则只能选择不放入背包
    if (wgt[i - 1] > c) {
        return knapsackDFSMem(wgt, val, mem, i - 1, c);
    }
    // 计算不放入和放入物品 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];
    // 记录并返回两种方案中价值更大的那一个
    mem[i][c] = Math.max(no, yes);
    return mem[i][c];
}
knapsack.dart
/* 0-1 背包:记忆化搜索 */
int knapsackDFSMem(
  List<int> wgt,
  List<int> val,
  List<List<int>> mem,
  int i,
  int c,
) {
  // 若已选完所有物品或背包无剩余容量,则返回价值 0
  if (i == 0 || c == 0) {
    return 0;
  }
  // 若已有记录,则直接返回
  if (mem[i][c] != -1) {
    return mem[i][c];
  }
  // 若超过背包容量,则只能选择不放入背包
  if (wgt[i - 1] > c) {
    return knapsackDFSMem(wgt, val, mem, i - 1, c);
  }
  // 计算不放入和放入物品 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];
  // 记录并返回两种方案中价值更大的那一个
  mem[i][c] = max(no, yes);
  return mem[i][c];
}
knapsack.rs
/* 0-1 背包:记忆化搜索 */
fn knapsack_dfs_mem(wgt: &[i32], val: &[i32], mem: &mut Vec<Vec<i32>>, i: usize, c: usize) -> i32 {
    // 若已选完所有物品或背包无剩余容量,则返回价值 0
    if i == 0 || c == 0 {
        return 0;
    }
    // 若已有记录,则直接返回
    if mem[i][c] != -1 {
        return mem[i][c];
    }
    // 若超过背包容量,则只能选择不放入背包
    if wgt[i - 1] > c as i32 {
        return knapsack_dfs_mem(wgt, val, mem, i - 1, c);
    }
    // 计算不放入和放入物品 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];
    // 记录并返回两种方案中价值更大的那一个
    mem[i][c] = std::cmp::max(no, yes);
    mem[i][c]
}
knapsack.c
/* 0-1 背包:记忆化搜索 */
int knapsackDFSMem(int wgt[], int val[], int memCols, int **mem, int i, int c) {
    // 若已选完所有物品或背包无剩余容量,则返回价值 0
    if (i == 0 || c == 0) {
        return 0;
    }
    // 若已有记录,则直接返回
    if (mem[i][c] != -1) {
        return mem[i][c];
    }
    // 若超过背包容量,则只能选择不放入背包
    if (wgt[i - 1] > c) {
        return knapsackDFSMem(wgt, val, memCols, mem, i - 1, c);
    }
    // 计算不放入和放入物品 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];
    // 记录并返回两种方案中价值更大的那一个
    mem[i][c] = myMax(no, yes);
    return mem[i][c];
}
knapsack.kt
/* 0-1 背包:记忆化搜索 */
fun knapsackDFSMem(
    wgt: IntArray,
    _val: IntArray,
    mem: Array<IntArray>,
    i: Int,
    c: Int
): Int {
    // 若已选完所有物品或背包无剩余容量,则返回价值 0
    if (i == 0 || c == 0) {
        return 0
    }
    // 若已有记录,则直接返回
    if (mem[i][c] != -1) {
        return mem[i][c]
    }
    // 若超过背包容量,则只能选择不放入背包
    if (wgt[i - 1] > c) {
        return knapsackDFSMem(wgt, _val, mem, i - 1, c)
    }
    // 计算不放入和放入物品 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]
    // 记录并返回两种方案中价值更大的那一个
    mem[i][c] = max(no, yes)
    return mem[i][c]
}
knapsack.rb
### 0-1 背包:记忆化搜索 ###
def knapsack_dfs_mem(wgt, val, mem, i, c)
  # 若已选完所有物品或背包无剩余容量,则返回价值 0
  return 0 if i == 0 || c == 0
  # 若已有记录,则直接返回
  return mem[i][c] if mem[i][c] != -1
  # 若超过背包容量,则只能选择不放入背包
  return knapsack_dfs_mem(wgt, val, mem, i - 1, c) if wgt[i - 1] > c
  # 计算不放入和放入物品 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]
  # 记录并返回两种方案中价值更大的那一个
  mem[i][c] = [no, yes].max
end
可视化运行

图 14-19 展示了在记忆化搜索中被剪掉的搜索分支。

图 14-19   0-1 背包问题的记忆化搜索递归树

图解 14-19:0-1 背包的记忆化搜索

沿选物品 3 的路线再次遇到 dp[1, 10] 时,直接读取缓存返回,省去重复子树;这与超重剪枝的含义不同。

0-1 背包中每件物品最多选择一次。本图使用与前图相同的独立 3 物品、容量 cap = 30 示例:重量依次为 10、20、20,价值依次为 60、110、120(见表)。dp[i, c] 表示前 i 件物品在可用容量 c 下的最大价值;图中表头写 wgt[i]、val[i](i 从 1 到 3),正文代码用下标 i-1 访问数组。

当当前物品装得下时,比较不选它的 dp[i-1, c] 与选它的 dp[i-1, c-wgt[i-1]] + val[i-1],取较大值;装不下时只取不选分支。无物品(i = 0)或容量为 0(c = 0)时返回 0。

从根 dp[3, 30] 依次对物品 3、2、1 决策时,由于物品 2(西瓜)和物品 3(菠萝)的重量同为 20,走“不选物品 3、再选物品 2”或“选物品 3、再不选物品 2”这两条路线都会剩下容量 10、待选范围只剩物品 1(苹果,重 10、价值 60),从而汇合到同一个状态 dp[1, 10]。

左子树首次访问 dp[1, 10](路线“不选3→选2”)时,展开比较 dp[0, 10] 与 dp[0, 0] + 60 并把结果存入缓存;当右子树在 dp[2, 10] 下选择不放物品 2、再次遇到 dp[1, 10](路线“选3→不选2”)时,触发“剪枝:找到记录”,直接读取缓存返回,不再重复展开两个叶节点。由物品 1 重 10、价值 60 可推知该缓存返回值为 60,这一数值由输入表推导而来,并非节点上的原标数字。

在右子树 dp[2, 10] 处,两个分支虽都带有剪刀标记,但停止原因完全不同:左分支 dp[1, 10] 是命中缓存、直接返回合法子问题的有效解 60;右分支 dp[1, -10](“剪枝:物品重量 > 背包容量”)则是因为物品 2 重量 20 超过当前剩余容量 10 而被排除的非法示意节点,程序在递归前已判断超重,只调用不选分支 dp[1, 10],不会实际调用 dp[1, -10]。

下方两表分别列出专用输入数据和完整图示递归树;递归树以从根出发的选择路线作为行标题,可区分同一状态的不同出现位置。

递归树使用的三件物品;容量 30
编号图示物品重量价值
1苹果1060
2西瓜20110
3菠萝20120
完整递归树;路线从根开始,包括被排除的负容量示意
选择路线状态处理或返回子节点与价值增量
根dp[3,30]比较不选与选的总价值不选:dp[2,30];选:dp[2,10]+120
不选3dp[2,30]比较不选与选的总价值不选:dp[1,30];选:dp[1,10]+110
不选3→不选2dp[1,30]比较不选与选的总价值不选:dp[0,30];选:dp[0,20]+60
不选3→不选2→不选1dp[0,30]基例,返回 0不展开
不选3→不选2→选1dp[0,20]基例,返回 0不展开
不选3→选2dp[1,10]比较不选与选的总价值不选:dp[0,10];选:dp[0,0]+60
不选3→选2→不选1dp[0,10]基例,返回 0不展开
不选3→选2→选1dp[0,0]基例,返回 0不展开
选3dp[2,10]超重,只执行不选分支不选:dp[1,10];选:dp[1,-10](被排除)
选3→不选2dp[1,10]命中缓存,返回 60(由输入推导)不展开
选3→选2dp[1,-10]超重分支示意;不实际调用不展开

图中共 11 个节点,基例叶节点由暴力树的 6 个减为 4 个;全局最大价值仍为选物品 1 和物品 3 所得的 180。缓存值 60 与最大价值 180 均根据输入数据推导,并非树节点上的原标数字。

3.   方法三:动态规划

动态规划实质上就是在状态转移中填充 \(dp\) 表的过程,代码如下所示:

knapsack.py
def knapsack_dp(wgt: list[int], val: list[int], cap: int) -> int:
    """0-1 背包:动态规划"""
    n = len(wgt)
    # 初始化 dp 表
    dp = [[0] * (cap + 1) for _ in range(n + 1)]
    # 状态转移
    for i in range(1, n + 1):
        for c in range(1, cap + 1):
            if wgt[i - 1] > c:
                # 若超过背包容量,则不选物品 i
                dp[i][c] = dp[i - 1][c]
            else:
                # 不选和选物品 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 背包:动态规划 */
int knapsackDP(vector<int> &wgt, vector<int> &val, int cap) {
    int n = wgt.size();
    // 初始化 dp 表
    vector<vector<int>> dp(n + 1, vector<int>(cap + 1, 0));
    // 状态转移
    for (int i = 1; i <= n; i++) {
        for (int c = 1; c <= cap; c++) {
            if (wgt[i - 1] > c) {
                // 若超过背包容量,则不选物品 i
                dp[i][c] = dp[i - 1][c];
            } else {
                // 不选和选物品 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 背包:动态规划 */
int knapsackDP(int[] wgt, int[] val, int cap) {
    int n = wgt.length;
    // 初始化 dp 表
    int[][] dp = new int[n + 1][cap + 1];
    // 状态转移
    for (int i = 1; i <= n; i++) {
        for (int c = 1; c <= cap; c++) {
            if (wgt[i - 1] > c) {
                // 若超过背包容量,则不选物品 i
                dp[i][c] = dp[i - 1][c];
            } else {
                // 不选和选物品 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 背包:动态规划 */
int KnapsackDP(int[] weight, int[] val, int cap) {
    int n = weight.Length;
    // 初始化 dp 表
    int[,] dp = new int[n + 1, cap + 1];
    // 状态转移
    for (int i = 1; i <= n; i++) {
        for (int c = 1; c <= cap; c++) {
            if (weight[i - 1] > c) {
                // 若超过背包容量,则不选物品 i
                dp[i, c] = dp[i - 1, c];
            } else {
                // 不选和选物品 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 背包:动态规划 */
func knapsackDP(wgt, val []int, cap int) int {
    n := len(wgt)
    // 初始化 dp 表
    dp := make([][]int, n+1)
    for i := 0; i <= n; i++ {
        dp[i] = make([]int, cap+1)
    }
    // 状态转移
    for i := 1; i <= n; i++ {
        for c := 1; c <= cap; c++ {
            if wgt[i-1] > c {
                // 若超过背包容量,则不选物品 i
                dp[i][c] = dp[i-1][c]
            } else {
                // 不选和选物品 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 背包:动态规划 */
func knapsackDP(wgt: [Int], val: [Int], cap: Int) -> Int {
    let n = wgt.count
    // 初始化 dp 表
    var dp = Array(repeating: Array(repeating: 0, count: cap + 1), count: n + 1)
    // 状态转移
    for i in 1 ... n {
        for c in 1 ... cap {
            if wgt[i - 1] > c {
                // 若超过背包容量,则不选物品 i
                dp[i][c] = dp[i - 1][c]
            } else {
                // 不选和选物品 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 背包:动态规划 */
function knapsackDP(wgt, val, cap) {
    const n = wgt.length;
    // 初始化 dp 表
    const dp = Array(n + 1)
        .fill(0)
        .map(() => Array(cap + 1).fill(0));
    // 状态转移
    for (let i = 1; i <= n; i++) {
        for (let c = 1; c <= cap; c++) {
            if (wgt[i - 1] > c) {
                // 若超过背包容量,则不选物品 i
                dp[i][c] = dp[i - 1][c];
            } else {
                // 不选和选物品 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 背包:动态规划 */
function knapsackDP(
    wgt: Array<number>,
    val: Array<number>,
    cap: number
): number {
    const n = wgt.length;
    // 初始化 dp 表
    const dp = Array.from({ length: n + 1 }, () =>
        Array.from({ length: cap + 1 }, () => 0)
    );
    // 状态转移
    for (let i = 1; i <= n; i++) {
        for (let c = 1; c <= cap; c++) {
            if (wgt[i - 1] > c) {
                // 若超过背包容量,则不选物品 i
                dp[i][c] = dp[i - 1][c];
            } else {
                // 不选和选物品 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 背包:动态规划 */
int knapsackDP(List<int> wgt, List<int> val, int cap) {
  int n = wgt.length;
  // 初始化 dp 表
  List<List<int>> dp = List.generate(n + 1, (index) => List.filled(cap + 1, 0));
  // 状态转移
  for (int i = 1; i <= n; i++) {
    for (int c = 1; c <= cap; c++) {
      if (wgt[i - 1] > c) {
        // 若超过背包容量,则不选物品 i
        dp[i][c] = dp[i - 1][c];
      } else {
        // 不选和选物品 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 背包:动态规划 */
fn knapsack_dp(wgt: &[i32], val: &[i32], cap: usize) -> i32 {
    let n = wgt.len();
    // 初始化 dp 表
    let mut dp = vec![vec![0; cap + 1]; n + 1];
    // 状态转移
    for i in 1..=n {
        for c in 1..=cap {
            if wgt[i - 1] > c as i32 {
                // 若超过背包容量,则不选物品 i
                dp[i][c] = dp[i - 1][c];
            } else {
                // 不选和选物品 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 背包:动态规划 */
int knapsackDP(int wgt[], int val[], int cap, int wgtSize) {
    int n = wgtSize;
    // 初始化 dp 表
    int **dp = malloc((n + 1) * sizeof(int *));
    for (int i = 0; i <= n; i++) {
        dp[i] = calloc(cap + 1, sizeof(int));
    }
    // 状态转移
    for (int i = 1; i <= n; i++) {
        for (int c = 1; c <= cap; c++) {
            if (wgt[i - 1] > c) {
                // 若超过背包容量,则不选物品 i
                dp[i][c] = dp[i - 1][c];
            } else {
                // 不选和选物品 i 这两种方案的较大值
                dp[i][c] = myMax(dp[i - 1][c], dp[i - 1][c - wgt[i - 1]] + val[i - 1]);
            }
        }
    }
    int res = dp[n][cap];
    // 释放内存
    for (int i = 0; i <= n; i++) {
        free(dp[i]);
    }
    return res;
}
knapsack.kt
/* 0-1 背包:动态规划 */
fun knapsackDP(wgt: IntArray, _val: IntArray, cap: Int): Int {
    val n = wgt.size
    // 初始化 dp 表
    val dp = Array(n + 1) { IntArray(cap + 1) }
    // 状态转移
    for (i in 1..n) {
        for (c in 1..cap) {
            if (wgt[i - 1] > c) {
                // 若超过背包容量,则不选物品 i
                dp[i][c] = dp[i - 1][c]
            } else {
                // 不选和选物品 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 背包:动态规划 ###
def knapsack_dp(wgt, val, cap)
  n = wgt.length
  # 初始化 dp 表
  dp = Array.new(n + 1) { Array.new(cap + 1, 0) }
  # 状态转移
  for i in 1...(n + 1)
    for c in 1...(cap + 1)
      if wgt[i - 1] > c
        # 若超过背包容量,则不选物品 i
        dp[i][c] = dp[i - 1][c]
      else
        # 不选和选物品 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
可视化运行

如图 14-20 所示,时间复杂度和空间复杂度都由数组 dp 大小决定,即 \(O(n \times cap)\) 。

图 14-20   0-1 背包问题的动态规划过程

图解 14-20:0-1 背包动态规划

三件物品各最多选一次,演示 0-1 背包的逐格递推;容量 4 时求得最大总价值 20。

候选物品共 3 件(n = 3),编号、名称、重量和价值见输入表。背包容量 cap = 4,目标是不超重时获得最大总价值,无须恰好装满。

状态 dp[i, c] 表示从前 i 件物品中选择、总重量不超过容量 c 时的最大价值。行下标 i 取 0 至 3,列下标 c 取 0 至 4,状态表共 4 行 5 列;物品编号 i 从 1 开始,对应数组重量 wgt[i-1] 和价值 val[i-1]。

第 1 步初始化;第 2 至 5、6 至 9、10 至 13 步分别计算第 1、2、3 行,每行按容量 c = 1 至 4 推进;第 14 步返回答案。每个非边界格只计算一次,之后不再改动。最终表的单元格附有首次计算的步骤号:到达该步之前,此格为未计算初值 0;到达该步及之后,此格取表中的最终值。

对于第 i 件物品,重量记为 w,价值记为 v。若 w > c,装不下,只能不选,继承正上方 dp[i-1, c];否则比较不选时的 dp[i-1, c] 与选入时的 dp[i-1, c-w] + v。后者位于上一行、向左移 w 列。两个来源都取自上一行,尚未包含第 i 件物品,保证每件最多选一次。

本组物品数据
物品编号i物品重量wgt[i−1]价值val[i−1]
1苹果15
2菠萝211
3西瓜315
  1. 初始化 4×5 状态矩阵

    建立 4 行 5 列的 dp 表,所有格子先填 0。第 0 行(无物品)和第 0 列(零容量)是已确定的边界值 0,图中用深色字表示;其余 12 格是尚未计算的初值 0,用淡色字表示,不能当作已算出的最优价值。

  2. 计算 dp[1, 1],得 5

    考虑前 1 件物品、容量 1,当前物品是苹果(重 1、价值 5)。不选得上一行 dp[0, 1] = 0;选入后剩余容量 1 - 1 = 0,查上一行(前 0 件物品)的 dp[0, 0] = 0,加价值 5 得 5。取较大值 5 写入 dp[1, 1]。此前只有初始化的边界格,其后非边界格仍为未计算初值 0。

  3. 计算 dp[1, 2],得 5

    考虑前 1 件物品、容量 2,当前物品是苹果(重 1、价值 5)。不选得上一行 dp[0, 2] = 0;选入后剩余容量 2 - 1 = 1,查上一行(前 0 件物品)的 dp[0, 1] = 0,加价值 5 得 5。取较大值 5 写入 dp[1, 2]。此前各格已算好,其后非边界格仍为未计算初值 0。

  4. 计算 dp[1, 3],得 5

    考虑前 1 件物品、容量 3,当前物品是苹果(重 1、价值 5)。不选得上一行 dp[0, 3] = 0;选入后剩余容量 3 - 1 = 2,查上一行(前 0 件物品)的 dp[0, 2] = 0,加价值 5 得 5。取较大值 5 写入 dp[1, 3]。此前各格已算好,其后非边界格仍为未计算初值 0。

  5. 计算 dp[1, 4],得 5

    考虑前 1 件物品、容量 4,当前物品是苹果(重 1、价值 5)。不选得上一行 dp[0, 4] = 0;选入后剩余容量 4 - 1 = 3,查上一行(前 0 件物品)的 dp[0, 3] = 0,加价值 5 得 5。取较大值 5 写入 dp[1, 4]。此前各格已算好,其后非边界格仍为未计算初值 0。

  6. 计算 dp[2, 1],得 5

    考虑前 2 件物品、容量 1,当前物品是菠萝(重 2、价值 11)。重量 2 大于容量 1,装不下,只能不选;继承上一行 dp[1, 1] = 5,写入 dp[2, 1] = 5。此前各格已算好,其后非边界格仍为未计算初值 0。

  7. 计算 dp[2, 2],得 11

    考虑前 2 件物品、容量 2,当前物品是菠萝(重 2、价值 11)。不选得上一行 dp[1, 2] = 5;选入后剩余容量 2 - 2 = 0,查上一行(前 1 件物品)的 dp[1, 0] = 0,加价值 11 得 11。取较大值 11 写入 dp[2, 2]。此前各格已算好,其后非边界格仍为未计算初值 0。

  8. 计算 dp[2, 3],得 16

    考虑前 2 件物品、容量 3,当前物品是菠萝(重 2、价值 11)。不选得上一行 dp[1, 3] = 5;选入后剩余容量 3 - 2 = 1,查上一行(前 1 件物品)的 dp[1, 1] = 5,加价值 11 得 16。取较大值 16 写入 dp[2, 3]。此前各格已算好,其后非边界格仍为未计算初值 0。

  9. 计算 dp[2, 4],得 16

    考虑前 2 件物品、容量 4,当前物品是菠萝(重 2、价值 11)。不选得上一行 dp[1, 4] = 5;选入后剩余容量 4 - 2 = 2,查上一行(前 1 件物品)的 dp[1, 2] = 5,加价值 11 得 16。取较大值 16 写入 dp[2, 4]。此前各格已算好,其后非边界格仍为未计算初值 0。

  10. 计算 dp[3, 1],得 5

    考虑前 3 件物品、容量 1,当前物品是西瓜(重 3、价值 15)。重量 3 大于容量 1,装不下,只能不选;继承上一行 dp[2, 1] = 5,写入 dp[3, 1] = 5。此前各格已算好,其后非边界格仍为未计算初值 0。

  11. 计算 dp[3, 2],得 11

    考虑前 3 件物品、容量 2,当前物品是西瓜(重 3、价值 15)。重量 3 大于容量 2,装不下,只能不选;继承上一行 dp[2, 2] = 11,写入 dp[3, 2] = 11。此前各格已算好,其后非边界格仍为未计算初值 0。

  12. 计算 dp[3, 3],得 16

    考虑前 3 件物品、容量 3,当前物品是西瓜(重 3、价值 15)。不选得上一行 dp[2, 3] = 16;选入后剩余容量 3 - 3 = 0,查上一行(前 2 件物品)的 dp[2, 0] = 0,加价值 15 得 15。取较大值 16 写入 dp[3, 3]。此前各格已算好,其后非边界格仍为未计算初值 0。

  13. 计算 dp[3, 4],得 20

    考虑前 3 件物品、容量 4,当前物品是西瓜(重 3、价值 15)。不选得上一行 dp[2, 4] = 16;选入后剩余容量 4 - 3 = 1,查上一行(前 2 件物品)的 dp[2, 1] = 5,加价值 15 得 20。取较大值 20 写入 dp[3, 4]。至此全部 12 个非边界格已算完。

  14. 返回容量 4 的最大价值 20

    读取右下角 dp[3, 4] = 20,选择苹果与西瓜:总重量 1 + 3 = 4,总价值 5 + 15 = 20。末帧所写“将所有物品放入背包的最大价值 20”指考虑全部三件候选物品后的最优子集;三件全选重 6,超过容量 4。

填表完成后的 dp 最大价值与首次计算步骤
可选物品(前 i 件)容量 c=0容量 c=1容量 c=2容量 c=3容量 c=4
没有物品(i=0)0(边界有效)0(边界有效)0(边界有效)0(边界有效)0(边界有效)
苹果(i=1)0(边界有效)5(第 2 步)5(第 3 步)5(第 4 步)5(第 5 步)
苹果、菠萝(i=2)0(边界有效)5(第 6 步)11(第 7 步)16(第 8 步)16(第 9 步)
苹果、菠萝、西瓜(i=3)0(边界有效)5(第 10 步)11(第 11 步)16(第 12 步)20(第 13 步)

4.   空间优化

由于每个状态都只与其上一行的状态有关,因此我们可以使用两个数组滚动前进,将空间复杂度从 \(O(n \times cap)\) 降至 \(O(cap)\) 。

进一步思考,我们能否仅用一个数组实现空间优化呢?观察可知,每个状态都是由正上方或左上方的格子转移过来的。假设只有一个数组,当开始遍历第 \(i\) 行时,该数组存储的仍然是第 \(i-1\) 行的状态。

  • 如果采取正序遍历,那么遍历到 \(dp[i, j]\) 时,左上方 \(dp[i-1, 1]\) ~ \(dp[i-1, j-1]\) 值可能已经被覆盖,此时就无法得到正确的状态转移结果。
  • 如果采取倒序遍历,则不会发生覆盖问题,状态转移可以正确进行。

图 14-21 展示了在单个数组下从第 \(i = 1\) 行转换至第 \(i = 2\) 行的过程。请思考正序遍历和倒序遍历的区别。

图 14-21   0-1 背包的空间优化后的动态规划过程

图解 14-21:背包动态规划的单行压缩

使用单行一维数组保存状态,按容量从大到小倒序更新,确保状态转移读取的是上一轮物品的旧值,避免同一件物品被重复选入。

共有三件物品:物品 1 苹果(重量 1、价值 5)、物品 2 菠萝(重量 2、价值 11)、物品 3 西瓜(重量 3、价值 15),背包最大容量为 4,每件物品最多选一次。物品编号 i 从 1 开始,对应数组下标 wgt[i-1] 与 val[i-1]。

图解 6 步仅演示外层循环 i=2(处理第二件物品菠萝)这一轮的完整倒序更新过程。进入本轮前,一维数组 dp[0..4] 已保存仅考虑第 1 件物品苹果(i=1)的结果 [0, 5, 5, 5, 5];第 3 件物品西瓜(i=3)在本图中始终尚未处理。dp[c] 表示在当前已考虑物品范围内、总重量不超过容量 c 时的最大价值,不要求恰好装满。

处理菠萝(重 2、值 11)时,若当前容量 c ≥ 2,状态转移需比较“不选菠萝”(保留上一轮旧值 dp[c])与“选入菠萝”(读取上一轮较小容量旧值 dp[c-2] + 11),取较大者写回 dp[c]。按容量 c = 4、3、2、1 倒序遍历时,被读取的左方格 dp[c-2] 尚未被本轮覆盖,仍保持上一轮(i=1,仅考虑苹果)的旧状态。

反之,若按容量从小到大正序更新,容量 2 会先被更新为 dp[2] = 11(已选入一件菠萝);随后计算容量 4 时读取 dp[2] + 11 就会算出 22,相当于在容量 4 内把同一件菠萝重复装入两次,违背 0-1 背包每件最多一次的限制。倒序更新在 dp[2] 仍为旧值 5 时先算容量 4,从而得到正确值 5 + 11 = 16。

每帧画面上方给出 4×5 二维对照表,下方为实际使用的单行数组 dp[0..4]。单行中蓝色格表示保留的上一轮(i=1)旧状态,绿色格表示本轮(i=2)已完成更新的新状态;本轮末尾整行统一改标为蓝色,准备作为下一轮处理西瓜时的旧状态,数值本身不再变化。

每步的单行表按容量分别列出数值与所属轮次:i=1 只考虑苹果,i=2 考虑苹果与菠萝,容量 0 始终为边界 0。每步也保留完整二维对照表;其中前 0 件、前 1 件、前 3 件三行始终不变,前 3 件行在容量 1 至 4 的 0 仍是未计算初值。两类表名均含步号,可直接按步骤、容量及物品范围查找。

单行压缩示例:容量 4 的三件物品
物品编号i物品重量wgt[i−1]价值val[i−1]
1苹果15
2菠萝211
3西瓜315
  1. 开始处理菠萝

    进入 i=2(菠萝,重 2、值 11)这一轮前,单行 dp[0..4] 已存有上一轮 i=1(仅考虑苹果)的有效结果 [0, 5, 5, 5, 5],并非全零初始表。容量 0 恒为有效边界 0,容量 1 至 4 均处于上一轮 i=1 的旧状态,准备从最大容量 c=4 开始倒序更新。

    背包压缩第 1 步(开始处理菠萝):单行 dp 的值与所属轮
    容量 c当前值所属轮次与状态
    00各轮共有的边界
    15i=1,上一轮,尚未被本轮覆盖
    25i=1,上一轮,尚未被本轮覆盖
    35i=1,上一轮,尚未被本轮覆盖
    45i=1,上一轮,尚未被本轮覆盖
    背包压缩第 1 步(开始处理菠萝):完整二维对照表
    可选物品容量0容量1容量2容量3容量4
    前0件物品0,边界有效0,边界有效0,边界有效0,边界有效0,边界有效
    前1件物品0,边界有效5,已计算5,已计算5,已计算5,已计算
    前2件物品0,边界有效0,未计算初值0,未计算初值0,未计算初值0,未计算初值
    前3件物品0,边界有效0,未计算初值0,未计算初值0,未计算初值0,未计算初值
  2. 倒序更新容量4

    首先处理最大容量 c=4:不选菠萝保留旧值 dp[4]=5;选入菠萝则读取尚未被本轮覆盖的上一轮旧值 dp[4-2]=dp[2]=5,加上菠萝价值 11 得 16。取较大值将 dp[4] 更新为 16(归属本轮 i=2),而容量 1、2、3 仍保持上一轮 i=1 的旧值 5。当前单行 dp = [0, 5, 5, 5, 16]。

    背包压缩第 2 步(倒序更新容量4):单行 dp 的值与所属轮
    容量 c当前值所属轮次与状态
    00各轮共有的边界
    15i=1,上一轮,尚未被本轮覆盖
    25i=1,上一轮,尚未被本轮覆盖
    35i=1,上一轮,尚未被本轮覆盖
    416i=2,本轮已处理
    背包压缩第 2 步(倒序更新容量4):完整二维对照表
    可选物品容量0容量1容量2容量3容量4
    前0件物品0,边界有效0,边界有效0,边界有效0,边界有效0,边界有效
    前1件物品0,边界有效5,已计算5,已计算5,已计算5,已计算
    前2件物品0,边界有效0,未计算初值0,未计算初值0,未计算初值16,已计算
    前3件物品0,边界有效0,未计算初值0,未计算初值0,未计算初值0,未计算初值
  3. 倒序更新容量3

    继续倒序处理容量 c=3:不选菠萝保留旧值 dp[3]=5;选入菠萝则读取仍属上一轮 i=1 的旧值 dp[3-2]=dp[1]=5,加 11 得 16。取较大值将 dp[3] 更新为 16(归属本轮 i=2),容量 1、2 仍保持上一轮 i=1 的旧状态 5。当前单行 dp = [0, 5, 5, 16, 16]。

    背包压缩第 3 步(倒序更新容量3):单行 dp 的值与所属轮
    容量 c当前值所属轮次与状态
    00各轮共有的边界
    15i=1,上一轮,尚未被本轮覆盖
    25i=1,上一轮,尚未被本轮覆盖
    316i=2,本轮已处理
    416i=2,本轮已处理
    背包压缩第 3 步(倒序更新容量3):完整二维对照表
    可选物品容量0容量1容量2容量3容量4
    前0件物品0,边界有效0,边界有效0,边界有效0,边界有效0,边界有效
    前1件物品0,边界有效5,已计算5,已计算5,已计算5,已计算
    前2件物品0,边界有效0,未计算初值0,未计算初值16,已计算16,已计算
    前3件物品0,边界有效0,未计算初值0,未计算初值0,未计算初值0,未计算初值
  4. 倒序更新容量2

    继续倒序处理容量 c=2:不选菠萝保留旧值 dp[2]=5;选入菠萝则读取边界 dp[2-2]=dp[0]=0,加 11 得 11。取较大值将 dp[2] 更新为 11(归属本轮 i=2)。正因为倒序到此刻才覆盖 dp[2],此前计算容量 4 时才能读到未被覆盖的旧值 dp[2]=5;此时仅剩容量 1 仍属上一轮 i=1。当前单行 dp = [0, 5, 11, 16, 16]。

    背包压缩第 4 步(倒序更新容量2):单行 dp 的值与所属轮
    容量 c当前值所属轮次与状态
    00各轮共有的边界
    15i=1,上一轮,尚未被本轮覆盖
    211i=2,本轮已处理
    316i=2,本轮已处理
    416i=2,本轮已处理
    背包压缩第 4 步(倒序更新容量2):完整二维对照表
    可选物品容量0容量1容量2容量3容量4
    前0件物品0,边界有效0,边界有效0,边界有效0,边界有效0,边界有效
    前1件物品0,边界有效5,已计算5,已计算5,已计算5,已计算
    前2件物品0,边界有效0,未计算初值11,已计算16,已计算16,已计算
    前3件物品0,边界有效0,未计算初值0,未计算初值0,未计算初值0,未计算初值
  5. 处理装不下菠萝的容量1

    最后处理容量 c=1:由于菠萝重量 2 大于容量 1,无法装入菠萝,只能沿用上一轮不选菠萝的值 dp[1]=5。虽然 dp[1] 的数值依然是 5,但该容量已完成第二轮(i=2)的判断,状态归属由上一轮 i=1 推进为本轮 i=2(数值不变不等于所属轮次未变)。当前单行 dp = [0, 5, 11, 16, 16]。

    背包压缩第 5 步(处理装不下菠萝的容量1):单行 dp 的值与所属轮
    容量 c当前值所属轮次与状态
    00各轮共有的边界
    15i=2,本轮已处理
    211i=2,本轮已处理
    316i=2,本轮已处理
    416i=2,本轮已处理
    背包压缩第 5 步(处理装不下菠萝的容量1):完整二维对照表
    可选物品容量0容量1容量2容量3容量4
    前0件物品0,边界有效0,边界有效0,边界有效0,边界有效0,边界有效
    前1件物品0,边界有效5,已计算5,已计算5,已计算5,已计算
    前2件物品0,边界有效5,已计算11,已计算16,已计算16,已计算
    前3件物品0,边界有效0,未计算初值0,未计算初值0,未计算初值0,未计算初值
  6. 本轮结束,准备下一轮

    第二轮(i=2,菠萝)的所有容量均已更新完毕,单行 dp[0..4] = [0, 5, 11, 16, 16] 完整保存前两件物品的解。本帧没有新增计算,将容量 1 至 4 的格子由绿色改标为蓝色,使整行统一为蓝色,表示这组 i=2 的结果将在下一轮处理第三件物品西瓜(i=3)时充当旧状态;西瓜尚未开始处理。

    背包压缩第 6 步(本轮结束,准备下一轮):单行 dp 的值与所属轮
    容量 c当前值所属轮次与状态
    00各轮共有的边界
    15i=2,本轮已处理;将作为下一轮旧状态
    211i=2,本轮已处理;将作为下一轮旧状态
    316i=2,本轮已处理;将作为下一轮旧状态
    416i=2,本轮已处理;将作为下一轮旧状态
    背包压缩第 6 步(本轮结束,准备下一轮):完整二维对照表
    可选物品容量0容量1容量2容量3容量4
    前0件物品0,边界有效0,边界有效0,边界有效0,边界有效0,边界有效
    前1件物品0,边界有效5,已计算5,已计算5,已计算5,已计算
    前2件物品0,边界有效5,已计算11,已计算16,已计算16,已计算
    前3件物品0,边界有效0,未计算初值0,未计算初值0,未计算初值0,未计算初值

第二轮(i=2,菠萝)倒序更新结束后,单行数组为 dp = [0, 5, 11, 16, 16],其中 dp[4] = 16 仅代表前两件物品(苹果与菠萝)在容量 4 下的最大价值,是中间轮次的局部结果;第三件物品西瓜(重 3、值 15)尚未处理,不能将 16 误认为三件物品完整问题的最终答案 20。最终答案 20 由输入推算:选苹果和西瓜,重量 1 + 3 = 4,价值 5 + 15 = 20;本图未画出这一轮结果。

在代码实现中,我们仅需将数组 dp 的第一维 \(i\) 直接删除,并且把内循环更改为倒序遍历即可:

knapsack.py
def knapsack_dp_comp(wgt: list[int], val: list[int], cap: int) -> int:
    """0-1 背包:空间优化后的动态规划"""
    n = len(wgt)
    # 初始化 dp 表
    dp = [0] * (cap + 1)
    # 状态转移
    for i in range(1, n + 1):
        # 倒序遍历
        for c in range(cap, 0, -1):
            if wgt[i - 1] > c:
                # 若超过背包容量,则不选物品 i
                dp[c] = dp[c]
            else:
                # 不选和选物品 i 这两种方案的较大值
                dp[c] = max(dp[c], dp[c - wgt[i - 1]] + val[i - 1])
    return dp[cap]
knapsack.cpp
/* 0-1 背包:空间优化后的动态规划 */
int knapsackDPComp(vector<int> &wgt, vector<int> &val, int cap) {
    int n = wgt.size();
    // 初始化 dp 表
    vector<int> dp(cap + 1, 0);
    // 状态转移
    for (int i = 1; i <= n; i++) {
        // 倒序遍历
        for (int c = cap; c >= 1; c--) {
            if (wgt[i - 1] <= c) {
                // 不选和选物品 i 这两种方案的较大值
                dp[c] = max(dp[c], dp[c - wgt[i - 1]] + val[i - 1]);
            }
        }
    }
    return dp[cap];
}
knapsack.java
/* 0-1 背包:空间优化后的动态规划 */
int knapsackDPComp(int[] wgt, int[] val, int cap) {
    int n = wgt.length;
    // 初始化 dp 表
    int[] dp = new int[cap + 1];
    // 状态转移
    for (int i = 1; i <= n; i++) {
        // 倒序遍历
        for (int c = cap; c >= 1; c--) {
            if (wgt[i - 1] <= c) {
                // 不选和选物品 i 这两种方案的较大值
                dp[c] = Math.max(dp[c], dp[c - wgt[i - 1]] + val[i - 1]);
            }
        }
    }
    return dp[cap];
}
knapsack.cs
/* 0-1 背包:空间优化后的动态规划 */
int KnapsackDPComp(int[] weight, int[] val, int cap) {
    int n = weight.Length;
    // 初始化 dp 表
    int[] dp = new int[cap + 1];
    // 状态转移
    for (int i = 1; i <= n; i++) {
        // 倒序遍历
        for (int c = cap; c > 0; c--) {
            if (weight[i - 1] > c) {
                // 若超过背包容量,则不选物品 i
                dp[c] = dp[c];
            } else {
                // 不选和选物品 i 这两种方案的较大值
                dp[c] = Math.Max(dp[c], dp[c - weight[i - 1]] + val[i - 1]);
            }
        }
    }
    return dp[cap];
}
knapsack.go
/* 0-1 背包:空间优化后的动态规划 */
func knapsackDPComp(wgt, val []int, cap int) int {
    n := len(wgt)
    // 初始化 dp 表
    dp := make([]int, cap+1)
    // 状态转移
    for i := 1; i <= n; i++ {
        // 倒序遍历
        for c := cap; c >= 1; c-- {
            if wgt[i-1] <= c {
                // 不选和选物品 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 背包:空间优化后的动态规划 */
func knapsackDPComp(wgt: [Int], val: [Int], cap: Int) -> Int {
    let n = wgt.count
    // 初始化 dp 表
    var dp = Array(repeating: 0, count: cap + 1)
    // 状态转移
    for i in 1 ... n {
        // 倒序遍历
        for c in (1 ... cap).reversed() {
            if wgt[i - 1] <= c {
                // 不选和选物品 i 这两种方案的较大值
                dp[c] = max(dp[c], dp[c - wgt[i - 1]] + val[i - 1])
            }
        }
    }
    return dp[cap]
}
knapsack.js
/* 0-1 背包:空间优化后的动态规划 */
function knapsackDPComp(wgt, val, cap) {
    const n = wgt.length;
    // 初始化 dp 表
    const dp = Array(cap + 1).fill(0);
    // 状态转移
    for (let i = 1; i <= n; i++) {
        // 倒序遍历
        for (let c = cap; c >= 1; c--) {
            if (wgt[i - 1] <= c) {
                // 不选和选物品 i 这两种方案的较大值
                dp[c] = Math.max(dp[c], dp[c - wgt[i - 1]] + val[i - 1]);
            }
        }
    }
    return dp[cap];
}
knapsack.ts
/* 0-1 背包:空间优化后的动态规划 */
function knapsackDPComp(
    wgt: Array<number>,
    val: Array<number>,
    cap: number
): number {
    const n = wgt.length;
    // 初始化 dp 表
    const dp = Array(cap + 1).fill(0);
    // 状态转移
    for (let i = 1; i <= n; i++) {
        // 倒序遍历
        for (let c = cap; c >= 1; c--) {
            if (wgt[i - 1] <= c) {
                // 不选和选物品 i 这两种方案的较大值
                dp[c] = Math.max(dp[c], dp[c - wgt[i - 1]] + val[i - 1]);
            }
        }
    }
    return dp[cap];
}
knapsack.dart
/* 0-1 背包:空间优化后的动态规划 */
int knapsackDPComp(List<int> wgt, List<int> val, int cap) {
  int n = wgt.length;
  // 初始化 dp 表
  List<int> dp = List.filled(cap + 1, 0);
  // 状态转移
  for (int i = 1; i <= n; i++) {
    // 倒序遍历
    for (int c = cap; c >= 1; c--) {
      if (wgt[i - 1] <= c) {
        // 不选和选物品 i 这两种方案的较大值
        dp[c] = max(dp[c], dp[c - wgt[i - 1]] + val[i - 1]);
      }
    }
  }
  return dp[cap];
}
knapsack.rs
/* 0-1 背包:空间优化后的动态规划 */
fn knapsack_dp_comp(wgt: &[i32], val: &[i32], cap: usize) -> i32 {
    let n = wgt.len();
    // 初始化 dp 表
    let mut dp = vec![0; cap + 1];
    // 状态转移
    for i in 1..=n {
        // 倒序遍历
        for c in (1..=cap).rev() {
            if wgt[i - 1] <= c as i32 {
                // 不选和选物品 i 这两种方案的较大值
                dp[c] = std::cmp::max(dp[c], dp[c - wgt[i - 1] as usize] + val[i - 1]);
            }
        }
    }
    dp[cap]
}
knapsack.c
/* 0-1 背包:空间优化后的动态规划 */
int knapsackDPComp(int wgt[], int val[], int cap, int wgtSize) {
    int n = wgtSize;
    // 初始化 dp 表
    int *dp = calloc(cap + 1, sizeof(int));
    // 状态转移
    for (int i = 1; i <= n; i++) {
        // 倒序遍历
        for (int c = cap; c >= 1; c--) {
            if (wgt[i - 1] <= c) {
                // 不选和选物品 i 这两种方案的较大值
                dp[c] = myMax(dp[c], dp[c - wgt[i - 1]] + val[i - 1]);
            }
        }
    }
    int res = dp[cap];
    // 释放内存
    free(dp);
    return res;
}
knapsack.kt
/* 0-1 背包:空间优化后的动态规划 */
fun knapsackDPComp(wgt: IntArray, _val: IntArray, cap: Int): Int {
    val n = wgt.size
    // 初始化 dp 表
    val dp = IntArray(cap + 1)
    // 状态转移
    for (i in 1..n) {
        // 倒序遍历
        for (c in cap downTo 1) {
            if (wgt[i - 1] <= c) {
                // 不选和选物品 i 这两种方案的较大值
                dp[c] = max(dp[c], dp[c - wgt[i - 1]] + _val[i - 1])
            }
        }
    }
    return dp[cap]
}
knapsack.rb
### 0-1 背包:空间优化后的动态规划 ###
def knapsack_dp_comp(wgt, val, cap)
  n = wgt.length
  # 初始化 dp 表
  dp = Array.new(cap + 1, 0)
  # 状态转移
  for i in 1...(n + 1)
    # 倒序遍历
    for c in cap.downto(1)
      if wgt[i - 1] > c
        # 若超过背包容量,则不选物品 i
        dp[c] = dp[c]
      else
        # 不选和选物品 i 这两种方案的较大值
        dp[c] = [dp[c], dp[c - wgt[i - 1]] + val[i - 1]].max
      end
    end
  end
  dp[cap]
end
可视化运行

欢迎在评论区留下你的见解、问题或建议