题目6. 多重背包问题 III题目描述有N NN种物品和一个容量是V VV的背包。第i ii种物品最多有s i s_isi​件每件体积是v i v_ivi​价值是w i w_iwi​。求解将哪些物品装入背包可使物品体积总和不超过背包容量且价值总和最大。输出最大价值。输入格式第一行两个整数N V ( 0 N ≤ 1000 , 0 V ≤ 20000 ) NV (0N≤1000, 0V≤20000)NV(0N≤1000,0V≤20000)用空格隔开分别表示物品种数和背包容积。接下来有N NN行每行三个整数v i , w i , s i v_i,w_i,s_ivi​,wi​,si​用空格隔开分别表示第i ii种物品的体积、价值和数量。输出格式输出一个整数表示最大价值。数据范围0 N ≤ 1000 0N≤10000N≤10000 V ≤ 20000 0V≤200000V≤200000 v i , w i , s i ≤ 20000 0v_i,w_i,s_i≤200000vi​,wi​,si​≤20000时空限制1s / 128MB输入样例4 5 1 2 3 2 4 1 3 4 3 4 5 2输出样例10代码1二维数组#includebits/stdc.husingnamespacestd;constintN100010,M2000010;intn,V,v,w,s,f[N][M],q[M],hh,tt;intmain(){cinnV;for(inti1;in;i){cinvws;for(intr0;rv;r){//枚举余数hh0,tt-1;for(intjr;jV;jv){//枚举体积while(hhttj-q[hh]s*v)hh;//超出滑动窗口长度while(hhttf[i-1][q[tt]](j-q[tt])/v*wf[i-1][j])tt--;q[tt]j;f[i][j]f[i-1][q[hh]](j-q[hh])/v*w;}}}coutf[n][V];return0;}代码2一维数组#includeiostream#includecstringusingnamespacestd;constintMaxV2000010;intN,V,f[MaxV],g[MaxV],q[MaxV];intmain(){cinNV;for(inti1;iN;i){intv,w,s;cinvws;memcpy(g,f,sizeoff);for(intj0;jv;j){inthh0,tt-1;for(intkj;kV;kv){if(hhttq[hh]k-s*v){// 假如队列窗口已满则队首出列hh;}/* 若队内有值该值就是前k个元素的最大值 (k - q[hh]) / v 表示拿取物品的数量相当于最原始的多重背包dp的k q[hh]为队首元素g[]中前k个数中最大值的下标g[]为dp[i-1][] 所以 g[q[hh]]为只考虑前i-1个物品时拿前q[hh]个物品的最大价值 */if(hhtt){f[k]max(f[k],g[q[hh]](k-q[hh])/v*w);}/* 若队尾元素小于当前元素则队尾元素出队 若队内一个元素比当前元素小则该元素一定不会被用到单调队列思想 g[q[tt]] (k - q[tt]) / v * w 与 g[k] - (k - j) / v * w 分别表示队尾元素的值和当前元素的值 */while(hhttg[q[tt]]-(q[tt]-j)/v*wg[k]-(k-j)/v*w){tt--;}//去除了比当前小的元素保证队列里的元素都比当前元素大入队q[tt]k;}}}coutf[V];return0;}结果