多重背包优化小结

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16576747.html

普通多重背包

外层枚举哪个包，中层枚举容量，内存枚举数量

for(i=1; i<=n; ++i)
	for(j=m; j>=0; --j)
		for(k=1; k*w[i]<=j && j<=s[i]; ++k)
			f[j]=max(f[j], f[j-k*w[i]]+k*v[i]); 

二进制优化

相当于把每个包拆成 $log$ 个包然后分别01背包

for(i=1; i<=n; ++i)
{
	cin>>v[i]>>w[i]>>s[i]; 
	for(j=1; j<=s[i]; j<<=1) 
		a[++k].v=v[i]*j, a[k].w=w[i]*j, s[i]-=j; 
	if(s[i]) a[++k].v=v[i]*s[i], a[k].w=w[i]*s[i]; 
}

for(...) //对a进行01背包

单调队列优化

相当于完全背包，但太久之前的要pop掉

for(i=1; i<=n; ++i)
{
	for(j=0; j<w[i]; ++j) l[j]=0, q[j][r[j]=1]=f[j], z[j][1]=0; 
	for(j=w[i]; j<=m; ++j)
	{
		while(l[j%w[i]]<r[j%w[i]] && j/w[i]-z[j%w[i]][l[j%w[i]]+1]>s[i]) ++l[j%w[i]]; 
		f[j]=max(f[j%w[i]], q[j][l[j]+1]+v[i]); 
		while((l[j%w[i]]<r[j%w[i]] && f[j]>q[j%w[i][r[j%w[i]]]])	--r[j%w[i]]; 
		q[j%w[i]][++r[j%w[i]]]=f[j]; z[j%w[i]][r[j%w[i]]]=j/w[i]; 
	}
}

没调过，不知道有没有打错