跳转至

二进制分组解多重背包

二进制分组解多重背包

例题经典问题 - 多重背包

题目大意:有 n 种物品,每种物品有 a_i 件,购买一件这种物品的费用为 c_i ,价值为 v_i 。有一个容量为 t 的背包,现在让你找到最优的一种方案,使得装入背包的物品的总价值最大。

考虑常规的动规方式,定义 f_{i,j} 为当前考虑到第 i 个物品,背包容量为 j 所能获得的最大价值。

状态转移方程为, f_{i,j}=\max\{f_{i-1,j},f_{i-1,j-c_i}+v_i\}

对于 每件 物品,都要这样循环一次,时间复杂度为 t\times \sum_{i=1}^n a_i ,某些时候可能不可接受,需要优化。

考虑这样一种情况,如果我们有 17 个硬币,要去买 1 17 元钱的物品,只需将这些硬币打包成 1,2,4,8 2 这样的几包。前面的 4 包能保证覆盖 1 15 所有的情况,最后一包在之前的基础上再加上一个值,能保证实现支付的时候取整包,肯定能保证支付。这就是二进制优化的原理和基本思想。

用上述的方法,就可以把 k 件相同的物品看作是 O(log_2 k) 件物品了。优化后

代码实现:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
for (int i = 1; i <= n; i++) {
  scanf("%d", a + i);
  tot += c[i] * a[i];
  for (int j = 1; j <= a[i]; j *= 2)
    if (a[i] >= j) a[i] -= j, v[++cur] = c[i] * j;
  if (a[i]) v[++cur] = c[i] * a[i];
}
for (int i = 1; i <= cur; i++)
  for (int j = m; j >= v[i]; j--)
    if (f[j - v[i]]) f[j] = true;

几道练习题

HDU 2844 Coins


评论