题目描述
有$N$种物品和一个容量是$V$的背包。第$i$种物品最多有$s_i$件,每件体积是$v_i$,价值是$w_i$
求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。
输出最大价值。
单调队列优化多重背包
时间复杂度 $O(N*V)$
首先我们不妨先看一下多重背包的暴力dp转移方程:
$f[j]=max(f[j],f[j-k\cdot v[i]]+k\cdot w[i])(0\le k\le s[i])$
也就是说会对$f[j]$产生贡献的只有可能是$f[j-v[i]],f[j-2\cdot v[i]]\cdots f[j-k\cdot v[i]]$
所以我们可以把$f[j]$按照$\mod v[i]$的余数来分类 每一类只能在自己的类里进行转移 互相不受影响
即令$f[j]=f[u+p \cdot v[i]]$ 那么能对$f[j]$产生贡献的$f[k]$满足条件$p-s[i]\le k\le p-1$
这是很显然的 因为第$i$件物品最多选$s[i]$个 那么转移方程便可以写成如下形式:
$f[u+p\cdot v[i]]=max_{p-s[i]\le k\le p-1}(f[u+k\cdot v[i]]+(p-k)\cdot w[i])(0\le u<v[i])$
我们注意到在每一层中$u$和$i$是定值 我们每次考虑到$p$时都需要找到一个最小的$k$ 所以不妨把$p$剥离出来
即$f[u+p\cdot v[i]]=max_{p-s[i]\le k\le p-1}(f[u+k\cdot v[i]]-k\cdot w[i])+p\cdot w[i]$
由于我们需要倒序处理(由01背包可知)而我们的$p$每次减少一位 会多一个新决策$p-s[i]-1$并且大于$p-1$的老决策会过期
所以我们可以倒着建立一个单调队列保存$f[u+k\cdot v[i]]-k\cdot w[i]$最大值 一开始首先算出$maxp=\frac{V-u}{s[i]}$
然后把$[maxp-s[i],maxp-1]$个决策先加入单调队列 之后每次考虑完当前的$p$ 我们便把$p-s[i]-1$考虑加入单调队列 每次到当前$p$ 我们首先把大于$p-1$的决策出队 之后假如队头存在便更新$f$的值 对于每一件物品都这样考虑 由于单调队列是线性的 所以最终的时间复杂度就是$O(N\cdot v_{max})=O(N\cdot V)$
参考文献
《算法竞赛进阶指南》
C++ 代码
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;
const int maxn=20050;
int N,V;
int v[maxn],w[maxn],s[maxn],q[maxn],f[maxn];
inline int read()
{
int x=0,t=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')t=-1;ch=getchar();}
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return x*t;
}
int calc(int u,int k,int i){return f[u+k*v[i]]-k*w[i];}
int main()
{
N=read(),V=read();
for(int i=1;i<=N;i++) v[i]=read(),w[i]=read(),s[i]=read();
for(int i=1;i<=N;i++)
{
for(int u=0;u<v[i];u++)
{
int maxp=(V-u)/v[i];
int hh=1,tt=0;q[1]=0;
for(int k=maxp-1;k>=max(0,maxp-s[i]);k--)
{
while(hh<=tt&&calc(u,q[tt],i)<=calc(u,k,i)) tt--;
q[++tt]=k;
}
for(int p=maxp;p>=0;p--)
{
while(hh<=tt&&q[hh]>p-1) hh++;
if(hh<=tt) f[u+p*v[i]]=max(f[u+p*v[i]],calc(u,q[hh],i)+p*w[i]);
if(p-s[i]-1>=0)
{
while(hh<=tt&&calc(u,q[tt],i)<=calc(u,p-s[i]-1,i)) tt--;
q[++tt]=p-s[i]-1;
}
}
}
}
cout<<f[V]<<endl;
return 0;
}
前辈还有一个 问题
“我们注意到在每一层中u和i是定值 我们每次考虑到p时都需要找到一个最小的k 所以不妨把p剥离出来”
u 和 i是定值我明白 那 什么叫找最小的k
噢,这个是当时书写的问题)我的意思是$p\cdot w[i]$在同一个循环中大家都是这样,所以可以提取出来,然后只剩下$f-k$,这个是与k相关的,我们只要在单调队列中找到$f-k$这个最小的值加上$p\cdot w[i]$即可,也就是说$p\cdot w[i]$是与决策无关的,我们找到最优决策再加上这个就好了
透彻,膜拜
前辈 “也就是说会对f[j]f[j]产生贡献的只有可能是f[j−v[i]],f[j−2⋅v[i]]⋯f[j−k⋅v[i]]f[j−v[i]],f[j−2⋅v[i]]⋯f[j−k⋅v[i]]
所以我们可以把f[j]f[j]按照modv[i]modv[i]的余数来分类 每一类只能在自己的类里进行转移 互相不受影响”
这句话不理解 能指点一下吗
因为对于体积$j$,它只会从$j-v[i],\cdots, j-k\cdot v[i]$转移过来,这个看状态转移方程能看出来,因为这些体积都是在$j$的基础上减了一些$v[i]$,所以它们模$v[i]$的值是相同的,而假如模$v[i]$值不同相互不会转移,所以可以把模相等的分成一组,它们只能组内转移@子非余安知余之美也