完全背包问题是 01 背包问题的进阶问题，解题思路也十分经典，值得仔细研究。

问题概述

有 n 种物品和一个容量为 V 的背包，每种物品都有无限件可用。放入第 i 种物品的费用是 Ci，重量是 Wi。求将哪些物品装入背包，可使这些物品的耗费的费用总和不超过背包容量，且重量总和最大。

解题思路

数据筛选

首先，要将 Ci 大于 V 的物品剔除。 其次，对于任意正整数 i 和 j，如果有 Ci ≤ Cj 且 Wi ≥ Wj，那么可以去掉编号为 j 的物品：即从 1 到 V 有 V 个整数代表 V 个桶，每个桶内的物品其费用和桶的编号相同，最后只有每个桶内的重量最大的物品被筛选为合法数据。

写成伪代码为：

1
2
3
4

int[] bucket = new int[V + 1]
for i = 1 .. n
    if bucket[Ci] == 0 || bucket[Ci] < Wi
        bucket[Ci] = Wi

然后，再从数组 bucket 中筛选出正整数值，对应的下标为费用，数组值为重量。

基本解法

本题最基本的解法是直接转化为 01 背包问题。看似每种物品都可以放入无限多个，但是实际上还要保证物品体积之和不超过背包容量 V，所以每种物品放入的个数上限为 V / Ci 个，可以假设这个数为 Mi。这样每种物品可以拆分为 Mi 个单个的待选物品，并且它们的费用和重量都相等，物品总个数会变成 ΣMi，再对这些物品使用 01 背包算法即可。 这个解法的时间复杂度为 O(V _ ΣMi)，即 O(V _ V * Σ(1 / Ci))，在 V 数值较小的时候，这个解法没有什么大问题。但是，当 V 数值很大时，ΣMi 的值会急剧增加，计算时间也会暴增。

所以，仍然需要其他更省时的算法。

二进制分解法

实际上这个解法的拆分方法非常常用，就是将整数转换为二进制多项式，也就将原有的复杂度为 O(N) 的问题转化为复杂度为 O(logN) 的问题。 具体到本题的计算中，可以不必那么死板，一定要求出 Mi 的二进制表示法的各个位数的数值。 可以构造一个首项为 1，比例为 2 的等比数列，然后不断从 Mi 中减去数列的各项，直到剩余数字小于要减去的数列项，即 Mi = 1 + 2 + ... + 2^k + (M - 2^(k + 1) + 1)。

写成伪代码为：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

void zeroOnePack(cost, weight)
    for i = V .. cost
        dp[i] = max(dp[i], dp[i - cost] + weight)

void completePack(cost, weight)
    int m = V / cost
    int k = 1
    while m > k
        zeroOnePack(K * cost, k * weight)
        m -= k
        k *= 2
    zeroOnePack(m * cost, m * weight)

最后的解题伪代码为：

1
2
3
4

int calculate(n, V)
    for i = 1 .. n
        zeroOnePack(Ci, Wi)
    return dp[V]

最高效算法

求解 01 背包问题时的方法来重新审视本题，先写出完全背包问题的状态转移方程如下：

1
2
3
4

dp[i][j] = max{ dp[i - 1][j], dp[i-1][j - Ci] + Wi, dp[i - 1][j - 2 * Ci] + 2 * Wi ... dp[i - 1][j - Mi * Ci] + Mi * Wi) }
dp[i][j] 表示在容积为 j 的背包中放入 编号 i 的物品的情况时所有物品重量和的最大值
也就是
dp[i][j] = max{ dp[i - 1][j - k * Ci] + k * Wi (0 ≤ k ≤ Mi) }

可以看出本轮的动态规划计算也只依赖上一轮的计算，因而也可以使用一维数组简化控件复杂度。比照 01 背包问题可以得到：

1
2

dp[j] = max{ dp[j - K * Ci] + k * Wi (0 ≤ k * Ci ≤ j)}
左边的 dp[j] 表示对第 i 轮计算 dp[j] 表示本轮计算中放入容量为 j 的背包中物品重量之和的最大值，右边的则表示上一轮计算得到的最大值

那么，最终可以得到算法伪代码：

1
2
3

void completePack(cost, weight)
    for i = cost .. V
        dp[i] = max(dp[i], dp[i - cost] + weight)

这样，右边的 dp[i] 表示本轮计算不放入当前待算物品，也就是上一轮计算的结果；而 dp[i - cost] 则表示本轮计算在容积 i - cost 的结果已经计算出来后，再多放入一个本轮物品的计算结果，即保证至少放入一个本轮物品。

注意：dp[i - cost] 并不意味着只允许放入一个当前物品，因为：和 01 背包不同，循环是从左向右进行的，所以如果要放入一个以上的当前物品，则必定包含在 dp[i - cost] 的计算情况中，无需再算。

这个解法和 01 背包的解法极为相像，仅仅是状态缓存数组的再赋值方向不同，但不应该死机硬背算法伪代码，应该仔细解题思路，尤其是状态变化的递推方式。

参考

背包问题九讲