多重背包问题

多重背包也是 0-1 背包的一个变式。与 0-1 背包的区别在于每种物品有ki个，而非一个。

一个很朴素的想法就是：把「每种物品选ki次」等价转换为「有ki个相同的物品，每个物品选一次」。这样就转换成了一个 0-1 背包模型，套用上文所述的方法就可已解决。状态转移方程如下：

时间复杂度 

二进制分组优化

考虑优化。我们仍考虑把多重背包转化成 0-1 背包模型来求解。

解释

显然，复杂度中的 O(nW) 部分无法再优化了，我们只能从 O(∑ki) 处入手。为 了表述方便，我们用 Ai,j 代表第 i 种物品拆分出的第 j 个物品。

在朴素的做法中，∀j ≤ ki，Ai,j 均表示相同物品。那么我们效率低的原因主要在 于我们进行了大量重复性的工作。举例来说，我们考虑了「同时选 Ai,1, Ai,2」与 「同时选 Ai,2 , Ai,3」这两个完全等效的情况。这样的重复性工作我们进行了许多 次。那么优化拆分方式就成为了解决问题的突破口。

我们可以通过「二进制分组」的方式使拆分方式更加优美。

过程

我们可以通过「二进制分组」的方式使拆分方式更加优美。

具体地说就是令 Ai,j (j ∈ [0, ⌊log2(ki + 1)⌋ − 1]) 分别表示由 2 j 个单个物品「捆 绑」而成的大物品。特殊地，若 ki + 1 不是 2 的整数次幂，则需要在最后添加一 个由 ki − 2 ⌊log2(ki+1)⌋−1 个单个物品「捆绑」而成的大物品用于补足。

举几个例子：

6=1+2+3
8=1+2+4+1
18=1+2+4+8+3
31=1+2+4+8+16

显然，通过上述拆分方式，可以表示任意 ≤ ki 个物品的等效选择方式。将每种物 品按照上述方式拆分后，使用 0-1 背包的方法解决即可。

优化后的时间复杂度为

 实现

index = 0;
for (int i = 1; i <= m; i++) {
  int c = 1, p, h, k;
  cin >> p >> h >> k;
  while (k - c > 0) {
    k -= c;
    list[++index].w = c * p;
    list[index].v = c * h;
    c *= 2;
  }
  list[++index].w = p * k;
  list[index].v = h * k;
}

单调队列优化

这个到后面再详细讲。

下一期讲混合背包。