首页 > 分享 > 题解：樱花

题解：樱花

花匠小妙招
2024-11-16 04:38

题目链接

前言

这是一道混合背包的问题，其他题解讲述的十分清晰，但在多重背包的问题上大多只是使用了二进制拆分优化，本篇文章将以通俗易懂的方法讲解单调队列优化多重背包，因此默认大家已经掌握了背包的知识，推荐大家拿着笔推一推式子。

前置知识

多重背包

优先队列

什么样的 DP 可以使用单调队列优化

状态转移方程形如：

Fi=max/minj=lii−1{gj}+wili⩽li+1" role="presentation">Fi=max/minj=lii−1{gj}+wili⩽li+1

翻译成人话意思就是对于序列中的点，决策区间随着序列下标的增大从左向右进行转移，类似于一个窗口从左向右进行滑动。如果存在 i1<i2" role="presentation">i1<i2 ，且 gi1" role="presentation">gi1 劣于 gi2" role="presentation">gi2 。那么当窗口滑动到 i2" role="presentation">i2 时，i1" role="presentation">i1 永远不会成为最优决策点，此时这个点也将不用进行转移了。

一个人如果比你小还比你强，那么你就可以退役了。

对此我们可以维护一个下标递增的单调队列，使队头一直保持最优转移。每次从队尾判断，若已经不可能成为最优决策就弹出。特别的，当队头超出了所在的新区间，因为下标单调递增，以后它也不可能回到这个区间，这时我们还需要将队头弹出。这样每次转移之后，我们只需要取出队头，队头就是最优解。

保持单调性的方法非常简单，在新的队尾入队前，要先将劣于它的元素从尾部弹出；“窗口”滑动之后，要检查队头是否合法，如果不合法要从队头弹出。因此一般使用双端队列或者直接数组模拟。

单调队列优化多重背包

记总共有 N" role="presentation">N 种物品，每种物品中一个物品的体积为 Vi" role="presentation">Vi ，价值为 Wi" role="presentation">Wi ，数量为 Ci" role="presentation">Ci , Fi,j" role="presentation">Fi,j 为前 i" role="presentation">i 件物品选出总重量为 j" role="presentation">j ， DP 值表示最大价值。

容易得出多重背包的状态转移方程为：

Fi,j=max1⩽k⩽Ci{Fi−1,j−k∗Vi+k∗Wi}" role="presentation">Fi,j=max1⩽k⩽Ci{Fi−1,j−k∗Vi+k∗Wi}

这个东西看起来可能不是很清晰，我们把它分成一项一项来看：

Fi,j=max{Fi−1,j,Fi−1,j−v+w,Fi−1,j−2v+2w,⋯,Fi−1,j−kv+kw}" role="presentation">Fi,j=max{Fi−1,j,Fi−1,j−v+w,Fi−1,j−2v+2w,⋯,Fi−1,j−kv+kw}

Fi,j−v=max{Fi−1,j−v,Fi−1,j−2v+w,⋯,Fi−1,j−kv+(k−1)w,Fi−1,j−(k+1)v+kw}" role="presentation">Fi,j−v=max{Fi−1,j−v,Fi−1,j−2v+w,⋯,Fi−1,j−kv+(k−1)w,Fi−1,j−(k+1)v+kw}

⋯" role="presentation">⋯

可以发现对于任何一个 Fi,j" role="presentation">Fi,j 是由它前面的 (k+1)" role="presentation">(k+1) 项形如 Fi−1,j−k∗Vi+k∗Wi" role="presentation">Fi−1,j−k∗Vi+k∗Wi 的式子转移而来，直到背包的体积不能再用。

但是，这个队列中前面的数，每次都会增加一个 w" role="presentation">w ，所以我们需要做一些转换。

不妨设 j=k′∗Vi+d" role="presentation">j=k′∗Vi+d ，其中 k′" role="presentation">k′ 表示的是 j" role="presentation">j 重量所能装下的该物品最大数量， d" role="presentation">d 则是余数。可以得到：

Fi,j=max1⩽k⩽Ci{Fi−1,k′∗Vi+d−k∗Vi+k∗Wi}" role="presentation">Fi,j=max1⩽k⩽Ci{Fi−1,k′∗Vi+d−k∗Vi+k∗Wi}

Fi,j=max1⩽k⩽Ci{Fi−1,(k′−k)∗Vi+d+k∗Wi}" role="presentation">Fi,j=max1⩽k⩽Ci{Fi−1,(k′−k)∗Vi+d+k∗Wi}

Fi,j=max1⩽k⩽Ci{Fi−1,(k′−k)∗Vi+d+k∗Wi−k′∗Wi+k′∗Wi}" role="presentation">Fi,j=max1⩽k⩽Ci{Fi−1,(k′−k)∗Vi+d+k∗Wi−k′∗Wi+k′∗Wi}

Fi,j=max1⩽k⩽Ci{Fi−1,(k′−k)∗Vi+d+(k′−k)∗Wi}+k′∗Wi" role="presentation">Fi,j=max1⩽k⩽Ci{Fi−1,(k′−k)∗Vi+d+(k′−k)∗Wi}+k′∗Wi

对于每一种余数 d" role="presentation">d 我们可以维护一个单调队列，因为通过式子可以看出不同余数之间的状态不会互相转移，这样我们就可以在线性的时间里求出在第 i" role="presentation">i 个物品时，对于 j≡d(modVi)" role="presentation">j≡d(modVi) 的 Fi,j" role="presentation">Fi,j 最大值。

时间复杂度 O(NV)" role="presentation">O(NV) ，空间复杂度 O(NV)" role="presentation">O(NV) 。

二维数组代码：

int n,V,v[MAX],w[MAX],c[MAX];int f[MAX][MAX],q[MAX]; //数组模拟单调队列cin>>n>>V;for(int i=1;i<=n;i++)cin>>v[i]>>w[i]>>c[i];for(int i=1;i<=n;i++)for(int j=0;j<v[i];j++) //枚举余数{int head=0,tail=-1;for(int k=j;k<=V;k+=v[i]){//(j-q[tail])/v[i] 以及下面的 (j-q[head])/v[i] 对应的都是每一个k'//超出可取范围，弹出队头while(head<=tail&&(k-q[head])/v[i]>c[i]) head++;//当前队尾解劣于新解，全部弹出while(head<=tail&&f[i-1][q[tail]]+(k-q[tail])/v[i]*w[i]<=f[i-1][k]) tail--;q[++tail]=k;//每次更新直接取出队头最优解f[i][k]=f[i-1][q[head]]+(k-q[head])/v[i]*w[i];}}cout<<f[n][V];

空间上的进一步优化

虽然时间优秀了，但是空间还不够优秀。

因为第 i" role="presentation">i 层的状态只会用到第 i−1" role="presentation">i−1 层，我们可以把这个式子用优化完全背包的思路压成一维，倒着向回推一边。考虑倒序枚举背包体积，对于每种余数 d∈[0,Vi−1]" role="presentation">d∈[0,Vi−1] ，倒序循环 k=⌊(V−d)/Vi⌋∼0" role="presentation">k=⌊(V−d)/Vi⌋∼0 ,这样就可以得到一个新的状态转移方程。

Fd+k∗Vi=maxk−Ci⩽k′⩽k−1{Fd+k′∗Vi+(k−k′)∗Wi}" role="presentation">Fd+k∗Vi=maxk−Ci⩽k′⩽k−1{Fd+k′∗Vi+(k−k′)∗Wi}

这样我们就可以得到一个空间复杂度为 O(V)" role="presentation">O(V) 的更优秀算法。

一维数组代码：

int n,V,v[MAX],w[MAX],c[MAX];int f[MAX],q[MAX],g[MAX]; //数组模拟单调队列cin>>n>>V;for(int i=1;i<=n;i++)cin>>v[i]>>w[i]>>c[i];for(int i=1;i<=n;i++){memcpy(g,f,sizeof g);for(int j=0;j<v[i];j++) //枚举余数{int head=0,tail=-1;for(int k=j;k<=V;k+=v[i]){while(head<=tail&&(k-q[head])/v[i]>c[i]) head++;while(head<=tail&&g[q[tail]]+(k-q[tail])/v[i]*w[i]<=g[k]) tail--;q[++tail]=k;f[k]=g[q[head]]+(k-q[head])/v[i]*w[i];}}}cout<<f[V];

完整代码

#include<bits/stdc++.h> #define MAX 10010 using namespace std; inline int read() {int s=0,w=1;char c=getchar();while(!isdigit(c)) (c=='-')?w=-1:w=1,c=getchar();while(isdigit(c)) s=(s<<1)+(s<<3)+(c^48),c=getchar();return s*w; } int t1,t2,t3,t4,V; int n,c[MAX],w[MAX],v[MAX]; int f[MAX],g[MAX]; inline void Zerone_Bag(int i) {for(int k=V;k>=w[i];k--)f[k]=max(f[k],f[k-w[i]]+v[i]);return; } inline void Full_Bag(int i) {for(int k=w[i];k<=V;k++)f[k]=max(f[k],f[k-w[i]]+v[i]);return; } inline void Multiple_Bag(int i) {int q[MAX];memcpy(g,f,sizeof g);for(int j=0;j<w[i];j++){int head=0,tail=-1;for(int k=j;k<=V;k+=w[i]){while(head<=tail&&(k-q[head])/w[i]>c[i]) head++;while(head<=tail&&g[q[tail]]+(k-q[tail])/w[i]*v[i]<=g[k]) tail--;q[++tail]=k;f[k]=g[q[head]]+(k-q[head])/w[i]*v[i];}}return; } int main() {t1=read(),t2=read(),t3=read(),t4=read();V=(t3*60+t4)-(t1*60+t2);n=read();for(int i=1;i<=n;i++)w[i]=read(),v[i]=read(),c[i]=read();for(int i=1;i<=n;i++){if(c[i]==0) Full_Bag(i);if(c[i]==1) Zerone_Bag(i);if(c[i]>=2) Multiple_Bag(i);}cout<<f[V];return (0-0); }