wzf2000 数据结构与算法教程之动态规划（2）——背包 dp
Contents
动态规划
背包 dp
背包问题是动态规划中入门级别的题目，其应用还算广泛。
一般背包就是指一个容器，然后装载物品，使得期望的某些价值最大等等。
01 背包
问题模型
有 $n$ 个价值和体积分别为 $v[i],w[i]$ 的物品（每个物品都只有一件），有一个大小为 $W$ 的背包，求问最多能在背包中装多少价值的物品。
分析
根据上讲的分析，我们先来思考状态的表示。
题目相当于算体积和不超过 $W$ 的物品的最大价值和。
不超过看上去不太好写，我们可以考虑计算体积和恰为 $W$ 的物品的最大价值和。
之后只需要对体积和为 $0 \sim W$ 求得其中的最大值即可。
设 $dp[i][j]$ 表示从前 $i$ 件物品选出体积和为 $j$ 的物品集合的最大价值。
转移十分自然：$dp[i][j]=\max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])$。
所以核心代码就是：
for (int i=1;i<=n;i++)
for (int j=0;j<=W;j++)
if (j>=w[i]) dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
else dp[i][j]=dp[i-1][j];
时间复杂度与空间复杂度均为 $O(nW)$。
优化
这样子用一个二维数组来表示状态显得冗余，我们考虑用一维数组 $dp[i]$ 表示到当前体积和为 $j$ 的物品集合的最大价值。
那么转移本身还是差不多：$dp[j]=\max(dp[j],dp[j-w[i]]+v[i])$。
但我们需要保证每件物品最多用了一次。
所以有一个巧妙的方法，就是倒着枚举 $j$，这样小的 $j$ 就不会更新给大的。
代码会变为：
for (int i=1;i<=n;i++)
for (int j=W;j>=w[i];j--)
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
甚至变得更为简单。
这样时间复杂度不变，空间复杂度降为了 $O(W)$。
完全背包
问题模型
有 $n$ 类价值和体积分别为 $v[i],w[i]$ 的物品（每个物品有无限件），有一个大小为 $W$ 的背包，求问最多能在背包中装多少价值的物品。
分析
跟上一个的区别就是每个物品可以取多次。
所以我们只需要将上面的优化算法的 $j$ 的枚举顺序重新变为正序即可。
我写的代码：
for (int i=1;i<=n;i++)
for (int j=w[i];j<=W;j++)
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
复杂度跟上面完全相同。
多重背包
问题模型
有 $n$ 类价值和体积分别为 $v[i],w[i]$ 的物品（每个物品 $m[i]$ 件），有一个大小为 $W$ 的背包，求问最多能在背包中装多少价值的物品。
分析
有点像上述两个的中间体，既不是不能多次，又不是无限次使用。
看起来十分难以直接表示状态。所以需要更进一步的状态。
考虑到每个非负整数都能用二进制表示，我们可以将 $m[i]$ 件物品分为若干部分。
取 $t_i = \lfloor \log_2(m[i]+1) \rfloor$，可以将其分为 $2^0,2^1,\cdots,2^{t_i-1},m[i] – 2^{t_i} + 1$ 这么几个部分。
这样每一个 $0 \sim m[i]$ 的整数，一定能被分成这些部分的和。
也就是说，用这些每个部分作为整体（价值和体积都乘上若干倍数），其选择方案肯定覆盖了原有的所有可能。
所以这之后就重新变为了 01 背包问题。
具体代码不再演示。
时件复杂度为 $O(n W \log M)$，空间复杂度为 $O(W)$。（$M = \max\limits_{i=1}^{n}m_i$）
优化
这种方法不是一定要掌握。
如果用 $dp[i][j]$ 表示同样的含义，容易写出转移方程：
$dp[i][j]=\max\{dp[i-1][j-k \times w[i]]+k \times v[i]\},0 \le k \le m[i]$。
这个算法的复杂度大概高的可怕。
设 $d = w[i],a = \lfloor \dfrac{j}{d} \rfloor,b = j – a \times d$。
则转移方程可改写为：
$dp[i][j]=\max\{dp[i-1][b+k \times d]-k \times v[i]\} + a \times v[i],a – m[i] \le k \le a$。
（相信大家可以自己看出来是怎么化简的）
$dp[i][j]$ 就是求 $j$ 的前面 $m[i] + 1$ 个数 $dp[i-1][b+k \times d]-k \times v[i]$ 的最大值，然后加上 $a \times v[i]$。
如果将 $dp[i][j]$ 前面所有的 $dp[i-1][b+k \times d]-k \times v[i]$ 放入一个队列，那么 $dp[i][j]$ 就是求这个队列长度不超过 $m[i] + 1$ 时，元素的最大值，再加上一个常数。所以我们希望用 $O(1)$ 的时间算出一个队列的最大值。
而这也正是单调队列所能做到的。
具体关于单调队列的内容先不讲，留待之后数据结构部分细说。
这里给一下代码：
pair<int,int> Q[M];
for (int i=1;i<=n;i++)
{
m[i]=min(m[i],W/w[i]);
for (int j=0;j<w[i];j++)
{
int head=0,tail=1;
for (int k=0;k<=(W-j)/w[i];k++)
{
int y=dp[k*w[i]+j]-k*v[i];
while (head<=tail&&Q[tail].second<=y) tail--;
Q[++tail]=make_pair(k,y);
if (Q[head].first<k-m[i]) head++;
dp[k*w[i]+j]=Q[head].second+k*v[i];
}
}
}
学过单调队列再来看这题，我们可以发现，这样做的时间复杂度应当是 $O(nW)$，空间复杂度是 $O(W)$，成功将时间复杂度优化掉了一个 $\log$。
混合背包
问题模型
每个物品都有前三个物品的三种可能数量要求，其他不变。
分析
显然可以使用多重背包直接做。
当然，如果想常数优秀，你可能还可以对于每个 $i$，特判掉 $m[i] = 1$（01 背包）和 $m[i] \times w[i] \ge W$（完全背包）的情况。
多重背包的两种方法往往都已经足够优秀。
二维费用背包
问题模型
与前面的背包问题不同的是，每个物品的体积限制变为了两维。
也就是有两个属性 $w[i]$ 和 $g[i]$，其总和分别不超过 $W$ 和 $T$。
分析
二维版 01 背包显然可以通过加一维状态解决。
设 $dp[i][j][k]$ 表示从前 $i$ 件物品选出 $w[i]$ 之和为 $j$，$g[i]$ 之和为 $k$ 的物品集合的最大价值和。
则转移显然是：
$dp[i][j][k]=\max(dp[i-1][j][k],dp[i-1][j-w[i]][k-g[i]]+v[i])$。
当然也可以倒序使得维数下降。
完全背包同理使用顺序即可，多重背包使用二进制拆分即可。
当然这里原来的优先队列方法就较难类比了。
时间复杂度应该是 $O(nWT)$ 和 $O(nWT\log M)$。
空间复杂度应该是 $O(WT)$ 或者 $O(nWT)$。
分组背包
问题模型
在 01 背包的问题基础上，对于物品有一个分组，对于同一组中的物品，至多选择一件。
分析
其实只有把原来的前 $i$ 件，换为前 $i$ 组，并且在最后枚举第 $i$ 组中的每个物品即可。
大致核心代码：
for (int i=1;i<=m;i++)//m 为组数
for (int j=W;j>=0;j--)
for (int k=1;k<=size[i];k++)
if (j>=w[i][k]) dp[j]=max(dp[j],dp[j-w[i][k]]+v[i][k]);
时空复杂度还是 $O(nW)$ 和 $O(W)$。
有依赖背包
简化问题模型
在 01 背包的问题基础上，物品间存在一些依赖关系，比如选择物品 $i$ 就必须选择物品 $j$。
这里我们先假设没有一个物品既被依赖，又依赖别的物品，并且一个物品至多依赖一个物品。
分析
对于不依赖其他物品的物品，称之为”主件“，依赖其他物品的物品，称之为”附件“。
则对于每一个主件及依赖其的 $m$ 个附件，构成了一个组合。
对于这个组合，我们有 $2^m$ 种选择方案，也就是如果转化为分组背包，这个分组中将有 $2^m$ 个物品。
但是实际上，在体积相同的情况下，我们只需要知道最大的价值即可。
那么我们可以对每个主件 $i$ 的所有附件进行一次体积上限为 $W – w[i]$ 的 01 背包得到 $dp[0 \sim W – w[i]]$，那么转化后的分组就是 $W – w[i] + 1$ 件物品，体积分别为 $k + w[i]$，价值分别为 $dp[k] + v[i]$。
这之后再进行分组背包即可。
时间复杂度大概是 $O(nW^2)$，空间复杂度大概是 $O(nW)$。
一般问题模型
一个物品可以既被依赖又依赖别的物品，也就是这些依赖关系以森林形式给出。
可以考虑从最底层开始不断向上合并，方法与简化问题模型类似，然后用这一层的 $dp$ 值和 $v[i],w[i]$ 的和作为下一层的新的一些物品。
因为这里涉及到了树形 dp 的思想，而且每个子树的物品组都类似于一个泛化物品，所以不细讲，可以在讲完树形 dp 后自行探究。
泛化物品
问题模型
每个物品的价值变为与其体积也就是费用相关的一个函数。
每次选择物品时还要选择它的体积。
也就是说一个泛化物品是一个数组 $v[i][0 \sim W]$，给出费用（体积）$c$，可得到其价值 $v[i][c]$。
可以发现，上面所有的背包问题，都可以转化成这里的泛化物品。
具体转化可以自行探究一下。
分析
对于两个泛化物品，如何选择分别的大小，使其总费用为 $j$ 时总价值最大呢？
设两个泛化物品的函数关系 $f[i]$ 和 $g[i]$，设最终合并两个泛化物品的结果为 $h[i]$。
可以轻松得到转移：
$h[j]=\max\limits_{i=0}^{j}\{f[i] + h[j-i]\}$。
而事实上，原问题其实就相当于求解 $n$ 个泛化物品的和。
所以自然只需要重复这个过程就能得出泛化物品下的背包问题做法。
一般对于较为复杂的类背包问题，就可以尝试转化为泛化物品解决。
背包问题的变化
求方案
总体思想是记录是从哪一个状态转移而来转移，如通过 $g[i]$ 表示 $dp[i]$ 的状态通过 $dp[i-w[g[i]]]+v[i]$ 转移而来。
这样只要对最终状态倒序循环，就能找出每一步的转移，即得方案。
字典序最小方案
也就是需要在转移时，对于价值相同的情况优先选择序号小的。
对于选择了物品 $1$，则问题转化为体积上限为 $W – w[1]$ 的物品 $2 \sim n$ 的背包，否则就是体积不变的物品 $2 \sim n$ 的背包。
可以发现问题总是变为 $i \sim n$ 的子问题，所以我们可以倒序加入物品。
特别注意，当 $dp[i][j]=dp[i-1][j]$ 和 $dp[i][j] = dp[i-1][j-w[i]] + v[i]$ 同时成立，优先选择后者，也就是选择物品 $i$。
求方案总数
其实就是把 $\max$ 换成 $\sum$ 即可。
初始条件 $dp[0][0] = 1$。
求最优方案数
直接加一个数组，如果更新了最大值，同步更新方案数。
如果与原来最大值相同，则加上新的方案数。
第 $k$ 优解
无非就是用一个大小不超过 $k$ 的单调下降数组来代替原来的 $dp[i][j]$ 或者 $dp[j]$。
合并时可以类比归并排序。
时间复杂度也就是乘了一个 $k$。
No Comments