题意
多重背包
数据范围:$0 \le w \le 4 \cdot 10^4,1 \le n \le 100$
题解
设$w$为价值,$v$为体积,$c$为数量
多重背包的状态转移方程为$$f[i][j]=\max(f[i-1][j-kv]+kw)$$其中$k \in [1,c]$
由于$i$一定从$i-1$转移而来,所以第一维可以去掉$$f[j]=\max(f[j-kv]+kw)$$
但是这样$dp$的复杂度为$O(N^3)$,需要进行优化
发现在计算$f[j]$与$f[j-v]$重复使用了较多的相同状态;而对于所有模$v$同余的$j$都存在这个问题
那么按模$v$划分:令$j=pv+d$,则
$$ \begin{aligned} f[j] &=\max(f[pv+d-kv]+kw) \\ &=\max(f[(p-k)v+d]+kw) \\ &=\max(f[(p-k)v+d]-(p-k)w)+pw \\ \end{aligned} $$
为了方便描述,将$p-k$换原为$k$
$$f[j]=\max(f[kv+d]-kw)+pw$$
其中$k \in [0,p)$
这样便可以使用单调队列优化
具体操作为:枚举每个$d$(余数),然后对于每$d$都用单调队列优化即可
代码:
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int M=4e4+10;
int n,m,w,v,c;
int hd,tl,sum;
int dp[M],mq[M],id[M];
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d%d%d",&w,&v,&c);
if(v==0){ //v=0时特殊处理
sum+=w*c;
continue;
}
int p=m/v;
c=min(c,p);
for(int d=0;d<v;d++){
hd=1,tl=0;
for(int k=0;k<=p;k++){
int t=dp[k*v+d]-k*w;
for(;hd<=tl && t>=mq[tl];tl--);
mq[++tl]=t;
id[tl]=k;
for(;hd<=tl && id[hd]<k-c;hd++);
dp[k*v+d]=max(dp[k*v+d],mq[hd]+k*w);
}
}
}
printf("%d",dp[m]+sum);
return 0;
}