GGTalk播客解析：WAMaker分享的01背包问题在算法中的应用
几天前，GGTalk 发布了一个关于算法的播客。主持人雷子和嘉宾WAMaker都分享了非常有趣的算法经验。本系列文章将帮助您梳理本期电台应该了解的知识点。
本文就讲一下WAMaker在博客中提到的01背包问题。
[11:25] WAMaker：项目中有这样的功能。从各个科目中挑选题目，组成模拟试卷……我们如何挑选题目，才能得到满分10分呢？
其实WAMaker的具体场景是：有一个题库假设有N题，每题都会有它的分数m[i]，现在我需要用这些题组成一份总分试卷，那么应该怎么做我选择。
为什么这是01背包问题？我们来对比一下原题的场景：有N件物品，一个容量为V的背包，第i件物品的成本为c[i]，体积为w[i]。解决哪些物品应该装进背包才能最大化总价值。
是不是和问题场景的问题很相似？唯一的区别是，在问题评分问题中，总分需要等于total，而在下面的背包问题中，上限只有V才能找到最大值。
为了统一问题场景，我们将积分问题视为携带一个包装好的物品，其体积和价值相等。这时候我们就要携带一个总价值为V的物品。 好了，统一了场景之后，我们来看这两种情况。
返回最大值
首先我们来看看如何记忆一个上限为V但总值最大的卷？
我们先考虑一下题目的这个特点：每一项只有一项，可以选择放或者不放。然后我会考虑每一项是否应该放置！
我们从中间状态开始。假设背包中剩余V0容量。那么我们放入第i个物品后，它的容量就变成了V1=V0-w[i]，而我们原来背包C0的总价值就变成了C1=C0+c[i]。
我们将 C1 和 C0 视为自变量，将 i 视为自变量，来思考一个函数：
F(i,w)表示从背包中的前i件物品中选择一些东西放入体积为w的背包中所产生的最大值。
由于我们在这种中间情况下已经遍历到了第 i 个项目，因此之前的状态考虑了 i - 1 个项目。所以我们从我们已经考虑了 i - 1 项这一事实开始。假设此时我们要决定是否将第i件物品放入背包中。如果没有，我们的价值就不会改变。通过上面的二元函数，我们有下面的公式：
换句话来说，对于一个体积为w的背包，考虑前i-1件物品中的最大值与考虑前i件物品中的值之和的最大值是一样的。
那么如果放入第i个项目呢？我们如何表示递归关系？如果第i项可以放下，那么肯定意味着w > w[i]。这时候我们求第i项的值。由于我们计算的是体积为w下的最大值，那么在w[体积为i的物品之后]，实际上还有一个体积为w - w[i]的背包。事实上，我们只需要知道i - 1件物品的最大值，然后再将它们放入容量为w - w[i]的背包中，加上第i件物品的价值，实际上就是F （i，w）我们要求）”
这样，我们通过 i 和体积 w 得到了这个中间情况的两个递归公式。下面我们将它们结合起来。考虑到我们的F函数代表的是包的每个状态可以放入的最大值，那么结合上面两个公式，可以推导出完整的F(i,w)表达式：
取上述两个方程的最大值，即可将i-1状态完全推导为i状态。其中，我们借用了封装的最大容量w作为状态的影响因素，因此这里结合了二维动态规划模型。这种用来表示两种状态的递归公式在动态规划中称为状态转移方程，它是动态规划问题的核心要素。一般只要确定了状态转移，基本上就可以按照这个思路编程来解决。
但如何理解这个表达呢？我花了很长时间才理解01背包的状态转移方程，最后我发现最好的理解方法就是画一张表格。
这里我举一个例子。有五个项目具有以下属性。背包的总体积为10：
看动态规划的状态转移，红色区域就是状态转移：
给出描述，例如第二行标记为红色的位置值为10，推导如下：
这个例子表明，当考虑物品a和b之间的权衡时，如果背包的最大容量为9，则可以获得的最大物品价值为10。
那么如何编写代码来实现呢？可以将上表中的行和列作为二维数组的下标，并利用上述规则完成迭代。
# 物品容积
w = [0, 4, 5, 5, 2, 2]
# 物品价值
c = [0, 6, 4, 6, 3, 6]
# 背包大小
W = 10
# 初始化 dp 状态数组
dp = [[0 for _ in range(W + 1)] for _ in range(len(w))]
for i in range(1, len(w)):
for j in range(0, W + 1):
if (j < w[i]):
dp[i][j] = dp[i - 1][j]
else:
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + c[i])
# debug
for i in range(1, len(w)):
print(dp[i])
print(f'可以装最大价值是 {dp[-1][-1]}')
"""
[0, 0, 0, 0, 6, 6, 6, 6, 6, 6, 6]
[0, 0, 0, 0, 6, 6, 6, 6, 6, 10, 10]
[0, 0, 0, 0, 6, 6, 6, 6, 6, 12, 12]
[0, 0, 3, 3, 6, 6, 9, 9, 9, 12, 12]
[0, 0, 6, 6, 9, 9, 12, 12, 15, 15, 15]
可以装最大价值是 15
"""
准确的回值
回到WAMaker所说的，如果我们想在背包中携带指定尺寸的总容量，我们该如何实现呢？
我们继续从上面的背包来看这个问题。如果我们将物体的体积视为问题的得分，则物体的价值等于物体的体积，即该场景中的得分既是体积又是价值。背包的大小等于试卷的总分，折算成01背包题。
但在背包问题中，我们最终的解是我们能够获得的最大值。在我们的场景中，我们需要获得准确的分数。这该如何处理呢？
或者你是否需要从上面的状态转变来寻找想法？
我们观察到第二行的状态值都是从第一行相同颜色对应的状态值转来的。第一行没有项目的状态是我们定义的。当没有物品时，无论背包的大小如何扩展，其值都将为0。在背包问题下，这个定义似乎很合适。但如果我们不把它当作背包容量，而是当作试卷满分，那么当试卷满分为0分时，所有试题均无效（试题分数之和等于试卷满分）总分），否则视为无效状态。
从这个角度来看，我们定义负无穷-无穷状态，并规定负无穷加上任意正数都是负无穷。这样，我们用0填充有意义的初始状态，用负无穷填充无意义的初始状态。我们看看上面的状态转换变成了什么？
这样我们就剩下足够装满背包的东西了。综上所述，我们只需要在没有项的情况下修改初始状态即可解决记忆正确值的问题。使用代码来实现：
# 物品容积
w = [0, 4, 5, 5, 2, 2]
# 物品价值
c = [0, 6, 4, 6, 3, 6]
# 背包大小
W = 10
# 初始化 dp 状态数组
dp = [[0 for _ in range(W + 1)] for _ in range(len(w))]
for i in range(1, len(dp[0])):
dp[0][i] = -1e5
for i in range(1, len(w)):
for j in range(0, W + 1):
if (j < w[i]):
dp[i][j] = dp[i - 1][j]
else:
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + c[i])
if dp[i][j] < 0:
dp[i][j] = -1e5
for i in range(1, len(w)):
for j in range(len(dp[i])):
print('-∞' if dp[i][j] < 0 else dp[i][j], '\t', end='')
print('\n')
"""
表中所有的数字都是可以正好装满时候的价值总和
0 -∞ -∞ -∞ -∞ -∞ -∞ -∞ -∞ -∞ -∞
0 -∞ -∞ -∞ 6 -∞ -∞ -∞ -∞ -∞ -∞
0 -∞ -∞ -∞ 6 4 -∞ -∞ -∞ 10 -∞
0 -∞ -∞ -∞ 6 6 -∞ -∞ -∞ 12 10
0 -∞ 3 -∞ 6 6 9 9 -∞ 12 10
0 -∞ 6 -∞ 9 6 12 12 15 15 10
"""
路径记录
在以上所有记录和解答中，虽然我们解决了背包中可容纳的最大价值以及通过广告问题可获得的总分，但我们无法查明我们具体容纳了什么物品以及收集了多少物品。获得最大值。分配总分时我们会包括哪些问题。这其实就是dp中的记录路径。
我们继续使用上面的状态转移表，以dp[5][10]的最终结果为例：
其实这里的路径分为两种情况：
同一列相当于没有添加项；
不相同的行相当于在之前的状态上添加了新的项；
我们关注第二种情况。我们在状态转移时记录这个关系标记col[i][j]，然后从后到前记录每一项的选择状态。
# 物品容积
w = [0, 4, 5, 5, 2, 2]
# 物品价值
c = [0, 6, 4, 6, 3, 6]
# 背包大小
W = 10
# 初始化 dp 状态数组
dp = [[0 for _ in range(W + 1)] for _ in range(len(w))]
# 标记数组
col = [[0 for _ in range(W + 1)] for _ in range(len(w))]
for i in range(1, len(w)):
for j in range(0, W + 1):
# 容量不够放
if (j < w[i]):
dp[i][j] = dp[i - 1][j]
else:
dp[i][j] = dp[i - 1][j]
# 如果发现从上一状态放入当前物品价值更大，则放入记录价值并记录路径
if dp[i - 1][j - w[i]] + c[i] > dp[i][j]:
dp[i][j] = dp[i - 1][j - w[i]] + c[i]
col[i][j] = 1
for i in range(0, len(w)):
for j in range(len(dp[i])):
print('-∞' if dp[i][j] < 0 else dp[i][j], '\t', end='')
print('')
print("总价值", dp[-1][-1])
# 从最后一个物品向上查询路径，即装入物品
print("选择的物品有：")
i, j = len(dp) - 1, len(dp[0]) - 1
while i > 0 and j > 0:
if col[i][j] == 1:
print(f'{i}({w[i]}, {c[i]}) ', end="")
j -= w[i]
i -= 1
"""
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 6 6 6 6 6 6 6
0 0 0 0 6 6 6 6 6 10 10
0 0 0 0 6 6 6 6 6 12 12
0 0 3 3 6 6 9 9 9 12 12
0 0 6 6 9 9 12 12 15 15 15
总价值 15
选择的物品有：
5(2, 6) 4(2, 3) 1(4, 6)
"""
实现WAMaker试卷问题的代码
上面讨论了这么多背包问题。接下来我们利用WAMaker的实际场景来编写试卷评分题的demo。假设我们要收集一份100分的试卷。我们的题目包括5分、10分、16分、20分、14分、30分、36分、40分、45分各一题。那么我们做100分试卷要如何选题呢？
我们直接将上面的问题应用到之前的01背包问题中，计算出准确的值：
# 题目分数
w = [0, 5, 10, 16, 20, 14, 30, 36, 40, 45]
c = w
# 总分
W = 100
# 初始化 dp 状态数组
dp = [[0 for _ in range(W + 1)] for _ in range(len(w))]
for i in range(1, len(dp[0])):
dp[0][i] = -1e5
# 标记数组
col = [[0 for _ in range(W + 1)] for _ in range(len(w))]
for i in range(1, len(w)):
for j in range(0, W + 1):
if (j < w[i]):
dp[i][j] = dp[i - 1][j]
else:
dp[i][j] = dp[i - 1][j]
if dp[i - 1][j - w[i]] + c[i] > dp[i][j]:
dp[i][j] = dp[i - 1][j - w[i]] + c[i]
col[i][j] = 1
dp[i][j] = -1e5 if dp[i][j] < 0 else dp[i][j]
print("总分", dp[-1][-1])
print("选择题目有：")
i, j = len(dp) - 1, len(dp[0]) - 1
while i > 0 and j > 0:
if col[i][j] == 1:
print(f'题目{i}({c[i]}分) ', end="")
j -= w[i]
i -= 1
"""
总分 100
选择题目有：
题目7(36分) 题目6(30分) 题目5(14分) 题目4(20分)
"""
至此，我们就解决了WAMaker的问题。但事实上，它并不能覆盖所有场景。在这里我问一些扩展问题：
如果某些练习属于同一类型，导致出现问题A不能出现但问题B也不能出现的场景；
有些练习是扩展练习（思考问题）。例如，问题C出现的前提是问题D已经出现；
有些练习的分数是概括的。这些练习的分数只会随着某些因素而变化，导致这些练习的分数在一定的范围内；
当然，还有更多的需求可以猜测，但是上述三个需求对应了背包问题的三个子类型：分组背包、依赖背包和广义物品。有兴趣的读者可以阅读崔天一大牛写的《背包问题九讲》，更有针对性地了解背包问题。
空间复杂度优化——滚动数组
在上面所有的代码中，为了方便大家理解，我都使用了一个二维的dp状态数组来推导所有的子状态。但实际上，在背包问题中，由于我们只需要找到一个子状态，因此中间状态在递归规则中只用于下一状态一次。所以我们可以将dp数组当做一维数组来进行空间优化。
for i in range(1, len(w)):
for j in range(W, w[i] - 1, -1):
dp[j] = max(dp[j], dp[j - w[i]] + c[i])
可以继续使用之前状态数组的推理方法，大家可以自行推演。我这里就不详细说了。
关于bitset还有一件事要说
在WAMaker的试卷题中，其实如果我们不需要对每道题要求具体分值，而只是判断已知题库中的题是否可以组合成X分的试卷，那么我们不需要维持这么重的dp阵。在这种情况下，可以使用另一种称为 bitset 的数据结构来确定对数字进行向上舍入的可行方法。
比如我们用上面的例子来计算是否可以凑成100点、103点、105点（我对Python中的bitset不太了解，所以改成了C++）。
#include
using namespace std;
int a[10] = {0, 5, 10, 16, 20, 14, 30, 36, 40, 45};
bitset<120> bs;
int main() {
bs[0] = 1;
for (int i = 1; i < 10; ++ i) {
bs |= bs << a[i];
}
cout << bs[100] << endl; // 1
cout << bs[103] << endl; // 0
cout << bs[105] << endl; // 1
}
我们可以考虑 bs |= bs