使用单调队列，可以把求解多重背包问题的复杂度进一步优化到 $O(NM)$

把状态 j 按照除以 $V_i$ 的余数分组，对每一组分别进行计算，不同组之间的状态在阶段 i 不会互相转移。

上代码

for(int i=1;i<=n;i++){
         scanf("%d%d%d",&v[i],&w[i],&c[i]);     for(int u=0;u
     
      =std::max(maxp-c[i],0);j--){             while(l<=r&&calc(q[r],u,i)<=calc(j,u,i)) r--;             q[++r]=j;         }         for(int j=maxp;~j;j--){
                 while(l<=r&&q[l]>j-1) l++;             if(l<=r)   //这句不能忘！！                f[u+j*v[i]]=std::max(f[u+j*v[i]],f[u+q[l]*v[i]]+(j-q[l])*w[i]);             if(j-c[i]-1>=0){
                     while(l<=r&&calc(q[r],u,i)<=calc(j-c[i]-1,u,i)) r--;                 q[++r]=j-c[i]-1;             }         }     } }
     

代码中的几句话有必要解释一下

for(int j=maxp-1;j>=std::max(maxp-c[i],0);j--)

这里是预处理，为了让状态能够转移到 maxp，此后队头保存的一直是 j-1 ~ j-c[i] 的最大值

while(l<=r&&q[l]>j-1) l++;

q[l]>j-1 的意义是不让 q[j] 转移到 q[j]

if(j-c[i]-1>=0){
        while(l<=r&&calc(q[r],u,i)<=calc(j-c[i]-1,u,i)) r--;         q[++r]=j-c[i]-1; }

这里的目的是更新队尾，也就是随着 j 的减小，可以从更靠前的状态转移来，但是从 j-1 ~ j-c[i] 都已经在之前更新过队尾了，所以这里更新 j-c[i]-1