多重背包问题

【问题描述】有 n 种物品和一个容量为 C 的背包。第 i 种物品的重量是 w[i]，价值是 v[i]，数量为 a[i]。求解将哪些物品装入背包可使价值总和最大。

【分析】

二进制法：按照二进制分割物品。比方说，物品 i 有13个，就可以把它分成系数为1、2、4、6，共4个

0/1背包的物品。（13＝20＋21＋22＋6）

for (int i=1;i<n;i++) { if (w*a>C)		// 如果物品够多，问题其实就是完全背包问题
{   for (int c=0;c<=C;c++)		// 完全背包
if (c>=w) f[c] = max(f[c], f[c-w] + v); } else {   int k=1, amount=a;   while (k<amount)   {    // 是否取一个重量为k×w，价值为k×v的物品？    for (int c=k*w;c>=0;c--)     if (c>=w) f[c] = max(f[c], f[c-w] + k*v);      // 继续分割    amount-=k;    k+=k;   }   // 把剩下的作为单独一个物品   for (int c=amount*w;c>=0;c--)    if (c>=w) f[c] = max(f[c], f[c-w] + amount*v); } }

时间复杂度：O(V×ålogw[i])