浅谈几类背包题
浅谈几类背包题
摘要
背包问题作为一个经典问题在动态规划中是很基础的一个部分，然而以 0-1 背包问题为原题，衍生转变出的各类题目，可以说是千变万化，当然解法也各有不同，如此就有了继续探究的价值。 本文就 4 道背包变化的题做一些探讨研究，提出本人的一些做法，希望能起到抛砖引玉的作用。
关键字
动态规划 背包 优化
正文
一、 引言
背包问题是运筹学中的一个经典的优化难题，是一个 NP-完全问题，但其有 着广泛的实际应用背景，是从生活中一个常见的问题出发展开的： 一个背包，和很多件物品，要在背包中放一些物品，以达到一定的目标。
在信息学中，把所有的数据都量化处理后，得到这样的一个问题： 0-1 背包问题：给定 n 件物品和一个背包。物品 i 的价值是 Wi ，其体积为 Vi，背包 的容量为 C。可以任意选择装入背包中的物品，求装入背包中物品的最大总价值。
在选择装入背包的物品时，对每件物品 i ，要么装入背包，要么不装入背包。 不能将物品 i 多次装入背包，也不能只装入部分物品 i （分割物品 i）。 因此，该 问题称为 0-1 背包问题。 用于求解 0-1 背包问题的方法主要有回溯算法、贪婪算法、遗传算法、禁忌 搜索算法、模拟退火算法等。
在高中阶段，我们所谓的经典 0-1 背包问题，保证了所有量化后的数据均为 正整数，即是一个特殊的整数规划问题，本文中如无特殊说明均以此为前提。其 经典的 \(O(n*C)\)动规解法是： 状态是在前 i 件物品中，选取若干件物品其体积总和不大于 j，所能获得的最大价值为 \(F_i[j]\)，当前的决策是第 i 件物品放或者不放，最终得到转移方程：
\]
\]
其中由于 Fi只与 Fi-1 有关，可以用滚动数组来节省程序的空间复杂度。以下 就是经典算法的伪代码。
FOR i: = 1 TO n
FOR j: = C DOWNTO V_i
MAX (F[j],F[j-V_i]+W_i)
END FOR
END FOR
二、 背包的基本变换
1. 完全背包
完全背包问题：
给定 n 种物品和一个背包。第 i 种物品的价值是 \(W_i\) ，其体积为 \(V_i\)，背包的容量为 C，同一种物品的数量无限多。可以任意选择装入背包中的物品， 求装入背包中物品的最大总价值。
这个问题完全可以转化为 0-1 背包问题来解决，即把第 i 种物品分割成 \((C div Vi)\)件物品，再用 0-1 背包问题的经典动规实现。 但是，这个算法的时间复杂度太高，并不能作为一种实用的方法来实现。
很容易注意到，这个问题对于 0-1 背包来说，是另一个极端，每种物 品都可以无限制地取，只要改变转移方程，就可以构造出新的算法： 状态是在前 i 种物品中，选取若干件物品其体积总和不大于 j，所能获得的最大 价值为 \(F_i[j]\)，当前的决策是第 i 件物品放（多件）或者不放，转移方程是
\]
\]
//注意第二个是 Fi而不是 Fi-1，与 0-1 背包区别仅在于此，因为允许在放过的基础上再增加一件。
这样，这个问题就有了与 0-1 背包一样时间复杂度\(O(n*C)\)的解决方法， 同样的可以用滚动数组来实现。
FOR i: = 1 TO n
FOR j: =V_i TO C
MAX(F[j], F[j-V]+W[i]) → F[j]
END FOR
END FOR
2. 多次背包
多次背包问题：给定 n 种物品和一个背包。第 i 种物品 的价值是 \(W_i\) ，其体积为 \(V_i\)，数量是 \(K_i\)件，背包的容量为 C。可以任意选择装入背包中的物品，求装入背 包中物品的最大总价值。
和完全背包一样，可以直接套用 0-1 背包问题的经典动规实现，但是 效率太低了，需要寻找更高效的算法。
首先对于第 i 种物品，不能确定放多少件才是最优的，因为并没有什么 可以证明放一件或者全放一定会更优。换句话说，最优解所需要的件数， 可能是 0 到 \(K_i\)中的任何数。
在日常生活中，如果需要能拿得出 1 到 Ki的任意整数数额的钱，往往不会带 \(K_i\)个一元钱，因为那实在是太不方便了，取而代之的是带一些 1 元 和其他一些面值各不相同的非 1 数额的钱。 这种思想完全可以运用到这道题上！
不需要把一种物品拆分成 \(K_i\) 份，而是只要物品拆分到能凑出 1 到 \(K_i\) 之间任意数量的程度就可以了。
可以证明，按照二进制的拆分能使件数达到最小，把 \(K_i\) 拆分成 \(1,2,4,\dots,2^t,K_i-2^{t-1}+1\color{yellow}\ \ \ (2^{t-2}>K_i\ge2^{t-1}\)，就一定可以满足最优解要求了。下一步， 还是用 0-1 背包的经典算法。
如此，我们得到了一个时间复杂度为\(\texttt{O}(C*\Sigma(\log_2K_i))\)的算法。
FOR i: = 1 TO n
1 → m
WHILE K_i > 0
IF m > K_i
THEN K_i → m
K_i - m → K_i
FOR j: = C DOWNTO V_i * m
MAX( F[j] , F[j-V_i*m]+W_i*m ) → F[j]
END FOR
m * 2 → m
END WHILE
END FOR
此算法还能加上一个优化，判断如果 \(K_i\)大于 C/Vi，则多出的部分是没 有意义的，可以舍去。时间复杂度就可以优化到 \(O(n*C*\log_2C)\)。由于在高中阶段碰到的题中 C 的值很有限，所以这个算法在实际应用上的效果已经 可能满足一般的需求了。 但是在下一节中，有一个更高效的解决方法.
单调队列优化☆
长度限制最大连续和问题：给出长度为 n 的序列 \(X_i\)，求这个序列中长度不超过 \(l_{\max}\)的最大连续和。
首先考虑最简单的做法，就是直接用 \(O(n*l_{\max})\)的二次循环求最大值
FOR i: = 1 TO n
0 → s
FOR j: = i DOWNTO Max( i-lmax+1 ,1)
s + Xj → s
IF s > ans THEN s → ans
END FOR
END FOR
用 \(S_i\) 记 \(X_1\) 到 \(X_i\) 的总和，就可以看到，如果确定一个端点后，要做的 就是在 S 数组的一个连续区间取一个最值，区间最值问题完全可以用线段树来实现。 但是这个题目的另一个特性是区间的长度是固定的，而且每个区间都 只需要取一次，所以我们可以用更简单的数据结构来实现——单调队列。
先来研究一下单调队列，以维护最大值为例，在满足序列中的编号递增以后，还要满足元素的值的递减。
| L | L+1 | … | R-1 | R | |
|---|---|---|---|---|---|
| 编号 | \(A_L\) | \(A_{L+1}\) | … | \(A_{R-1}\) | \(A_R\) |
| 数值 | \(B_L\) | \(B_{L+1}\) | … | \(B_{R-1}\) | \(B_R\) |
满足\(A_{i+1}>A_i>A_{i-1}\operatorname{and} B_{i-1}>B_i>B_{i+1}\ \ \color{yellow}(R>i>L)\)
单调队列除队列首元素出队列外，还需要用一定的操作来维护队列的 特殊性质。如果进入了一个新的元素(a,b)，其中 a 必然大于 \(A_R\)，但是 b 可 能会大于等于 \(B_R\)。既然 b 大于等于 \(B_R\)，而元素 R 又是要先于新元素出队 列，那么元素 R 就已经失去价值，因为接下来新元素必然都会比元素 R 更 优。所以现在就可以删除元素 R 了。
重复上面的步骤，直到前面没有元素或者满足 \(B_R>b\) 为止，再让新元素 进队列。显然，当前的队列首元素，必定是这个区间的最大值
PROCEDURE INSERT a , b
WHILE R >= L AND b > B[ R ]
DO R - 1 → R
R + 1 → R
a → A[ R ]
b → B[ R ]
END
如此完成的单调队列，虽然不能保证每一次的操作是 O(1)，但是因为 每个元素只进队列一次，并出队列一次，所以总效率是 O(n)。
当然，这道题其实就是单调队列的基本功能，而我们希望的是能把它用来优化背包问题，所以现在重新考虑 多次背包问题 。
对于第 i 种物品来说，已知体积 v，价值 w，数量 k，那么可以按照当 前枚举的体积 j 对 v 的余数把整个动规数组分成 v 份，以下是 v=3 的情况：
| j | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | … |
|---|---|---|---|---|---|---|---|---|---|---|
| \(j \mod v\) | 0 | 1 | 2 | 0 | 1 | 2 | 0 | 1 | 2 | … |
我们可以把每一份分开处理，假设余数为 d。
| 编号 | j | 0 | 1 | 2 | 3 | 4 | 5 | … |
|---|---|---|---|---|---|---|---|---|
| 对应体积 | d | d+v | \(d+2*v\) | \(d+3*v\) | \(d+4*v\) | \(d+5*v\) | … |
现在看到分组以后，编号 j 可以从 j-k 到 j-1 中的任意一个编号转移而 来（因为相邻的体积正好相差 v），这看上去已经和区间最大值有点相似了。 但是注意到由于体积不一样，显然体积大的价值也会大于等于体积小的， 直接比较是没有意义的，所以还需要把价值修正到同一体积的基础上。比 如都退化到 d，也就是说用\(F[j*v+d]- j*w\) 来代替原来的价值进入队列。 对于第 i 件物品，转移伪代码
FOR d: = 0 TO v-1 //枚举余数，分开处理
清空队列
FOR j: = 0 TO (C-d) div v //j 枚举标号，对应体积为 j*v+d
INSERT j , F[ j*v+d ] – j * w //插入队列
IF A[ L ] < j - k THEN L + 1 → L //如果队列的首元素已经失效
B[ L ] + j * w → F[ j*v+d ] //取队列头更新
END FOR
END FO
已知单调队列的效率是 O(n)，那么加上单调队列优化以后的多次背包， 效率就是 O(n*C)了。
三、 其他几类背包问题
1. 树形依赖背包（选课）☆
树形依赖背包问题：给定 n 件物品和一个背包。第 i 件物品 的价值是 \(W_i\) ，其 体积为 \(V_i\)，但是依赖于第 \(X_i\)件物品（必须选取 \(X_i\)后才能取 i，如果无依赖则 \(X_i=0\)）， 依赖关系形成森林，背包的容量为 C。可以任意选择装入背包中的物品，求装入背包中物品的最大总价值。
这道题需要在 treedp 的基础上用背包实现。
泛化物品——定义： 考虑这样一种物品，它并没有固定的费用（体积）和价值，而是它的价值随着 你分配给它的费用（体积）变化而变化。
泛化物品可以用一个一维数组来表示体积与价值的关系 Gj表示当体积 为 j 的时候，相对应的价值为 \(G_j\ \ \color{yellow}(C>=j\ge0)\)。 显然，之前的背包动规数组 \(F_i\)，就是一件泛化物品，因为 \(F_i[j]\)表示的 正是体积为 j 的时候的最大价值。同样的，多件物品也是可以合并成一件泛化物品。
泛化物品的和：
把两个泛化物品合并成一个泛化物品的运算，就是枚举体积分配给两个泛化物 品，满足： \(G[j] = \max\{ G_1[j-k] + G_2[k] \}\ \ \color{yellow} (C\ge j\ge k\ge0)\)
把两个泛化物品合并的时间复杂度是 O(C^2)。
对于具有树形依赖关系的背包问题，我们可以把每棵子树看作是一个 泛化物品，那么一棵子树的泛化物品就是子树根节点的这件物品的泛化物 品与由根所连的所有子树的泛化物品的和。 整个动规过程就是从叶子进行到根，对于每一棵子树的操作就是：
PROCEDURE DEAL i , v , w //第 i 个节点 体积为 v 价值为 w
FOR j: = v TO C //初始化这件泛化物品
w → F_i[ j ]
END FOR
FOR s: = 1 TO n
IF s 是 i 的儿子 THEN
F_i 与 F_s 的和 → F_i
END IF
END FOR
END
一次只能把两个泛化物品合并，那么要把 n 个泛化物品合并成一个就 需要 n-1 次合并，所以这个算法效率是 \(O(n*C^2+n^2)\) ，当然，其中的 \(O(n^2)\) 可以用邻接表的记边方法变成 \(O(n)\)，最终的效率就是 \(O(n*C^2)\)。
回顾经典 0-1 背包问题，在那个经典算法中，求泛化物品与一件物品 的和，只需要 O(C)的时间复杂度，推论出：
泛化物品与一件物品的和： 把一个泛化物品与一件物品合并成一个泛化物品，可以用类似于 0-1 背包经典动 规的方法求出。
\]
\]
这样的合并，时间复杂度仅为 O(C)，同样也是合并了一件物品，效率 比求两件泛化物品的和快很多。那么有没有办法用这种 O(C)的合并方式来 代替计算两个泛化物品的和来处理这道题呢？
泛化物品的并： 因为两个泛化物品之间存在交集，所以不能同时两者都取，那么我们就需要求 泛化物品的并，对同一体积，我们需要选取两者中价值较大的一者，效率 O(C)。
\(G[j] = \max\{ G_1[j] , G_2[j] \} \color{yellow}\quad(C\ge j\ge0)\)
重新考虑对以 i 为根的子树的处理，假设当前需要处理 i 的一个儿子 s。
如果我们在当前的 \(F_i\)中强制放入物品 s 后作为以 s 为根的子树的初始 状态的话，那么处理完以 s 为根的子树以后，\(F_s\)就是与 \(F_i\)有交集的泛化物 品（实际上是 \(F_s\)包含 \(F_i\)），同时，Fs必须满足放了物品 s，即 \(F_s[j]\color{yellow}\quad (V_s>j\ge0)\) 已经无意义了，而 \(F_s[j]\color{yellow}\quad(C>=j\ge V_s)\)必然包含物品 s。为了方便，经过处理以 后，在程序中规定只有\(F_s[j]\color{yellow}\quad(C-V_s\ge j\ge0)\)是合法的。
接下来只需要把 \(F_s\)与\(F_i\)的并赋给\(F_i\)，就完成了对一个儿子的处理。如 此，我们需要的总时间复杂度仅为 O(n*C)。
PROCEDURE DEAL i , C
FOR s: = 1 TO n
IF s 是 i 的儿子 THEN
Fi → Fs
DEAL s , C – Vs //背包容量减小 Vs
FOR K: =Vs TO C //求两者的并
Max ( Fi[ k ] , Fs[ k-Vs ] + Ws ) → Fi[ k ]
END FOR
END IF
END FOR
END
2. PKU3093☆
PKU3093：给定 n 件物品和一个背包，第 i 件物品的体积为 Vi，背包的容量为 C。 要求把一些物品放入背包使得剩下的物品都放不下，求方案数。
暂时先不考虑“使剩下的物品都放不下”的条件，那就是求 0-1 背包 的所有可行方案。 用 \(F_i[j]\)表示前 i 件物品中选若干件总体积为 j 的方案数，初始为 \(F_0[0]=1\)，转移方程是
\]
\]
显然这个算法的效率是 O(n*C)的，它计算了所有装放背包的方案数。
现在考虑“使剩下的物品都放不进去”的条件，如果剩下的物品中体 积最小为 v，那么方案数就是 \(\text{sum }\{ F_n[j] \}\color{yellow}\quad(C\ge j>C-v)\)。前提是我们事先确定 了剩下中体积最小的是哪个。 对体积排序后，下一步就是枚举 i 作为剩余物品中体积最小的一件。
对 于所有 \(s<i\) 的物品必须都要放入背包，对于 i 则不能放入背包，对于 s>i 的 物品做 0-1 背包可行方案的统计，将 \(\text{sum}\{ F_n[j]\}\color{yellow}\quad(C\ge j>C-V_i)\)累加到 ans。 由于每次都需要对 n-i 件物品做统计，一共统计 n 次，效率是 \(O(n^2*C)\)。
0 → sum //sum 记 1 到 i-1 的物品体积总和
FOR i: = 1 TO N
F 数组清零
1 → F[ sum ] //初始化
FOR s: = i + 1 TO N //统计可行方案数
FOR j: = C DOWNTO Vs + sum
F[ j ] + F[ j-Vs ] → F[ j ]
END FOR
END FOR
FOR k: = C DOWNTO C - Vi + 1 //累加总方案数
IF k >= sum THEN ans + F[ k ] → ans
END FOR
sum + Vi → sum
END FOR
可以发现，同一个物品多次被考虑放入背包，这样会造成时间的浪费。 观察得到，第 i 件物品共考虑了 i-1 次。每一次循环都会少一件物品。如果 把整个过程倒置，每件物品是否可以只考虑一次呢？
由于初始状态不一样，我们还需要把初始状态统一。可以让每次 \(F[0]=1\)，总容量为 \(C-sum\)。 但是只统一初始化状态还不够，因为每次的背包容量还是不同的，做 背包统计的时候，背包容量不可以是一个变值，也必须要统一，所以每次 考虑一件物品都要用最大容量 C 来更新背包。 一次操作之后要将 \(\text{sum}\{ F[j] \}\color{yellow}\quad(C-sum\ge j>C-sum-V_i , j\ge 0)\)累加到 ans。 现在，每件物品都只考虑一次，背包体积统一是 C，那么效率就变成 了 O(n*C)。
0 → sum
1 → F[ 0 ]
FOR i: = 1 TO n
sum + Vi → sum
END FOR
FOR i: = n DOWNTO 1
sum - Vi → sum
FOR j: = C - sum DOWNTO Max( C – sum – Vi + 1 , 0 )//累加总方案数
ans + F[ k ] → ans
END FOR
FOR j: = C DOWNTO Vi //考虑第 i 件物品放入背包
F[ j ] + F[ j – Vi ] → F[ j ]
END FOR
END FOR
四、 总结
回顾全文的四道背包题：
- 对于完全背包问题，用转化方程就解决了；
- 对于多次背包，使用了单调队列优化来实现 \(O(n*C)\)的效率；在树形依赖背包问题中，探索了新的概念，最终完成算法的转化；
- 在 PKU3093 一题中，通过合并相似 操作来达到优化的效果。 虽然用到的方法各不相同，每个方法都不仅仅限于背包问题，完全可以灵 活运用到其他问题中。
- 文中提到的问题最后都用时间复杂度 O(n*C)的算法解决了，这并不是 说所有背包题都可以优化到这个程度，但是，可以肯定的是不会有比这个更快的 效率了。
- 就目前来说，背包类的题目还有很多没有得到很好的解决，等待着大家去 继续探索研究。