

二进制分组解多重背包

介绍¶

题目大意：有 $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 k)$ 件物品了。优化后

代码实现：

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

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：TrisolarisHD, hsfzLZH1, greyqz, Ir1d, abc1763613206, tigerruanyifan
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用

二进制分组解多重背包

介绍¶

习题¶

评论