动态规划之——背包DP(进阶篇)

概要说明

本文讲多重背包、混合背包以及二维费用背包，至于其他背包问题后续补充
01背包和完全背包问题：传送门

多重背包(朴素算法)

模板例题

点这里~~

思路

多重背包也是 0-1 背包的一个变式，与 0-1 背包的区别在于每种物品有 k 个，而非一个
那么我们可以在01背包的基础上，多加上一重循环，让循环遍量k从1开始循环，循环到总重W即可

code

void solve(){int n,W;cin >> n >> W;for(int i=1;i<=n;++i){cin >> w[i] >> v[i] >> s[i];}for(int i=1;i<=n;++i)for(int j=W;j>=w[i];--j)for(int k=1;k*w[i]<=j && k<=s[i];++k){f[j]=max(f[j],f[j-k*w[i]]+k*v[i]);}cout << f[W];return ;
}

很明显，这个代码的时间复杂度为$O（nWk）$
当数据过大时，这个代码很容易超时
因此我们也就衍生出了二进制优化多重背包的算法

多重背包（二进制优化）

模板例题

点这里~~

思路

我们首先确认三点：

• 我们知道转化成01背包的基本思路就是：判断每件物品我是取了你好呢还是不取你好。
• 我们知道任意一个实数可以由二进制数来表示，也就是$2^0{2}^k$其中一项或几项的和
• 这里多重背包问的就是每件物品取多少件可以获得最大价值

为什么可以进行二进制优化，我们拿苹果进行举例：
比如苹果总数为50，如果我们一个个拿，需要拿50次
假设说这时候有6个箱子，这6个箱子的容量为$1,2,4,8,16,19$(为什么有19呢，因为剩下的总数不够32，所以将剩余的苹果单独拎出来)
那么我们就可以将这50个苹果分别装在这6个箱子里面，是不是比朴素的算法快很多？

二进制优化多重背包本质上就是将个数进行拆分，由于每个数都能用二进制数来表示，所以它的时间复杂度可以降低到$O(nWlo{g}_{2}s)$
基于上述思想，我们只需要将每次拆分的物品个数和价值存入到数组中，最后套用01背包的模板即可

code

const int N=1e4+1010,M=2e3+5;
int v[N],w[N],f[M];
void solve(){int n,W;cin >> n >> W;int cnt=1;//统计数量for(int i=1;i<=n;++i){int a,b,s;cin >> a >> b >> s;for(int j=1;j<=s;j<<=1){w[cnt]=j*a;//存入重量v[cnt++]=j*b;//存入价值s-=j;//总个数减去二进制的个数}if(s){//若还有剩余w[cnt]=s*a;v[cnt++]=s*b;}}for(int i=1;i<cnt;++i)  //01背包的模板for(int j=W;j>=w[i];--j){f[j]=max(f[j],f[j-w[i]]+v[i]);}cout << f[W];return ;
}

二进制优化是将个数进行拆分，那么我们有没有其他更快的方法呢？
答案是有的：我们可以将体积进行拆分

多重背包(队列优化)

模板例题

点这里~~

思路

我们先来看一串数据：

从第二个物品开始，每个物品的价值跟物品的重量w有关系
就拿$f[9]来说，跟他有关的是f[7]、f[5]、f[3]$，这不是跟物品重量为2有很大关系吗，每次都相差物品重量的k倍关系
为什么没有1呢，因为我们可选的数量为3，$2\ast 3=6,而9>6$，说明9不可能由1转换而来，这时候队首的1就需要出队
那么我们就可以考虑用滑动窗口的思想来解决队首和队尾的问题
不了解滑动窗口可以先看这篇博客：传送门
首先定义两个指针hh(队首)，tt(队尾)
然后开3个数组$q，f，g，q数组用于存下标，f数组存答案，g数组表示的是f数组每次转移的状态$
当队首大于队尾时，说明队尾为空，不执行任何操作
若不为空，则需要判断当前重量k是否超出范围(个数s$\ast$重量w),超出则需要将队首出队
接着判断当前状态f[k] 是否比队首的状态($g[q[hh]])+(k-q[hh])/w\ast v)$
$k-q[hh]代表剩余的体积，然后除以体积w乘上价值v$
然后判断当前状态$g[k]$是否比队尾元素大，若为真则将他们一一排除
然后将当前元素存入q数组中
每次循环都需要将f的状态转移为g数组，因此我们需要用到memcpy函数

看的不是很明白？接下来看代码慢慢食用

int q[N],g[N],f[N];
void solve(){int n,W;cin >> n >> W;for(int i=1;i<=n;++i){memcpy(g,f,sizeof f);//状态转移int w,v,s;cin >> w >> v >> s;for(int j=0;j<w;++j){int hh=0,tt=-1;//队首和队尾的指针for(int k=j;k<=W;k+=w){//每次都相差w倍的关系if(hh<=tt && q[hh]<k-s*w) hh++;//判断队首是否需要出队if(hh<=tt) f[k]=max(g[k],g[q[hh]]+(k-q[hh])/w*v);//判断当前状态和队首状态加上新的价值哪个更大while(hh<=tt && g[k]>=g[q[tt]]+(k-q[tt])/w*v) tt--;//判断当前状态是否比队尾的价值更大，更大的话将他们一一排出q[++tt]=k;//入队}}}cout << f[W];return ;
}

混合背包

模板例题

点这里~~

思路

这种题目看起来很吓人，可是只要领悟了前面几种背包的中心思想，并将其合并在一起就可以了
我们可以将他们分为两类：

• 完全背包
• 多重背包(01背包相当于k为1)

那么我们只需要分别处理上面两种类型即可
遇上完全背包就套完全背包的模板，遇上01背包和多重背包就套多重背包的模板
（注意：多重背包的朴素算法会超时，因此我们在这里考虑用二进制优化和队列优化的方法来做）
接下来看代码：

code1

int f[N];
void solve(){int n,W;cin >> n >> W;for(int i=1;i<=n;++i){int w,v,s;cin >> w >> v >> s;if(s==0){//完全背包for(int j=w;j<=W;++j){f[j]=max(f[j],f[j-w]+v);}}else{if(s==-1) s=1;//01背包转换多重背包for(int k=1;k<=s;k<<=1){//二进制优化for(int j=W;j>=k*w;--j){f[j]=max(f[j],f[j-k*w]+k*v);//直接进行循环，比较大小}s-=k;//减去个数}if(s){for(int j=W;j>=s*w;--j){f[j]=max(f[j],f[j-s*w]+s*v);}}}}cout << f[W];return ;
}

如果套队列优化的多重背包的模板，实际上不需要分完全背包和多重背包
我们只需要将背包个数s设置为无穷大，这样每次都不会将队首出队，相当于无限放入物品（即完全背包）

code2

int q[N],f[N],g[N];
void solve(){int n,W;cin >> n >> W;for(int i=1;i<=n;++i){memcpy(g,f,sizeof f);int w,v,s;cin >> w >> v >> s;if(s==-1) s=1;if(s==0) s=1e6;for(int j=0;j<w;++j){int hh=0,tt=-1;for(int k=j;k<=W;k+=w){if(hh<=tt && q[hh]<k-s*w) hh++;if(hh<=tt) f[k]=max(g[k],g[q[hh]]+(k-q[hh])/w*v);while(hh<=tt && g[k]>=g[q[tt]]+(k-q[tt])/w*v) tt--;q[++tt]=k;}}}cout << f[W];return ;
}

二维费用背包

模板例题

点这里~~

思路

这种题型很明显是 0-1 背包问题的变形，可是不同的是选一个物品会消耗两种价值（容量、重量），只需在状态中增加一维存放第二种价值即可。
注意：开三维存放物品编号就不合适了，因为容易 MLE，我们可以像01背包一样，将三维压缩成二维

code

int f[105][105];
void solve(){int n,W,M;cin >> n >> W >> M;for(int i=1;i<=n;++i){int w,m,v;cin >> w >> m >> v;for(int j=W;j>=w;--j)//和01背包一样，倒着遍历for(int k=M;k>=m;--k){f[j][k]=max(f[j][k],f[j-w][k-m]+v);//相当于滚动数组，每次都在原来的状态进行新状态的转移}}cout << f[W][M];return ;
}