DP查缺补漏之多重背包优化原理
普通思路
-
类似完全背包
-
for(int i=1;i<=n;i++) for(int j=1;j<=V;j++) for(int k=1;k<=V/c[i];k++) { if(k*c[i]<=j) f[i][j]=max(f[i-1][j],f[i-1][j-k*c[i]]+k*w[i]); else f[i][j]=f[i-1][j]; }
二进制拆分优化
原理
任何数都能用二进制表示,任何正整数都能由若干个不同的\(2^n\)相加得到。
做法
直接把多重背包每一个分组的物品用二进制预处理成几个大物品。
然后直接用物品跑01背包即可
代码
for(int i=1;i<=n;i++)
{
for(int j=1;j<=num[i];j<<=1)
//二进制每一位枚举.
//注意要从小到大拆分
{
num[i]-=j;//减去拆分出来的
new_c[++tot]=j*c[i];//合成一个大的物品的体积
new_w[tot]=j*w[i];//合成一个大的物品的价值
}
if(num[i])//判断是否会有余下的部分.
//就好像我们某一件物品为13,显然拆成二进制为1,2,4.
//我们余出来的部分为6,所以需要再来一份.
{
new_c[++tot]=num[i]*c[i];
new_w[tot]=num[i]*w[i];
num[i]=0;
}
}