单调队列优化多重背包

话不多说，进入正题。

状态计算：f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i],f[i-1][j-2*v[i]]+2*w[i],...,f[i-1][j-s*v[i]+w[i])
如上可以看出，状态可分为不买，买一个i物体，买两个i物品…买(s-1)个i物品，买s个i物品共s+1种情况。
我们发现，可以把状态分为不重不漏的v类，分别是：
0+v,0+2v,0+3v,....,0+kv
1+v,1+2v,1+3v,....,1+kv
....
r+v,r+2v,r+3v,....,r+kv

r指的是v的余数，区间0<=r<=v-1。

在遍历每一个类时，我们可以发现，因为最多选s个i物品，所以f[j]是通过不超过数量s的同类值(即模余数相同的值，所谓的同一类值)递推得到的。
这不禁让我们想到，这好像就相当于从前面长度为s的窗口中选取最大值再与f[k]进行比较,而能实现这个窗口的数据结构就是单调队列。

单调队列需要正序遍历，这时候就会发现一个问题——在计算当前状态时，会用到本层已经更新过的状态，如计算f[r+3v]时需要用到f[r+2v]，然而f[r+2v]已经在它前头被更新了。解决这个问题的办法就是使用一个backup数组，即g数组。

了解了使用单调队列的原因之后，就来看具体的实现代码。

for(int i=1;i<=n;i++)
{
    int v,w,s;
    cin>>v>>w>>s;

    memcpy(g,f,sizeof f);//更新backup数组
    for(int j=0;j<v;j++)//j为余数
    {
        int hh=0,tt=-1;
        for(int k=j;k<=m;k+=v)//遍历当前类的每一个值
        {
            if(hh<=tt&&k-s*v>q[hh]) hh++;//判断队头是否划出窗口
            if(hh<=tt) f[k]=max(f[k],g[q[hh]]+(k-q[hh])/v*w);//f[k]与最大值g[q[hh]]对比更新
            while(hh<=tt&&g[k]>=g[q[tt]]+(k-q[tt])/v*w) tt--;//注意while

            /* 
            以下是g[k]>=g[q[tt]]+(k-q[tt])/v*w的推导过程：
            g[k]+(x-k)/v*w>=g[q[tt]]+(x-q[tt])/v*w
            移项(x-k)/v*w至等式右边,得g[k]>=g[q[tt]]+(k-q[tt])/v*w
            */    
            q[++tt]=k;
        }
    }
}

最后输出f[m]即可。

总算收工啦QWQ!