acwing6. 多重背包问题 III

题目

有 N 种物品和一个容量是 V 的背包。

第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。

题解

由于这里数据范围太大，不能用以前的方法进行一一列举，所以需要用单调队列进行优化，从每个物体的体积的余数开始列举，分别求装入0_{s个物体的最大值，那么将着0}s个物体放在单调队列中即可。

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;
const int M=20010,N=1010;
int n,m,f[M],g[M],q[M];

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        int v,w,s;
        cin>>v>>w>>s;
        memcpy(g,f,sizeof f);
        for(int j=0;j<v;j++){
           int hh=0,tt=-1;
           for(int k=j;k<=m;k+=v){
               if(hh<=tt&&q[hh]<k-s*v)hh++;
               while(hh<=tt&&g[q[tt]]-(q[tt]-j)/v*w<=g[k]-(k-j)/v*w)tt--;
               q[++tt]=k;
               f[k]=g[q[hh]]+(k-q[hh])/v*w;
           }
           
       }
    }
    
    cout<<f[m]<<endl;
    
    return 0;
}