多重背包单调队列优化（自己的理解方式）

传统的状态转移方程 f[i][j]=max(f[i][j],f[i-1][j-kv[i]]+kw[i]);

for(int i=1;i<=n;i++)  //第一重循环
        for(int j=0;j<=m;j++)  //第二重循环
            for (int k = 0; k <= s[i] && k * v[i] <= j; k ++ )  //第三重循环

考虑到对于每一层i，j 只与 j%v + kv 有关 k的范围 [ 0 , s ]
优化二三重循环,将每一层 j 按 j%v 分成v组，节省了第二重循环中 j+v…j+kv 的时间，将两重循环优化为遍历一次 m；
f[i][j]=max(f[i][j],f[i-1][j-kv[i]]+k*w[i]) 相当于求每一组在s个范围内的最大值，单调队列O（1）时间即可；

时间复杂度应该是O(nm)

C++

#include<iostream>
#include<cstring>

using namespace std;
const int N = 2e4+10;
int n,m,f[N],pre[N],q[N]//存储下标;

int main()
{
    scanf("%d%d",&n,&m);

    for(int i=0;i<n;i++)
    {
        int v,w,s;
        scanf("%d%d%d",&v,&w,&s);
        //保存i-1的状态
        memcpy(pre,f,sizeof f);
        for(int j=0;j<v;j++)
        {
            int head=0,tail=-1;
            for(int k=j;k<=m;k+=v)
            {
                //判断队列元素是否超过s+1
                if(head<=tail&&k-s*v>q[head]) head++;

                //保证队列单调 因为队内元素一定是单调的，只需比较对尾元素相应于k的价值pre[q[head]]+(k-q[head])/v*w与k的价值
                while(head<=tail&&pre[q[tail]]+(k-q[tail])/v*w<=pre[k]) tail--;

                //得到最大价值
                if(head<=tail) f[k]=max(f[k],pre[q[head]]+(k-q[head])/v*w);
                /*写成这样子也行f[k]=pre[q[head]]+(k-q[head])/v*w;因为之前已经在单调队列时比较过了,若队列中仍有元素则一定比f[i-1][k]大*/

                //入队
                q[++tail]=k;
            }
        }
    }
    printf("%d\n",f[m]);
    return 0;
}