数据结构与算法教程之动态规划（2）——背包 dp

wzf2000
2019年11月4日

数据结构与算法教程之动态规划（2）——背包 dp

动态规划

背包 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$。

习题

Luogu 2925 干草出售

Luogu 1853 投资的最大效益

Luogu 1776 宝物筛选

Luogu 1833 樱花

Luogu 1507 NASA的食物计划

Luogu 1757 通天之分组背包

Luogu 1064 金明的预算方案

HDU 2639 Bone Collector II

HDU 3810 Magina

 教程 数据结构与算法