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

数据结构与算法教程之动态规划(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$。

习题

Luogu 2925 干草出售

Luogu 1853 投资的最大效益

Luogu 1776 宝物筛选

Luogu 1833 樱花

Luogu 1507 NASA的食物计划

Luogu 1757 通天之分组背包

Luogu 1064 金明的预算方案

HDU 2639 Bone Collector II

HDU 3810 Magina

 

点赞 0

No Comments

Add your comment