1、背包问题九讲目录第一讲 01背包问题第二讲 完全背包问题第三讲 多重背包问题第四讲 混合三种背包问题第五讲 二维费用的背包问题第六讲 分组的背包问题第七讲 有依赖的背包问题第八讲 泛化物品第九讲 背包问题问法的变化附录一：USACO 中的背包问题附录二：背包问题的搜索解法P01: 01背包问题题目有 N 件物品和一个容量为 V 的背包。第 i 件物品的费用是 ci，价值是 wi。求解将哪些物品装入背包可使价值总和最大。基本思路这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。用子问题定义状态：即 fiv表示前 i 件物品恰放入一个容量为 v 的背包可以获得的最大价值。则其状态转
2、移方程便是：fiv=maxfi-1v,fi-1v-ci+wi这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下：“将前 i 件物品放入容量为 v 的背包中”这个子问题，若只考虑第 i 件物品的策略（放或不放） ，那么就可以转化为一个只牵扯前 i-1件物品的问题。如果不放第i 件物品，那么问题就转化为 “前 i-1件物品放入容量为 v 的背包中”，价值为 fi-1v；如果放第 i 件物品，那么问题就转化为 “前 i-1件物品放入剩下的容量为 v-ci的背包中” ，此时能获得的最大价值就是 fi-1v-ci再加上通过放入第 i 件物品获得的价值 wi。
3、优化空间复杂度以上方法的时间和空间复杂度均为 O(VN)，其中时间复杂度应该已经不能再优化了，但空间复杂度却可以优化到 O。先考虑上面讲的基本思路如何实现，肯定是有一个主循环 i=1.N，每次算出来二维数组 fi0.V的所有值。那么，如果只用一个数组 f0.V，能不能保证第 i 次循环结束后 fv中表示的就是我们定义的状态 fiv呢？fiv 是由 fi-1v和 fi-1v-ci两个子问题递推而来，能否保证在推 fiv时（也即在第 i 次主循环中推 fv时）能够得到 fi-1v和 fi-1v-ci的值呢？事实上，这要求在每次主循环中我们以 v=V.0的顺序推 fv，这样才能保证推 fv时 fv-
4、ci保存的是状态 fi-1v-ci的值。伪代码如下：for i=1.Nfor v=V.0fv=maxfv,fv-ci+wi;其中的 fv=maxfv,fv-ci一句恰就相当于我们的转移方程 fiv=maxfi-1v,fi-1v-ci，因为现在的 fv-ci就相当于原来的 fi-1v-ci。如果将 v 的循环顺序从上面的逆序改成顺序的话，那么则成了 fiv由 fiv-ci推知，与本题意不符，但它却是另一个重要的背包问题 P02最简捷的解决方案，故学习只用一维数组解01背包问题是十分必要的。事实上，使用一维数组解01背包的程序在后面会被多次用到，所以这里抽象出一个处理一件01背包中的物品过程，以后
5、的代码中直接调用不加说明。过程 ZeroOnePack，表示处理一件01背包中的物品，两个参数 cost、weight 分别表明这件物品的费用和价值。procedure ZeroOnePack(cost,weight)for v=V.costfv=maxfv,fv-cost+weight注意这个过程里的处理与前面给出的伪代码有所不同。前面的示例程序写成 v=V.0是为了在程序中体现每个状态都按照方程求解了，避免不必要的思维复杂度。而这里既然已经抽象成看作黑箱的过程了，就可以加入优化。费用为 cost 的物品不会影响状态 f0.cost-1，这是显然的。有了这个过程以后，01背包问题的伪代码就可
6、以这样写：for i=1.NZeroOnePack(ci,wi);初始化的细节问题我们看到的求最优解的背包问题题目中，事实上有两种不太相同的问法。有的题目要求“恰好装满背包”时的最优解，有的题目则并没有要求必须把背包装满。一种区别这两种问法的实现方法是在初始化的时候有所不同。如果是第一种问法，要求恰好装满背包，那么在初始化时除了 f0为0其它 f1.V均设为-，这样就可以保证最终得到的 fN是一种恰好装满背包的最优解。如果并没有要求必须把背包装满，而是只希望价格尽量大，初始化时应该将 f0.V全部设为0。为什么呢？可以这样理解：初始化的 f 数组事实上就是在没有任何物品可以放入背包时的合法状态
7、。如果要求背包恰好装满，那么此时只有容量为0的背包可能被价值为0的nothing“恰好装满 ”，其它容量的背包均没有合法的解，属于未定义的状态，它们的值就都应该是- 了。如果背包并非必须被装满，那么任何容量的背包都有一个合法解“什么都不装”，这个解的价值为0，所以初始时状态的值也就全部为0了。这个小技巧完全可以推广到其它类型的背包问题，后面也就不再对进行状态转移之前的初始化进行讲解。一个常数优化前面的伪代码中有 for v=V.1，可以将这个循环的下限进行改进。由于只需要最后 fv的值，倒推前一个物品，其实只要知道 fv-wn即可。以此类推，对以第 j 个背包，其实只需要知道到 fv-sumw
8、j.n即可，即代码中的for i=1.Nfor v=V.0可以改成for i=1.nbound=maxV-sumwi.n,cifor v=V.bound这对于 V 比较大时是有用的。小结01背包问题是最基本的背包问题，它包含了背包问题中设计状态、方程的最基本思想，另外，别的类型的背包问题往往也可以转换成01背包问题求解。故一定要仔细体会上面基本思路的得出方法，状态转移方程的意义，以及最后怎样优化的空间复杂度。P02: 完全背包问题题目有 N 种物品和一个容量为 V 的背包，每种物品都有无限件可用。第 i 种物品的费用是 ci，价值是 wi。求解将哪些物品装入背包可使这些物品的费用总和不超过背包
9、容量，且价值总和最大。基本思路这个问题非常类似于 01背包问题，所不同的是每种物品有无限件。也就是从每种物品的角度考虑，与它相关的策略已并非取或不取两种，而是有取0件、取1件、取2件等很多种。如果仍然按照解01背包时的思路，令 fiv表示前 i 种物品恰放入一个容量为 v 的背包的最大权值。仍然可以按照每种物品不同的策略写出状态转移方程，像这样：1. fiv=maxfi-1v-k*ci+k*wi|0=wj，则将物品 j 去掉，不用考虑。这个优化的正确性显然：任何情况下都可将价值小费用高得 j 换成物美价廉的 i，得到至少不会更差的方案。对于随机生成的数据，这个方法往往会大大减少物品的件数，从而
10、加快速度。然而这个并不能改善最坏情况的复杂度，因为有可能特别设计的数据可以一件物品也去不掉。这个优化可以简单的 O(N2)地实现，一般都可以承受。另外，针对背包问题而言，比较不错的一种方法是：首先将费用大于 V 的物品去掉，然后使用类似计数排序的做法，计算出费用相同的物品中价值最高的是哪个，可以 O(V+N)地完成这个优化。这个不太重要的过程就不给出伪代码了，希望你能独立思考写出伪代码或程序。转化为01背包问题求解既然01背包问题是最基本的背包问题，那么我们可以考虑把完全背包问题转化为01背包问题来解。最简单的想法是，1.考虑到第 i 种物品最多选 V/ci件，于是可以把第 i 种物品转化为
11、V/ci件费用及价值均不变的物品，然后求解这个01 背包问题。这样完全没有改进基本思路的时间复杂度，但这毕竟给了我们将完全背包问题转化为01背包问题的思路：将一种物品拆成多件物品。更高效的转化方法是：把第 i 种物品拆成费用为2 . ci*2k、价值为 wi*2k 的若干件物品，其中 k 满足 ci*2k0的最大整数。例如，如果 ni为13，就将这种物品分成系数分别为1,2,4,6的四件物品。分成的这几件物品的系数和为 ni，表明不可能取多于 ni件的第 i 种物品。另外这种方法也能保证对于0.ni间的每一个整数，均可以用若干个系数的和表示，这个证明可以分0.2k-1和2k.ni两段来分别讨论
12、得出，并不难，希望你自己思考尝试一下。这样就将第 i 种物品分成了 O(log ni)种物品，将原问题转化为了复杂度为O(V*log ni)的01背包问题，是很大的改进。下面给出 O(log amount)时间处理一件多重背包中物品的过程，其中 amount 表示物品的数量：procedure MultiplePack(cost,weight,amount)if cost*amount=VCompletePack(cost,weight)returninteger k=1while kamountZeroOnePack(k*cost,k*weight)amount=amount-kk=k*2Z
13、eroOnePack(amount*cost,amount*weight)希望你仔细体会这个伪代码，如果不太理解的话，不妨翻译成程序代码以后，单步执行几次，或者头脑加纸笔模拟一下，也许就会慢慢理解了。O(VN)的算法多重背包问题同样有 O(VN)的算法。这个算法基于基本算法的状态转移方程，但应用单调队列的方法使每个状态的值可以以均摊 O(1)的时间求解。由于用单调队列优化的 DP 已超出了 NOIP 的范围，故本文不再展开讲解。我最初了解到这个方法是在楼天成的“ 男人八题”幻灯片上。小结这里我们看到了将一个算法的复杂度由 O(V*ni)改进到 O(V*log ni)的过程，还知道了存在应用超出
14、 NOIP 范围的知识的 O(VN)算法。希望你特别注意 “拆分物品” 的思想和方法，自己证明一下它的正确性，并将完整的程序代码写出来。P04: 混合三种背包问题问题如果将 P01、P02、P03 混合起来。也就是说，有的物品只可以取一次（01背包） ，有的物品可以取无限次（完全背包） ，有的物品可以取的次数有一个上限（多重背包） 。应该怎么求解呢？01背包与完全背包的混合考虑到在 P01和 P02中给出的伪代码只有一处不同，故如果只有两类物品：一类物品只能取一次，另一类物品可以取无限次，那么只需在对每个物品应用转移方程时，根据物品的类别选用顺序或逆序的循环即可，复杂度是 O(VN)。伪代码如
15、下：for i=1.Nif 第 i 件物品属于01背包for v=V.0fv=maxfv,fv-ci+wi;else if 第 i 件物品属于完全背包for v=0.Vfv=maxfv,fv-ci+wi;再加上多重背包如果再加上有的物品最多可以取有限次，那么原则上也可以给出 O(VN)的解法：遇到多重背包类型的物品用单调队列解即可。但如果不考虑超过 NOIP 范围的算法的话，用 P03中将每个这类物品分成 O(log ni)个01背包的物品的方法也已经很优了。当然，更清晰的写法是调用我们前面给出的三个相关过程。for i=1.Nif 第 i 件物品属于01背包ZeroOnePack(ci,wi
16、)else if 第 i 件物品属于完全背包CompletePack(ci,wi)else if 第 i 件物品属于多重背包MultiplePack(ci,wi,ni)在最初写出这三个过程的时候，可能完全没有想到它们会在这里混合应用。我想这体现了编程中抽象的威力。如果你一直就是以这种“抽象出过程”的方式写每一类背包问题的，也非常清楚它们的实现中细微的不同，那么在遇到混合三种背包问题的题目时，一定能很快想到上面简洁的解法，对吗？小结有人说，困难的题目都是由简单的题目叠加而来的。这句话是否公理暂且存之不论，但它在本讲中已经得到了充分的体现。本来01背包、完全背包、多重背包都不是什么难题，但将它们简
17、单地组合起来以后就得到了这样一道一定能吓倒不少人的题目。但只要基础扎实，领会三种基本背包问题的思想，就可以做到把困难的题目拆分成简单的题目来解决。P05: 二维费用的背包问题问题二维费用的背包问题是指：对于每件物品，具有两种不同的费用；选择这件物品必须同时付出这两种代价；对于每种代价都有一个可付出的最大值（背包容量） 。问怎样选择物品可以得到最大的价值。设这两种代价分别为代价1和代价2，第 i 件物品所需的两种代价分别为 ai和 bi。两种代价可付出的最大值（两种背包容量）分别为 V 和 U。物品的价值为wi。算法费用加了一维，只需状态也加一维即可。设 fivu表示前 i 件物品付出两种代价分
18、别为v 和 u 时可获得的最大价值。状态转移方程就是：fivu=maxfi-1vu,fi-1v-aiu-bi+wi如前述方法，可以只使用二维的数组：当每件物品只可以取一次时变量 v 和 u 采用逆序的循环，当物品有如完全背包问题时采用顺序的循环。当物品有如多重背包问题时拆分物品。这里就不再给出伪代码了，相信有了前面的基础，你能够自己实现出这个问题的程序。物品总个数的限制有时， “二维费用” 的条件是以这样一种隐含的方式给出的：最多只能取 M 件物品。这事实上相当于每件物品多了一种“件数”的费用，每个物品的件数费用均为1，可以付出的最大件数费用为 M。换句话说，设 fvm表示付出费用 v、最多选
19、 m 件时可得到的最大价值，则根据物品的类型（01、完全、多重）用不同的方法循环更新，最后在 f0.V0.M范围内寻找答案。复数域上的背包问题另一种看待二维背包问题的思路是：将它看待成复数域上的背包问题。也就是说，背包的容量以及每件物品的费用都是一个复数。而常见的一维背包问题则是实数域上的背包问题。（注意：上面的话其实不严谨，因为事实上我们处理的都只是整数而已。 ）所以说，一维背包的种种思想方法，往往可以应用于二位背包问题的求解中，因为只是数域扩大了而已。作为这种思想的练习，你可以尝试将 P11中提到的“子集和问题”扩展到复数域（即二维） ，并试图用同样的复杂度解决。小结当发现由熟悉的动态规划
20、题目变形得来的题目时，在原来的状态中加一纬以满足新的限制是一种比较通用的方法。希望你能从本讲中初步体会到这种方法。P06: 分组的背包问题问题有 N 件物品和一个容量为 V 的背包。第 i 件物品的费用是 ci，价值是 wi。这些物品被划分为若干组，每组中的物品互相冲突，最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。算法这个问题变成了每组物品有若干种策略：是选择本组的某一件，还是一件都不选。也就是说设 fkv表示前 k 组物品花费费用 v 能取得的最大权值，则有：fkv=maxfk-1v,fk-1v-ci+wi|物品 i 属于组 k使用一维数组的伪代码
21、如下：for 所有的组 kfor v=V.0for 所有的 i 属于组 kfv=maxfv,fv-ci+wi注意这里的三层循环的顺序，甚至在本文的第一个 beta 版中我自己都写错了。 “for v=V.0”这一层循环必须在“for 所有的 i 属于组 k”之外。这样才能保证每一组内的物品最多只有一个会被添加到背包中。另外，显然可以对每组内的物品应用 P02中“一个简单有效的优化”。小结分组的背包问题将彼此互斥的若干物品称为一个组，这建立了一个很好的模型。不少背包问题的变形都可以转化为分组的背包问题（例如 P07） ，由分组的背包问题进一步可定义“泛化物品”的概念，十分有利于解题。P07: 有
22、依赖的背包问题简化的问题这种背包问题的物品间存在某种“依赖”的关系。也就是说，i 依赖于 j，表示若选物品 i，则必须选物品 j。为了简化起见，我们先设没有某个物品既依赖于别的物品，又被别的物品所依赖；另外，没有某件物品同时依赖多件物品。算法这个问题由 NOIP2006金明的预算方案一题扩展而来。遵从该题的提法，将不依赖于别的物品的物品称为“主件” ，依赖于某主件的物品称为“ 附件” 。由这个问题的简化条件可知所有的物品由若干主件和依赖于每个主件的一个附件集合组成。按照背包问题的一般思路，仅考虑一个主件和它的附件集合。可是，可用的策略非常多，包括：一个也不选，仅选择主件，选择主件后再选择一个附
23、件，选择主件后再选择两个附件无法用状态转移方程来表示如此多的策略。 （事实上，设有 n 个附件，则策略有2n+1个，为指数级。 ）考虑到所有这些策略都是互斥的（也就是说，你只能选择一种策略） ，所以一个主件和它的附件集合实际上对应于 P06中的一个物品组，每个选择了主件又选择了若干个附件的策略对应于这个物品组中的一个物品，其费用和价值都是这个策略中的物品的值的和。但仅仅是这一步转化并不能给出一个好的算法，因为物品组中的物品还是像原问题的策略一样多。再考虑 P06中的一句话： 可以对每组中的物品应用 P02中 “一个简单有效的优化 ”。 这提示我们，对于一个物品组中的物品，所有费用相同的物品只留一个价值最大的，不影响结果。所以，我们可以对主件 i 的“附件集合”先进行一次01背包，得到费用依次为0.V-ci所有这些值时相应的最大价值 f0.V-ci。那么这个主件及它的附件集合相当于 V-ci+1个物品的物品组，其中费用为 ci+k 的物品的价值为 fk+wi。也就是说原来指数级的策略中有很多策略都是冗余的，通过一次01背包后，将主件 i 转化为 V-ci+1个物品的物品组，就可以直接应用 P06的算法解决问题了。
