今天来简单聊聊动态规划中典型的背包问题。
01 背包问题
先来看看下面这样一道题目吧。
Problem Description: Many years ago, in Teddy’s hometown there was a man who was called “Bone Collector”. This man liked to collect various bones, such as dog’s, cow’s, and he also went to the grave. The bone collector had a big bag with a volume of V, and along his trip of collecting, there are a lot of bones. Obviously, different bones have different values and different volumes. Now given each bone’s value along his trip, can you calculate out the maximum total value the bone collector can get?
题目的意思大概是这样的：有一位“骨头收藏家”喜欢收集骨头，每一块骨头的体积 w[i] 和价值 v[i] 都已知，而他装骨头的袋子容量只有 V，计算他能够获得骨头的最大价值。
“背包问题”获取最大利益，乍一看确实是贪心算法，但这也是一道典型的动态规划问题。动态规划是算法设计方法之一，是用来求得最优解的数学方法。
假设我们使用一个函数 rec(i,j) 来表示“从第 i 块骨头开始拿重量不超过 j 的最大收益”，那么对于第 i 块骨头，有如下几种情况。
剩余空间 j 小于第 i 块骨头的体积，无法拿这一块骨头，那么对于从第 i+1 块骨头开始拿获得的最大收益有 rec(i,j)=rec(i+1,j)。
可以拿得下这一块骨头，选择拿或者不拿。若拿，则对于从第 i+1 块骨头开始拿获得的最大收益有 rec(i,j)=rec(i+1,j-w[i])+v[i]；若不拿，则与拿不下相同 rec(i,j)=rec(i+1,j)。而我们要选择这两者中较大的一个才算最大收益。
这样我们便得到了函数的递推关系，这种递推关系被称为“状态转移方程”，使用代码表示则为：
int rec(int i, int j) {
int res;
if (i == N)
res = 0;
else if (j < w[i])
res = rec(i + 1, j);
else
res = max(rec(i + 1, j), rec(i + 1, j - w[i]) + v[i]);
return res;
}
但是这样会产生很多重复的函数调用，特别是当 N 比较大的时候，程序运行时间会以指数形式增长。所以我们可以使用一个动态规划数组将计算过的函数值保存起来，当需要调用的时候可以直接从数组中访问。
int DP[1000][1000];
int rec(int i, int j) {
if (DP[i][j] != -1) { // 判断是否存在数据
return DP[i][j];
}
int res;
// ...
return DP[i][j] = res; // 将值记录在数组中
}
int main() {
memset(DP, -1, sizeof(DP)); // 初始化数组
}
首先在主函数中使用 memset 函数将数组初始化为 -1，为了和保存的元素做区别。函数在返回计算值的同时将值保存在数组中。
逆向递推
既然对于每一种情况的最优解都保存在了数组中，那在进行动态规划的时候，我们可以直接初始化数组。数组初始化的方法就是利用得到的状态转移方程，即递推关系，之后可以重复利用动态规划的结果，省去了多余的函数调用。
int main() {
int DP[1000][1000];
for (int i = N - 1; i >= 0; i--) {
for (int j = 0; j <= V; j++) {
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]] + v[i]);
}
}
return 0;
}
正向递推
上面的递推关系是逆向的，从最后一块骨头递推到第一块，即 i 从 N-1 到 0。我们也可以从正向递推，这时的 DP[i+1][j] 被定义为“从前 i 块骨头中选取体积不超过 j 所获取的最大收益”，递推关系写成代码如下：
int main() {
int DP[1000][1000];
for (int i = 0; i < N; i++) {
for (int j = 0; j <= V; j++) {
if (j < w[i])
DP[i + 1][j] = DP[i][j];
else
DP[i + 1][j] = max(DP[i][j], DP[i][j - w[i]] + v[i]);
}
}
return 0;
}
此外，除了运用递推方式逐项求解之外，还可以把状态转移想象成从“前 i 个物品中选取总重不超过 j 时的状态”向“前 i+1 个物品中选取总重不超过 j”和“前 i+1 个物品中选取总重不超过 j+w[i] 时的状态”的转移，于是可以实现成如下形式：
int main() {
int DP[1000][1000];
for (int i = 0; i < N; i++) {
for (int j = 0; j <= V; j++) {
DP[i + 1][j] = max(DP[i + 1][j], DP[i][j]);
if (j + w[i] <= V)
DP[i + 1][j + w[i]] = max(DP[i + 1][j + w[i]], DP[i][j] + v[i]);
}
}
return 0;
}
完全背包问题
上文所提到的可选择的物品个数有限的背包问题称为“01 背包问题”，假如可选择的每一种物品数量不限，则被称为“完全背包问题”。
若将上文题目改为每种骨头可以选择任意多的数量，就变成了一道完全背包问题。
我们还是设 DP[i+1][j] 表示“从前 i 块骨头中选取体积不超过 j 所获取的最大收益”，假设对于第 i 种骨头选了 k 块，而要选择其中收益最高的方法，则有：DP[i+1][j]=max{DP[i][j-k*w[i]]+k*v[i]|k>=0}，使用代码表示如下：
int main() {
int DP[1000][1000];
for (int i = 0; i < N; i++) {
for (int j = 0; j <= V; j++) {
for (int k = 0; k * w[i] <= j; k++) {
DP[i + 1][j] = max(DP[i][j - k * w[i]] + k * v[i], DP[i + 1][j]);
}
}
}
return 0;
}
这样多加了一层循环，使得算法的复杂度再次提升。不难发现，在 DP[i+1][j] 中选择 k (k>=1) 个与在 DP[i+1][j-w[i]] 中选择 k-1 个，计算出来的结果相同。所以选择 k (k>=1) 个的部分在之前的计算中已经得出过，那么可以简化状态转移方程。
DP[i+1][j]=max{DP[i][j-k*w[i]]+k*v[i]|k>=0}
=max(DP[i][j],max{DP[i][j-k*w[i]]+k*v[i]|k>=1})
=max(DP[i][j],max{DP[i][j-k*w[i]-w[i]]+k*v[i]+v[i]|k>=0})
=max(DP[i][j],DP[i+1][j-w[i]]+v[i])
而如上状态转移方程使用代码表示便为：
int main() {
int DP[1000][1000];
for (int i = 0; i < N; i++) {
for (int j = 0; j <= V; j++) {
if (j < w[i])
DP[i + 1][j] = DP[i][j];
else
DP[i + 1][j] = max(DP[i][j], DP[i + 1][j - w[i]]
+ v[i]);
}
}
return 0;
}