背包九讲学习笔记
背包九讲学习笔记
本文内容基本涵盖了 dd_engi 的背包九讲，在此基础上加上了自己的理解和代码实现
背包九讲原版 pdf 已由作者崔添翼（dd_engi）上传至 github，你可以 点击这里 进行下载
1. 01 背包问题
题目
基本思路
代码实现如下：
// N为物品数量，V为最大体积
// c[i]为第i件物品的体积，w[i]为第i件物品的价值
// f[i][j]为前i件物品放入容量为j的背包可以获得的最大价值
for (int i = 1; i <= N; i++) {
for (int j = 0; j <= V; j++) {
f[i][j] = f[i - 1][j];
if (j >= c[i]) // 如果当前背包容量能放下第i件物品
f[i][j] = max(f[i - 1][j], f[i - 1][j - c[i]] + w[i]);
}
}
// 最大价值就是 f[N][V];优化空间复杂度
在二维情况下，状态 f[i][j] 是由上一轮 i - 1 的状态得来的。而优化到一维后，如果我们还是正序，则有可能本应该用第 i - 1 轮的状态却用的是第 i 轮的状态。
举个例子，当我们枚举到第 i = 3 轮，物体的体积为 v[3] = 2
f[8] = max(f[8], f[8 - 2] + w[3]) ，这里我们要保证 f[8] 和 f[6] 都是上一轮的状态值。
如果按照正序进行更新 j = 6 时， f[6] = max(f[6], f[6 - 4] + w[3])，对 f[6] 的状态进行了更新，那么在更新 f[8] 时，用到的 f[6] 就不是上一轮的状态了。
按照逆序的顺序，一维数组的更新顺序为：f[8], f[7], f[6], ..., 在本轮更新的值，不会影响本轮中其他未更新的值。
代码如下：
// N为物品数量，V为最大体积
// c[i]为第i件物品的体积，w[i]为第i件物品的价值
// f[j]为N件物品放入容量为j的背包可以获得的最大价值
for (int i = 1; i <= N; i++) {
for (int j = V; j >= c[i]; j--) {
f[j] = max(f[j], f[j - c[i]] + w[i])
}
}
// 最大价值就是 f[V];二维下的状态定义 f[i][j] 是前 i 件物品，背包容量 j 下的最大价值。一维下，少了前 i 件物品这个维度，我们的代码中决策到第 i 件物品（循环到第 i 轮），f[j] 就是前 i 轮已经决策的物品且背包容量 j 下的最大价值。
初始化的细节问题
小结
01 背包问题是最基本的背包问题，它包含了背包问题中设计状态、方程的最基本思想。另外，别的类型的背包问题往往也可以转换成 01 背包问题求解。故一定要仔细体会上面基本思路的得出方法，状态转移方程的意义，以及空间复杂度怎样被优化。
2. 完全背包问题
题目
基本思路
// N为物品数量，V为最大体积
// c[i]为第i件物品的体积，w[i]为第i件物品的价值
// f[i][j]为N件物品放入容量为j的背包可以获得的最大价值
for (int i = 1; i <= N; i++)
for (int j = 0; j <= V; j++)
for (int k = 0; k * c[i] <= j; k++)
f[i][j] = max(f[i][j], f[i - 1][j - k * c[i]] + k * w[i]);
// 最大价值就是f[N][V];将 01 背包问题的基本思路加以改进，得到了这样一个清晰的方法。这说明 01 背包问题的方程的确是很重要，可以推及其它类型的背包问题。但我们还是要试图改进这个复杂度。
一个简单有效的优化
转化为 01 背包问题求解
O(VN) 的算法
这个算法使用一维数组，先看代码：
// N为物品数量，V为最大体积
// c[i]为第i件物品的体积，w[i]为第i件物品的价值
// f[j]为N件物品放入容量为j的背包可以获得的最大价值
for (int i = 1; i <= N; i++)
for (int j = c[i]; j <= V; j++)
f[j] = max(f[j], f[j - c[i]] + w[i]);
// 最大价值就是f[V];你会发现，这个伪代码与 01 背包问题的伪代码只有 v 的循环次序不同而已。
将这个方程用一维数组实现，便得到了上面的代码。
有了上面的关系，那么其实 k 循环可以不要了，之前的代码就可以优化成这样：
for (int i = 1; i <= N; i++)
for (int j = 0; j <= V; j++) {
f[i][j] = f[i - 1][j];
if (j >= c[i])
f[i][j] = max(f[i][j], f[i][j - c[i]] + w[i]);
}因为和 01 背包代码很相像，我们很容易想到进一步优化成一维数组
for (int i = 1; i <= N; i++)
// 注意，这里的j是从小到大枚举
for (int j = c[i]; j <= V; j++)
f[j] = max(f[j], f[j - c[i]] + w[i]);小结
完全背包问题也是一个相当基础的背包问题，它有两个状态转移方程。希望读者能 够对这两个状态转移方程都仔细地体会，不仅记住，也要弄明白它们是怎么得出来的，最好能够自己想一种得到这些方程的方法。
事实上，对每一道动态规划题目都思考其方程的意义以及如何得来，是加深对动态 规划的理解、提高动态规划功力的好方法。
3. 多重背包问题
题目
基本算法
// N为物品数量，V为最大体积
// c[i],w[i],m[i]分别为第i件物品的体积,价值,数量
// f[j]为物品放入容量为j的背包可以获得的最大价值
for (int i = 1; i <= N; i++)
for (int j = V; j >= 0; j--)
for (int k = 1; k <= m[i] && k * c[i] <= j; k++)
f[j] = max(f[j], f[j - k * c[i]] + k * w[i]);
// 最大价值就是f[V];转化为 01 背包问题
// N为物品数量，V为最大体积
// c[i],w[i],m[i]分别为第i件物品的体积,价值,数量
// f[j]为物品放入容量为j的背包可以获得的最大价值
struct Good {
int c, w;
};
vector<Good> goods;
// 二进制处理
for (int i = 1; i <= N; i++) {
for (int k = 1; k <= m[i]; k *= 2) {
m[i] -= k;
goods.push_back({k * c[i], k * w[i]})
}
if (m[i] > 0) {
goods.push_back({m[i] * c[i], m[i] * w[i]});
}
}
// 01背包问题
for (auto good : goods)
for (int j = V; j >= good.c; j--)
f[j] = max(f[j], f[j - good.c] + good.w);
// 最大价值就是f[V];简单来讲上面的过程就是一个二进制优化的方案
假设有一种物品有 m = 13 个，按照之间的方法我们一共需要枚举 14 次（0,1,2,…,13）
再来看看二进制的方法，我们将 13 分成 1,2,22,⋯ ,2k−1,Mi−2k+11, 2, 2^2, \cdots, 2^{k−1},M_i − 2^k + 11,2,22,⋯,2k−1,Mi−2k+1，也就是 1,2,4,6 四件物品，这样对于这件物品我们只需要枚举 4 次即可。我们并没有把m分成 m 份，而是分成了 logm\log mlogm 份。
那为什么不是 1,2,4,8 呢？因为如果取了 1,2,4,8 我们实际上不止可以表示出 0-13，实际上可以表示出 0-15，但是 14,15 并不是我们需要的。
使用单调队列优化
原文中并没有提及使用单调队列优化的算法，在这里给出参考
// q[]为单调队列
// dp_pre表示dp[i-1][]
// dp[]表示dp[i][]
for (int i = 1; i <= N; i++) {
for (int j = 0; j < c[i]; j++) {
// 分别表示队首和队尾
int head = 0, tail = -1;
// k表示当前背包容量
for (int k = j; k <= V; k += c[i]) {
dp[k] = dp_pre[k];
// 维护一个大小为k的区间
// (k - q[head]) / c[i] 表示拿取物品的数量
if (head <= tail && (k - q[head]) / c[i] > m[i])
head++;
// 若队内有值，则该值就是前k个元素的最大值
// dp_pre[q[head]]表示只考虑前i-1个物品时，拿前q[head]个物品的最大价值
if (head <= tail)
dp[k] = max(dp[k], dp_pre[q[head]] + (k - q[head]) / c[i] * w[i]);
// 若队尾元素小于当前元素，则队尾元素出队
// dp_pre[q[tail]] - (q[tail] - j) / c[i] * w[i]表示队尾元素的值
// g[k] - (k - j) / c[i] * w[i]表示当前元素的值
while (head <= tail && dp_pre[q[tail]] - (q[tail] - j) / c[i] * w[i] <= g[k] - (k - j) / c[i] * w[i])
tail--;
// 队列里的元素都比当前元素大，入队
q[++tail] = k;
}
}
}
// 最大价值就是f[V];小
4. 混合三种背包问题
问题
如果将前面 1 、 2 、 3 中的三种背包问题混合起来。也就是说，有的物品只可以取一次（ 01 背包），有的物品可以取无限次（完全背包），有的物品可以取的次数有一个上限（多重背包）。应该怎么求解呢？
01 背包与完全背包的混合
考虑到 01 背包和完全背包中给出的代码只有一处不同，故如果只有两类物品：一类物品只能取一次，另一类物品可以取无限次，那么只需在对每个物品应用转移方程时，根据物品的类别选用顺序或逆序的循环即可，复杂度是 O(VN)。
再加上多重背包
如果再加上最多可以取有限次的多重背包式的物品，那么利用单调队列，也可以给 出均摊 O(VN)的解法。但如果不考虑单调队列算法的话，用将每个这类物品分成O(\log M_i)个 01 背包的物品的方法也已经很优了。
// N为物品数量，V为最大体积
// c[i],w[i],m[i]分别为第i件物品的体积,价值,数量
// f[j]为物品放入容量为j的背包可以获得的最大价值
// 若 m[i]==-1 则为01背包
// 若 m[i]==0 则为完全背包
// 若 m[i]>0 则为多重背包
struct Thing {
int kind;
int c, w;
};
vector<Thing> things;
for (int i = 1; i <= N; i++) {
if (m[i] < 0) // 01背包
things.push_back({-1, c[i], w[i]});
else if (m[i] == 0) // 完全背包
things.push_back({0, c[i], w[i]});
else { // 多重背包
for (int k = 1; k <= m[i]; k *= 2) { // 二进制优化
m[i] -= k;
things.push_back({-1, k * c[i], k * w[i]});
}
if (m[i] > 0) things.push_back({-1, m[i] * c[i], m[i] * w[i]});
}
}
for (auto thing : things) {
if (thing.king < 0) // 01背包
for (int j = V; j >= thing.c; j--) f[j] = max(f[j], f[j - thing.c] + thing.w);
else // 完全背包
for (int j = thing.c; j <= V; j++) f[j] = max(f[j], f[j - thing.c] + thing.w);
}
// 最大价值就是f[V];关键在于将问题分类，将多重背包转化为 01 背包，将三个问题分门别类之后，就可以按照 01 背包，完全背包的思路解决
在最初写出这三个过程的时候，可能完全没有想到它们会在这里混合应用。我想这体现了编程中抽象的威力。如果你一直就是以这种“抽象出过程”的方式写每一类背包问题的，也非常清楚它们的实现中细微的不同，那么在遇到混合三种背包问题的题目时，一定能很快想到上面简洁的解法，对吗？
小结
有人说，困难的题目都是由简单的题目叠加而来的。这句话是否公理暂且存之不论，但它在本讲中已经得到了充分的体现。本来 01 背包、完全背包、多重背包都不是什么难题，但将它们简单地组合起来以后就得到了这样一道一定能吓倒不少人的题目。但只要基础扎实，领会三种基本背包问题的思想，就可以做到把困难的题目拆分成简单的题目来解决。
5. 二维费用的背包问题
问题
算法
// 以01背包问题为例
// N为物品数量，V为最大体积，U为最大质量
// c[i],d[i],w[i]分别为第i件物品的体积,质量,价值
// f[j][k]为物品放入容量j质量k的背包可以获得的最大价值
for (int i = 1; i <= N; i++)
for (int j = V; j >= c[i]; j--)
for (int k = U; k >= d[i]; k--)
f[j][k] = max(f[j][k], f[j - c[i]][k - d[i]] + w[i]);
// 最大价值就是f[V][U];本质上来说和 01 背包问题相同，只不过加了一个维度，这样也就需要我们添加一个新的循环
物品总个数的限制
复整数域上的背包问题
另一种看待二维背包问题的思路是：将它看待成复整数域上的背包问题。也就是说，背包的容量以及每件物品的费用都是一个复整数。而常见的一维背包问题则是自然数域上的背包问题。所以说，一维背包的种种思想方法，往往可以应用于二位背包问题的求解中，因为只是数域扩大了而已。
作为这种思想的练习，你可以尝试将后文中提到的“子集和问题”扩展到二维，并试图用同样的复杂度解决。
小结
当发现由熟悉的动态规划题目变形得来的题目时，在原来的状态中加一维以满足新的限制是一种比较通用的方法。希望你能从本讲中初步体会到这种方法。
6. 分组的背包问题
当发现由熟悉的动态规划题目变形得来的题目时，在原来的状态中加一维以满足新的限制是一种比较通用的方法。希望你能从本讲中初步体会到这种方法。
问题
算法
// N为物品组数，V为最大体积
// s[i]表示第i组物品的数量
// c[i][j],w[i][j]分别为第i组第j件物品的体积,价值
// f[j]为物品放入容量j的背包可以获得的最大价值
for (int i = 1; i <= N; i++)
for (int j = V; j >= 0; j--)
for (int k = 0; k < s[i]; k++)
if (j >= v[i][k])
f[j] = max(f[j], f[j - c[i][k]] + w[i][k]);
// 最大价值就是f[V];小结
分组的背包问题将彼此互斥的若干物品称为一个组，这建立了一个很好的模型。不少背包问题的变形都可以转化为分组的背包问题（例如 7 ），由分组的背包问题进一步可定义“泛化物品”的概念，十分有利于解题。
7. 有依赖的背包问题
简化的问题
算法
较一般的问题
更一般的问题是：依赖关系以图论中“森林” 3 的形式给出。也就是说，主件的附件仍然可以具有自己的附件集合。限制只是每个物品最多只依赖于一个物品（只有一个主件）且不出现循环依赖。
解决这个问题仍然可以用将每个主件及其附件集合转化为物品组的方式。唯一不同的是，由于附件可能还有附件，就不能将每个附件都看作一个一般的 01 背包中的物品了。若这个附件也有附件集合，则它必定要被先转化为物品组，然后用分组的背包问题解出主件及其附件集合所对应的附件组中各个费用的附件所对应的价值。
事实上，这是一种树形动态规划，其特点是，在用动态规划求每个父节点的属性之前，需要对它的各个儿子的属性进行一次动态规划式的求值。这已经触及到了“泛化物品”的思想。看完 8 后，你会发现这个“依赖关系树”每一个子树都等价于一件泛化物品，求某节点为根的子树对应的泛化物品相当于求其所有儿子的对应的泛化物品之和。
// 树形dp + 分组背包
// N为物品数量，V为最大体积
// c[i],w[i]分别为第i件物品的体积,价值
// f[i][j]为选择以第i件物品为节点的子树，放入容量j的背包可以获得的最大价值
// vector<int> adj[N]; // 邻接表，每一个节点的儿子
void dfs(int x) {
// 如果要选择以x为根的子树里的节点，则必须选x，设置初始值为w[x]
for (int j = c[x]; j <= V; j++) f[x][j] = w[x];
// 把当前结点x看成是分组背包中的一个组，子节点的每一种选择看作是组内的物品
for (int i = 0; i < adj[x].size(); i++) {
int y = adj[x][i]; // y为x的子节点
dfs(y); // 以y为根再选择结点
for (int j = V - c[x]; j >= 0; j--) {
for (int k = 0; k <= j; k++) { // 遍历子节点的组合
f[x][j] = max(f[x][j], f[x][j - k] + f[y][k]);
}
}
}
}小结
用物品组的思想考虑那题中极其特殊的依赖关系：物品不能既作主件又作附件，每个主件最多有两个附件，可以发现一个主件和它的两个附件等价于一个由四个物品组成的物品组，这便揭示了问题的某种本质。
8. 泛化物品
定义
泛化物品的和
背包问题的泛化物品
9. 背包问题问法的变换
以上涉及的各种背包问题都是要求在背包容量（费用）的限制下求可以取到的最大价值，但背包问题还有很多种灵活的问法，在这里值得提一下。但是我认为，只要深入理解了求背包问题最大价值的方法，即使问法变化了，也是不难想出算法的。
例如，求解最多可以放多少件物品或者最多可以装满多少背包的空间。这都可以根据具体问题利用前面的方程求出所有状态的值（ F 数组）之后得到。
还有，如果要求的是“总价值最小”“总件数最小”，只需将状态转移方程中的 max 改成 min 即可。
下面说一些变化更大的问法。
输出方案
输出字典序最小的最优方案
// N为物品数量，V为最大体积
// c[i]为第i件物品的体积，w[i]为第i件物品的价值
// f[i][j]为前i件物品放入容量为j的背包可以获得的最大价值
for (int i = N; i >= 1; i--) {
for (int j = 0; j <= V; j++) {
f[i][j] = f[i + 1][j];
if (j >= c[i])
f[i][j] = max(f[i][j], f[i + 1][j - c[i]] + w[i]);
}
}
int val = V;
for (int i = 1; i <= N; i++) {
if (f[i][val] == f[i + 1][val - c[i]] + w[i]) {
plan.push_back(i);
val -= c[i];
}
}由于输出字典序的要求，
需要从第 n 个物品遍历到第 1 个物品，求出当前背包的最大总价值 f[1][V]
再从第 1 个物品遍历到第 n 个物品
若 f[i][j] == f[i + 1][j], 则表示 f[i][j] 是从 f[i + 1][j] 状态转移过来的
若 f[i][j] == f[i + 1][j - c[i]] + w[i]，则表示 f[i][j] 是从 f[i + 1][j - c[i]] 状态转移过来的
求方案总数
对于一个给定了背包容量、物品费用、物品间相互关系（分组、依赖等）的背包问题，除了再给定每个物品的价值后求可得到的最大价值外，还可以得到装满背包或将背包装至某一指定容量的方案总数。
最优方案的总数
这里的最优方案是指物品总价值最大的方案。以 01 背包为例。
// N为物品数量，V为最大体积
// c[i]为第i件物品的体积，w[i]为第i件物品的价值
// f[j]为物品放入容量为j的背包可以获得的最大价值
// g[j]为背包容积为j时总价值为最佳的方案数(初始化为1)
for (int i = 1; i <= N; i++) {
for (int j = V; j >= c[i]; j--) {
int val = f[j - c[i]] + w[i]; // 选择当前物品后的最大价值
if (f[j] == val)
g[j] = g[j] + g[j - c[i]]; // 若相等，方案数为两者之和
else if (val > f[j])
g[j] = g[j - c[i]]; // 若最大价值增加，则更新为选择第i个物品的方案
f[j] = max(f[j], f[j - c[i]] + w[i]);
}
}
// 最大方案数就是 g[V];f[j]为物品放入容量为 j 的背包可以获得的最大价值
g[j]为背包容积为 j 时总价值为最佳的方案数
先初始化所有的 g[i] 为 1，因为背包里什么也不装也是一种方案
如果装新物品的方案总价值更大，那么 g[j] = g[j - c[i]]
如果总价值相等，方案数为两者之和
求次优解、第 K 优解
对于求次优解、第 K优解类的问题，如果相应的最优解问题能写出状态转移方程、用动态规划解决，那么求次优解往往可以相同的复杂度解决，第 K 优解则比求最优解的复杂度上多一个系数 K 。
其基本思想是，将每个状态都表示成有序队列，将状态转移方程中的 max/min 转化成有序队列的合并。
这里仍然以 01 背包为例讲解一下。
首先看 01 背包求最优解的状态转移方程：
小结
显然，这里不可能穷尽背包类动态规划问题所有的问法。甚至还存在一类将背包类动态规划问题与其它领域（例如数论、图论）结合起来的问题，在这篇论背包问题的专文中也不会论及。但只要深刻领会前述所有类别的背包问题的思路和状态转移方程，遇到其它的变形问题，应该也不难想出算法。
触类旁通、举一反三，应该也是一个程序员应有的品质吧。
腾讯云开发者
