算法设计与分析总结(2) --- 背包问题

算法

---

01背包

---

定义

01背包是最简单的一类问题，它的定义如下：有N件物品和容量为V的背包，第i件物品的大小为$v_i$价值为$w_i$,现在要求选择哪些物品装入背包中使的价值最大？

基本思路

这是最简单的一类背包问题，其特点是：每种物品只有一件，可以选择放或不放。如果我们用F[i,v]来表示前 i 件物品恰放入一个容量为 v 的背包可以获得的最大价值，那么它就对应了两种情况：

case1: F[i,v]没有选择第i件物品，则此时$F[i,v]=F[i-1,v]$,表示此时获得的最大价值即为前 i-1 件物品恰放入一个容量为 v 的背包可以获得的最大价值

case2: F[i,v]选择了第i件物品，则此时$F[i,v]=F[i-1,v-v_i]+w_i$，表示此时获得的最大价值即为前 i-1 件物品恰放入一个容量为 v-$c_i$ 的背包可以获得的最大价值再加上第i件物品的价值。

然后我们只需要判断上述两种情况哪一种你能够得到更高的价值即可，于是可以得到01背包问题的状态转移方程如下：

$$F[i,v]=max(F[i-1,v],F[i-1,v-v_i]+w_i)$$

其实现的伪代码如下：

for v = 0 to V
    F[0,c] = 0;//初始化
end
for i = 1 to N
    for v = 1 to V
        if (v < vi)//表示背包剩余空间小于第i件物品
            F[i,v] = F[i-1,v]
        else
            F[i,v] = max(F[i-1,v]),F(i-1,v-vi) + wi)
        end
    end
end
return F[N,V]

优化空间复杂度

以上方法的时间和空间复杂度均为 $O(VN)$，其中时间复杂度应该已经不能再优化
了，但空间复杂度却可以优化到 $O(V)$。

先考虑上面讲的基本思路如何实现，肯定是有一个主循环 i = 1 to N，每次算出来
二维数组 F[i; 0 to V ] 的所有值。那么，如果只用一个数组 F[0 to V ]，能不能保证第 i次循环结束后 F[v] 中表示的就是我们定义的状态 F[i;v] 呢？

事实上，这要求在每次主循环中我们以 v = V to 0 的递减顺序计算 F[v],这样才
能保证计算F[v]时F[v-ci]保存的是状态是F[i-1,v-vi],伪代码如下：

for v = 0 to V
    F[v] = 0;
for i = 1 to N
    for v = V to vi
        F[v] = max(F[v]),F(v-vi) + wi)
return F[N,V]

完全背包问题

---

定义

完全背包的定义如下：有N件物品和容量为V的背包，每件物品有无限件，其中第i件物品的大小为$v_i$价值为$w_i$,现在要求选择哪些物品装入背包中使的价值最大？

基本思路

这个问题非常类似于01背包问题，所不同的是每种物品有无限件。也就是从每种物品的角度考虑，与它相关的策略已并非取或不取两种，而是有取0件、取1件、取2件......直至取 [V/vi]等多种可能。如果仍然按照解 01 背包时的思路，用F[i,v]来表示前 i 件物品恰放入一个容量为 v 的背包可以获得的最大价值，那么对应的状态转移方程则为:

$$F[i,v] = max(F[i-1,V-kv_i]+kw_i | 0 \leq kv_i \leq V)$$ 这跟 01 背包问题一样有 $O(V N)$ 个状态需要求解，但求解每个状态的时间已经不是常数了,总的复杂度可以认为是$O(VN\sum\frac{V}{vi})$，这样的消耗就比较大了。

转化为01背包

最简单的想法是，考虑到第 i 种物品最多选 ⌊V /vi⌋ 件，于是可以把第 i 种物品转
化为 ⌊V /vi⌋ 件费用及价值均不变的物品，然后求解这个 01 背包问题。这样的做法完
全没有改进时间复杂度，但这种方法也指明了将完全背包问题转化为 01 背包问题的思
路：将一种物品拆成多件只能选 0 件或 1 件的 01 背包中的物品。

更高效的转化方法是：把第 i 种物品拆成费用为 $v_i2^k$、价值为 $W_i2^k$ 的若干件物
品，其中 k 取遍满足 $v_i2^k \leq V$的非负整数。

这是二进制的思想。因为，不管最优策略选几件第i种物品，其件数写成二进制后，总可以表示成若干个 $2^k$件物品的和。这样一来就把每种物品拆成$O(log⌊V/vi⌋)$件物品，是一个很大的改进。

这个算法使用一维数组，先看伪代码：

for v = 0 to V
    F[v] = 0;
for i = 1 to N
    for v = vi to V
        F[v] = max(F[v]),F(v-vi) + wi)
return F[N,V]

你会发现，这个伪代码与 01 背包问题的伪代码只有 v 的循环次序不同而已。

为什么这个算法就可行呢？首先想想为什么 01 背包中要按照 v 递减的次序来循环。让 v 递减是为了保证第 i 次循环中的状态F[i,v]是由状态F[i-1,V-vi]递推而来。换句话说，这正是为了保证每件物品只选一次，保证在考虑“选入第i件物品”这件策略时，依据的是一个绝无已经选入第 i 件物品的子结果F[i-1,V-vi]，而现在完全背包的特点恰是每种物品可选无限件，所以在考虑“加选一件第i种物品”这种策略时，却正需要一个可能已选入第i种物品的子结果F[i,V-vi],所以就可以并且必须采用v递增的顺序循环。这就是这个简单的程序为何成立的道理。

多重背包问题

定义

多重背包的定义如下：有N件物品和容量为V的背包，其中第i件物品最多有$M_i$件，它的大小为$v_i$价值为$w_i$,现在要求选择哪些物品装入背包中使的价值最大？

基本思路

与完全被曝类似，因为对于第 i 种物品有 Mi + 1 种策略：取 0 件，取 1 件……取 Mi 件。令 F[i; v]表示前i种物品恰放入一个容量为v的背包的最大价值，则有状态转移方程：

$$F[i,v] = max(F[i-1,V-kv_i]+kw_i | 0 \leq k \leq M_i)$$ 此时复杂度为$O(VN\sum M_i)$。

转化为01背包

把第 i 种物品换成 Mi 件 01背包中的物品，则得到了物品数为 $\sum Mi$ 的 01 背包问题。直接求解之，复杂度仍然是$O(VN\sum M_i)$。

但是我们期望将它转化为 01 背包问题之后，能够像完全背包一样降低复杂度。

仍然考虑二进制的思想，我们考虑把第i种物品换成若干件物品，使得原问题中第i种物品可取的每种策略——取 0 to Mi 件——均能等价于取若干件代换以后的物品。另外，取超过 Mi 件的策略必不能出现。方法是：将第i种物品分成若干件01背包中的物品，其中每件物品有一个系数。这件物品的费用和价值均是原来的费用和价值乘以这个系数。令这些系数分别为:$1,2^1,2^2...2^k-1,M_i-2^k+1$,且 k 是满足$M_i-2^k+1 > 0$的最大整数，例如，如果 Mi为 13，则相应的k=3，这种最多取13件的物品应被分成系数分别为1，2，4，6的四件物品。这样就将第 i 种物品分成了$O(logM_i)$种物品，将原问题转化为了复杂度为$O(V \sum logM_i)$的 01 背包问题。

本文参考自《背包九讲》，更多信息请点击这里,点击Markdown原文