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;
    }
}