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 背包容量”。
| 编号 | 图示物品 | 重量 | 价值 | 最优方案是否选入 |
|---|---|---|---|---|
| 1 | 苹果 | 10 | 50 | 否 |
| 2 | 香蕉 | 20 | 120 | 是 |
| 3 | 葡萄 | 30 | 150 | 是 |
| 4 | 菠萝 | 40 | 210 | 否 |
| 5 | 西瓜 | 50 | 240 | 否 |
按输入数据计算,选 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\) 两种方案中价值更大的那一个。由此可推导出状态转移方程:
需要注意的是,若当前物品重量 \(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\) 。
- 剪枝:若当前物品重量超出背包剩余容量,则只能选择不放入背包。
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)
/* 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);
}
/* 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);
}
/* 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);
}
/* 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)))
}
/* 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)
}
/* 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);
}
/* 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);
}
/* 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);
}
/* 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)
}
/* 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);
}
/* 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)
}
### 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],不会实际发起负容量调用。
下方两表分别列出专用输入数据和完整图示递归树;递归树以从根出发的选择路线作为行标题,可区分同一状态的不同出现位置。
| 编号 | 图示物品 | 重量 | 价值 |
|---|---|---|---|
| 1 | 苹果 | 10 | 60 |
| 2 | 西瓜 | 20 | 110 |
| 3 | 菠萝 | 20 | 120 |
| 选择路线 | 状态 | 处理或返回 | 子节点与价值增量 |
|---|---|---|---|
| 根 | dp[3,30] | 比较不选与选的总价值 | 不选:dp[2,30];选:dp[2,10]+120 |
| 不选3 | dp[2,30] | 比较不选与选的总价值 | 不选:dp[1,30];选:dp[1,10]+110 |
| 不选3→不选2 | dp[1,30] | 比较不选与选的总价值 | 不选:dp[0,30];选:dp[0,20]+60 |
| 不选3→不选2→不选1 | dp[0,30] | 基例,返回 0 | 不展开 |
| 不选3→不选2→选1 | dp[0,20] | 基例,返回 0 | 不展开 |
| 不选3→选2 | dp[1,10] | 比较不选与选的总价值 | 不选:dp[0,10];选:dp[0,0]+60 |
| 不选3→选2→不选1 | dp[0,10] | 基例,返回 0 | 不展开 |
| 不选3→选2→选1 | dp[0,0] | 基例,返回 0 | 不展开 |
| 选3 | dp[2,10] | 超重,只执行不选分支 | 不选:dp[1,10];选:dp[1,-10](被排除) |
| 选3→不选2 | dp[1,10] | 比较不选与选的总价值 | 不选:dp[0,10];选:dp[0,0]+60 |
| 选3→不选2→不选1 | dp[0,10] | 基例,返回 0 | 不展开 |
| 选3→不选2→选1 | dp[0,0] | 基例,返回 0 | 不展开 |
| 选3→选2 | dp[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)\) 。实现代码如下:
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]
/* 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];
}
/* 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];
}
/* 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];
}
/* 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]
}
/* 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]
}
/* 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];
}
/* 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];
}
/* 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];
}
/* 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]
}
/* 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];
}
/* 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]
}
### 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]。
下方两表分别列出专用输入数据和完整图示递归树;递归树以从根出发的选择路线作为行标题,可区分同一状态的不同出现位置。
| 编号 | 图示物品 | 重量 | 价值 |
|---|---|---|---|
| 1 | 苹果 | 10 | 60 |
| 2 | 西瓜 | 20 | 110 |
| 3 | 菠萝 | 20 | 120 |
| 选择路线 | 状态 | 处理或返回 | 子节点与价值增量 |
|---|---|---|---|
| 根 | dp[3,30] | 比较不选与选的总价值 | 不选:dp[2,30];选:dp[2,10]+120 |
| 不选3 | dp[2,30] | 比较不选与选的总价值 | 不选:dp[1,30];选:dp[1,10]+110 |
| 不选3→不选2 | dp[1,30] | 比较不选与选的总价值 | 不选:dp[0,30];选:dp[0,20]+60 |
| 不选3→不选2→不选1 | dp[0,30] | 基例,返回 0 | 不展开 |
| 不选3→不选2→选1 | dp[0,20] | 基例,返回 0 | 不展开 |
| 不选3→选2 | dp[1,10] | 比较不选与选的总价值 | 不选:dp[0,10];选:dp[0,0]+60 |
| 不选3→选2→不选1 | dp[0,10] | 基例,返回 0 | 不展开 |
| 不选3→选2→选1 | dp[0,0] | 基例,返回 0 | 不展开 |
| 选3 | dp[2,10] | 超重,只执行不选分支 | 不选:dp[1,10];选:dp[1,-10](被排除) |
| 选3→不选2 | dp[1,10] | 命中缓存,返回 60(由输入推导) | 不展开 |
| 选3→选2 | dp[1,-10] | 超重分支示意;不实际调用 | 不展开 |
图中共 11 个节点,基例叶节点由暴力树的 6 个减为 4 个;全局最大价值仍为选物品 1 和物品 3 所得的 180。缓存值 60 与最大价值 180 均根据输入数据推导,并非树节点上的原标数字。
3. 方法三:动态规划¶
动态规划实质上就是在状态转移中填充 \(dp\) 表的过程,代码如下所示:
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]
/* 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];
}
/* 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];
}
/* 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];
}
/* 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]
}
/* 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]
}
/* 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];
}
/* 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];
}
/* 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];
}
/* 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]
}
/* 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;
}
/* 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]
}
### 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 | 苹果 | 1 | 5 |
| 2 | 菠萝 | 2 | 11 |
| 3 | 西瓜 | 3 | 15 |
初始化 4×5 状态矩阵
建立 4 行 5 列的 dp 表,所有格子先填 0。第 0 行(无物品)和第 0 列(零容量)是已确定的边界值 0,图中用深色字表示;其余 12 格是尚未计算的初值 0,用淡色字表示,不能当作已算出的最优价值。
计算 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。
计算 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。
计算 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。
计算 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。
计算 dp[2, 1],得 5
考虑前 2 件物品、容量 1,当前物品是菠萝(重 2、价值 11)。重量 2 大于容量 1,装不下,只能不选;继承上一行 dp[1, 1] = 5,写入 dp[2, 1] = 5。此前各格已算好,其后非边界格仍为未计算初值 0。
计算 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。
计算 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。
计算 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。
计算 dp[3, 1],得 5
考虑前 3 件物品、容量 1,当前物品是西瓜(重 3、价值 15)。重量 3 大于容量 1,装不下,只能不选;继承上一行 dp[2, 1] = 5,写入 dp[3, 1] = 5。此前各格已算好,其后非边界格仍为未计算初值 0。
计算 dp[3, 2],得 11
考虑前 3 件物品、容量 2,当前物品是西瓜(重 3、价值 15)。重量 3 大于容量 2,装不下,只能不选;继承上一行 dp[2, 2] = 11,写入 dp[3, 2] = 11。此前各格已算好,其后非边界格仍为未计算初值 0。
计算 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。
计算 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 个非边界格已算完。
返回容量 4 的最大价值 20
读取右下角 dp[3, 4] = 20,选择苹果与西瓜:总重量 1 + 3 = 4,总价值 5 + 15 = 20。末帧所写“将所有物品放入背包的最大价值 20”指考虑全部三件候选物品后的最优子集;三件全选重 6,超过容量 4。
| 可选物品(前 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 仍是未计算初值。两类表名均含步号,可直接按步骤、容量及物品范围查找。
| 物品编号i | 物品 | 重量wgt[i−1] | 价值val[i−1] |
|---|---|---|---|
| 1 | 苹果 | 1 | 5 |
| 2 | 菠萝 | 2 | 11 |
| 3 | 西瓜 | 3 | 15 |
开始处理菠萝
进入 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 当前值 所属轮次与状态 0 0 各轮共有的边界 1 5 i=1,上一轮,尚未被本轮覆盖 2 5 i=1,上一轮,尚未被本轮覆盖 3 5 i=1,上一轮,尚未被本轮覆盖 4 5 i=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,未计算初值 倒序更新容量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 当前值 所属轮次与状态 0 0 各轮共有的边界 1 5 i=1,上一轮,尚未被本轮覆盖 2 5 i=1,上一轮,尚未被本轮覆盖 3 5 i=1,上一轮,尚未被本轮覆盖 4 16 i=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
继续倒序处理容量 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 当前值 所属轮次与状态 0 0 各轮共有的边界 1 5 i=1,上一轮,尚未被本轮覆盖 2 5 i=1,上一轮,尚未被本轮覆盖 3 16 i=2,本轮已处理 4 16 i=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,未计算初值 倒序更新容量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 当前值 所属轮次与状态 0 0 各轮共有的边界 1 5 i=1,上一轮,尚未被本轮覆盖 2 11 i=2,本轮已处理 3 16 i=2,本轮已处理 4 16 i=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,未计算初值 处理装不下菠萝的容量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 当前值 所属轮次与状态 0 0 各轮共有的边界 1 5 i=2,本轮已处理 2 11 i=2,本轮已处理 3 16 i=2,本轮已处理 4 16 i=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,未计算初值 本轮结束,准备下一轮
第二轮(i=2,菠萝)的所有容量均已更新完毕,单行 dp[0..4] = [0, 5, 11, 16, 16] 完整保存前两件物品的解。本帧没有新增计算,将容量 1 至 4 的格子由绿色改标为蓝色,使整行统一为蓝色,表示这组 i=2 的结果将在下一轮处理第三件物品西瓜(i=3)时充当旧状态;西瓜尚未开始处理。
背包压缩第 6 步(本轮结束,准备下一轮):单行 dp 的值与所属轮 容量 c 当前值 所属轮次与状态 0 0 各轮共有的边界 1 5 i=2,本轮已处理;将作为下一轮旧状态 2 11 i=2,本轮已处理;将作为下一轮旧状态 3 16 i=2,本轮已处理;将作为下一轮旧状态 4 16 i=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\) 直接删除,并且把内循环更改为倒序遍历即可:
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]
/* 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];
}
/* 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];
}
/* 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];
}
/* 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]
}
/* 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]
}
/* 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];
}
/* 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];
}
/* 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];
}
/* 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]
}
/* 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;
}
/* 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]
}
### 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