动态规 划水集（一） —— 背包十八讲

· · 个人记录

0.前言

我也不知道一个快要退役的人干嘛还要来整这个动态规划水集，可能只是想弥补一下四年来从来不会DP的大坑吧。。

作为最常考的DP类型——背包，貌似是最近唯一接触过得DP了，所以觉着应首当其冲的拿来讲一讲。

部分内容参照背包九讲，大部分来自做题经验，将来可能会截一些洛谷日报的内容。

1,2,3:零一，完全，多重背包

三种是个人都会写的板子，用一句话概括就是：

零一背包倒着搜，完全背包正着搜，多重背包用二的幂数量存物品再套个01背包。

就是这样，其中多重背包分割数量为 k 的物品时应从 2^0,2^1,2^2...2^k分割物品直至剩余物品数不满足下次分割，这样可以取到 1\to k 所有的数。

当然分成 k 个物品跑 01 背包也行。

4.依赖背包

金明为我们提供一道模板。

一个主件和它的附件集合实际上对应于分组背包中的一个物品组.
每个选择了主件又选择了若干附件的策略,对应这个物品组的中的一个物品.

定义如上，实际操作中可以先枚举主件，在选取主件的前提下枚举附件的可能性。

大概也没啥好说的，还有一道黄金矿工也是依赖背包的模型，按照斜率分类后应该先取近原点的才能取到远原点的，这里枚举附件就应该是递增的过程

5. 分类背包

这东西我没接触过啊。。。但事实上却是所有背包问题的起点。。

将物品分成几个组，每个组仅能至多选一个物品，问最大利益？

按照01背包的思路，我们可以把整个组看做一个物品，然后枚举每个组的所有物品找一个最大利益的，用式子表示即为：

f[j]=\sum_{k=1}^{c[i]} max(f[j],f[j-w[i][k]]+v[i][k])

先放上代码：

for (int i=1;i<=c[0];i++)
  for (int j=n;j>=0;j--)
    for (int k=1;k<=c[i];k++)
    if (j>=w[i][k]) f[j]=max(f[j],f[j-w[i][k]]+v[i][k]),ans=max(ans,f[j]);

可以注意到，我们先枚举容量再枚举每组的物品，这样可以保证对于每一个容量，组内物品最多只会保留一个当前最大的。

留一道例题，这题真好

6.混合背包

由于多重背包读入处理后就是个01，所以每个物品加个属性，分完全和01分开跑就行了。

7.二维费用背包

别看到啥二维就觉得难度上了一个档。把数组开二维，循环开二维，暴力跑就行了，用式子写就是：

f[v][u]=max \begin{Bmatrix}f[v][u],f[v-a[i]][u-b[i]]+w[i]\end{Bmatrix}

8.泛化物品背包（上）

按道理这应该放最后的，但是对于下面的树形背包，背包九讲的作者是以这玩意为基础介绍的。。。

一个泛化物品就是一个数组h[0..v]，给它费用v，可得到价值h[v]，给你一个总容量$V$的背包求最大价值。

这就是泛化背包的定义了。这其实就是个概念，可以看成是分组背包的强化版本，就是一个物品组有v+1件物品，费用v，价值h[v]，每组至多选一个的情况。事实上，泛化背包的标算就是转换成分组背包搞。。

当然，特殊地，对于以上的普通模型：

9.泛化物品的合并（下）

背包九讲原作者的意思就是说任何一个背包问题都可以把所有物品化作一个泛化物品，然后找其在[0..v]的极值，我寻思着这不是对解题啥意义都没有吗。。

这一讲真的很抽象，也许在“模型的抽象程度”这一方面已经超出了NOIP的要求，所以暂且看不懂也没关系。

这尼玛看懂了也没啥意思。。

10. 树形背包

这玩意洛谷题解都过于夸大他的难度了，李煜东的书讲的挺好。。。

题目描述：

给你N个课呈树形结构，选子课程必须选父课程，问你选M课的最大收益？

口胡分析：

以上就是树形背包板子题了，其实过程很直白，很简单。

  1. 首先套上树形DP板子：
    void dfs(int v)
{
 for (int i=fir[v];i;i=e[i].next)
 {
     int u=e[i].u; dfs(u); 
     //~~枚举子状态，选取最大值的过程~~
 }
}

然后把中间那个套一下改成背包模板就行了。。

  1. 我们可以知道题目给定的是一个森林，你要跑树形DP必须要建一个虚节点O，连接所有有向树的根，这步骤是公认的。

树形DP的通性就是他维护的子结构一定是一个子树，这样就很好定义转移方程。我们设f[i][j]为以i为根的子树，选了j节课且必选自己的最大利益。

那么显然的，初始状态即为f[i][1]=s[i]。且对于每一个子树，我们可以利用泛化物品的概念去构造一个泛化物品代替一棵子树。

对于每个子树u所控制的泛化物品A,给他分配的容量k当然指选j节课，造成了收益w[k]=f[u][k]，由于我们执行DFS之后已经搞出每个子树的信息，所以直接调用即可。

很显然，每个子树的泛化物品在~0 ~to ~(m+1)中枚举与父亲取极值后不断向上合并，最后可以汇聚成一个以虚节点O为根的总泛化物品。这应该就是DD大佬在说泛化物品时的本意。

当然我们解题时不需要这种乱七八糟的概念，我们只用把一个子树与父亲的关系看作一个分组背包，对于不同的k容量，价值应该是在子树里选j个与非该子树中选k-j个的价值。写作转移方程即为：

f[v][j]=max\begin{Bmatrix}f[v_{son}][j]+f[v][j-k]\end{Bmatrix}

这样的话，对于每棵子树的组合，只能至多选一个物品，且每棵子树只搜一次，于是就是裸的分组背包了。

void dfs(int v)
{
    for (int i=fir[v];i;i=e[i].next)
    {
        int u=e[i].u; dfs(u); 
        for (int j=m+1;j>=1;j--)  //容量VA 
            for (int k=0;k<j;k++)  //选这个子树的k节课 
                f[v][j]=max(f[v][j],f[u][k]+f[v][j-k]);
    }
}

就是这样。

11.单调队列优化背包

恶心玩意，NOIP，不可能考，打死不学。洛谷日报自己看。

前十讲都是一些板子啥的，接下来会在应用方面飙车了！

12.背包应用1——打印方案（上）

我发现洛谷日报就是抄袭背包九讲的。。

我们设g[i][j]表示当f[i][j]状态时的转移来源，g[i][j]=0即从f[i-1][j]转来的，g[i][j]=1即从f[i-1][j-v[i]]转移的.

类似这样写，应该很直观。

for(int i=n;i>=1;i--)
{
    for(int j=V;j>=c[i];j--)
    {
        if(f[j]<f[j-c[i]]+w[i])
        {
            f[j]=f[j-c[i]]+w[i];
                g[i][j]=true;///选第i件物品
        }
        else g[i][j]=false;///不选第i件物品
    }
}

打印时就这样：

for(int i=1;i<=n;i++)
{
    if(g[i][Vm])  
    {
        cout<<i<<" ";
        Vm-=c[i];//减去物品i的体积. 
    }
}

但很显然会出现有多种情况的数据，还要写spj。

13. 背包应用1——打印方案（下）

这里特别提一下打印字典序最小方案，原作者好像重点提及了，而且还不用写SPJ。

首先由于路径大小在之后的状态是从[1,n]变为[2,n]的，所以应该先把物品顺序倒放，跑的时候再根据01背包。打印的时候再正着来打印。

为了防止误解，11章的程序就是最小字典序了。

貌似这个g[i][j]的第一维不能滚？毕竟他是根据原动规状态来的。

14. 背包应用2 — —求方案总数

这个其实还是一个换背包模型的问题。。把f[j]定义为，容量为j的方案数，于是类似01背包可搞出转移方程

f[j]=\sum_{i=1}^n (f[j-v[i]]+w[i])

且初始化f[0]=1.

正常跑01即可，小A为我们提供了板子题。

15. 背包应用2 — —自然数累加问题

题目大意1：

给定一个数s，在1~to~n中，求可累加任意数等于s的方案数。

口胡分析1：

换背包模型，就是以i为容量，1为价值，求其的方案总数。。然后套一下上面那个应用板子即可。。

给个程序：

f[0]=1;
for (int i=1;i<=n;i++)
{
    for (int j=s;j>=1;j--) if (f[j]) 
        f[j]+=f[j-i]; //方案数直接加上即可
}

题目大意2：

给定一个数s，在1~to~n中，求可累加任意数大于等于s的方案数。

口胡分析2：

实质上还是背包，但是任何大于n的数我们全当n来考虑，这样最后f[n]仍为答案。

也是由于大于n的数我们当做n，所以只能采用向后刷表 的方式写DP了，给个程序：

for (int i=1;i<=st;i++)
{
    for (int j=n;j>=1;j--) 
    if (f[j]) {
        if (j+a[i]>=n) f[n]=(f[n]+f[j])%mo;
        else f[j+a[i]]=(f[j+a[i]]+f[j])%mo;  //当前和j+a[i]加上和为j的个数，向后刷表。 
    }
    f[a[i]]++;//啥都不选，f[a[i]]仍然加上 
}

16.背包应用3 ——特定选取物品顺序型

有些物品在特定的剩余背包容量下有特定的价值，那么区别于泛化物品的定义，我们要先确定贪心选取物品的顺序。

比如这道[疯狂的火神](https://www.luogu.org/problemnew/show/U47733)， 由于顺序的不确定性我们要先按照贪心策略对其排序，之后套一个$01$背包板子就行了。。 当$ W_1<W_2 $ 时， 可推出$ \frac{a_1 }{b_2} < \frac{a_2 }{b_1}

，按其排序即可。

CZH搞了个这种类型的原创题，上线后再更新。

这种DP不应该放背包专题里，可以出更多东西，但为了凑18讲就拿来了。。

17.背包应用4 ——多元背包转移

不同于混合背包，多元背包更偏向于转移方程中的混合而非物品的混合，且经常与线性DP，树形DP等毒瘤DP搭配使用。

那么在一盘CD中，可以看做一个简单的01背包，转移式

f[i][j]=max(f[i][j],f[i][j-l[k]]+1)

对于新开的CD可能，是一个线性DP，转移式：

f[i][j]=max(f[i][j],f[i-1][t]+1)

在没有题解的帮助下，我们可以用线性DP的思想得到一个简单转移式。设f[i][j]为到达(i,j)点击最小数，则：

f[i][j]=min(\sum_{j-k*x[i-1]>0} f[i-1][j-k*x[i-1]+k,f[i-1][j+y[i-1])

很明显，加上里面那重循环的话一共就有O(n^3)超时了。我们可以看出，这实质上就是一个容量为x[i-1]价值为1的物品跑完全背包，于是只要将其y值正着搜跑完全背包，之后再跑01背包就可以了（这地方用不着倒着搜，因为我们本来就是二维转移，但完全背包不用考虑第一维）。

用式子表示就是：

f[i][j]=min(min(f[i-1][j-x[i-1]],f[i][j-x[i-1]])+1,f[i-1][j+y[i-1]])

我知道很长，而且还有很多小细节。。。

18.背包应用5 ——神题集萃

你觉得我有机会写这一章吗？？

丢几道我都不会写的题，自己感受：

完。。。