多重背包问题

题目背景：

• 有 $N$ 种物品和一个容量是 $V$ 的背包。

• 第 $i$ 种物品最多有 $s_i$ 件，每件体积是 $v_i$，价值是 $w_i$。

$v[\ \ \ ]$ 、$w[\ \ \ ]$ 用来储存”打包“后的物品的体积和价格

思路参考：01背包问题

• 为什么不参考完全背包问题： 多重背包问题 每种物品个数有限制，而 完全背包问题 没有限制。简单来说：01背包问题 其实是 多重背包问题 的一个特殊情况。

优化方式：多重背包的二进制分组优化

const int N=11010,M=2010;//log2(2000)~11,11*1000=11000；体积小于2000，所以M=2010

int f[M],v[N],w[N];
int n,m;

int main()
{
   cin>>n>>m;
   int cnt=0;
   for(int i=1;i<=n;i++)
   {
       int a,b,s;
       cin>>a>>b>>s;
       int k=1;
       while(k<=s)//二进制优化
       {
           cnt++;
           v[cnt]=k*a;
           w[cnt]=k*b;
           s-=k;
           k*=2;
       }
       if(s!=0)//最大值-小于最大值的最大2的指数，用于补齐数值到最大值
       {
           cnt++;
           w[cnt]=s*b;
           v[cnt]=s*a;
       }
    }
   n=cnt;//将n更新为二进制打包后的“物品压缩包”个数
   for(int i=1;i<=n;i++)//对压缩包进行01背包，（因为二进制使得每个物品只能选一次，因为数值是“满映射”的
   {
       for(int j=m;j>=v[i];j--)
       {
           f[j]=max(f[j],f[j-v[i]]+w[i]);
       }
   }
   cout<<f[m];


    return 0;
}