绝对经典背包九讲完整版

《绝对经典背包九讲完整版》由会员分享，可在线阅读，更多相关《绝对经典背包九讲完整版（25页珍藏版）》请在装配图网上搜索。

1、背包问题九讲vl.O目录第一讲01背包问题第二讲完全背包问题第三讲多重背包问题第四讲混合三种背包问题第五讲二维费用的背包问题第六讲 分组的背包问题第七讲 有依赖的背包问题第八讲泛化物品第九讲 背包问题问法的变化附：USAC中的背包问题、八 、，刖言本篇文章是我（dd_engi）正在进行中的一个雄心勃勃的写作计划的一部分，这个 计划的内容是写作一份较为完善的 NOIP难度的动态规划总结，名为解动态规 划题的基本思考方式。现在你看到的是这个写作计划最先发布的一部分。背包问题是一个经典的动态规划模型。 它既简单形象容易理解，又在某种程度上 能够揭示动态规划的本质，故不少教材都把它作为动态规划部分的第

2、一道例题， 我也将它放在我的写作计划的第一部分。读本文最重要的是思考。因为我的语言和写作方式向来不以易于理解为长， 思路 也偶有跳跃的地方，后面更有需要大量思考才能理解的比较抽象的内容。 更重要 的是：不大量思考，绝对不可能学好动态规划这一信息学奥赛中最精致的部分。你现在看到的是本文的1.0正式版。我会长期维护这份文本，把大家的意见和建 议融入其中，也会不断加入我在OI学习以及将来可能的ACM-ICPC勺征程中得到 的新的心得。但目前本文还没有一个固定的发布页面， 想了解本文是否有更新版 本发布，可以在OIBH论坛中以“背包问题九讲”为关键字搜索贴子，每次比较 重大的版本更新都会在这里发贴公布

3、。目录第一讲01背包问题这是最基本的背包问题，每个物品最多只能放一次第二讲完全背包问题第二个基本的背包问题模型，每种物品可以放无限多次。第三讲多重背包问题每种物品有一个固定的次数上限。第四讲混合三种背包问题将前面三种简单的问题叠加成较复杂的问题。第五讲二维费用的背包问题一个简单的常见扩展。第六讲 分组的背包问题一种题目类型，也是一个有用的模型。后两节的基础。第七讲 有依赖的背包问题另一种给物品的选取加上限制的方法。第八讲泛化物品我自己关于背包问题的思考成果，有一点抽象。第九讲背包问题问法的变化试图触类旁通、举一反三。附：USACOP的背包问题给出USACO Training上可供练习的背包问题

4、列表，及简单的解答。联系方式如果有任何意见和建议，特别是文章的错误和不足，或者希望为文章添加新的材 料，可以通过这个网页联系我。致谢感谢以下名单：*阿坦* jason911* don glixp他们每人都最先指出了本文第一个 beta版中的某个并非无关紧要的错误。谢谢 你们如此仔细地阅读拙作并弥补我的疏漏。感谢XiaQ，它针对本文的第一个beta版发表了用词严厉的六条建议，虽然我只 认同并采纳了其中的两条。在所有读者几乎一边倒的赞扬将我包围的当时， 你的 贴子是我的一剂清醒剂，让我能清醒起来并用更严厉的眼光审视自己的作品。当然，还有用各种方式对我表示鼓励和支持的几乎无法计数的同学。 不管是当面

5、 赞扬，或是在论坛上回复我的贴子，不管是发来热情洋溢的邮件，或是在即时聊 天的窗口里竖起大拇指，你们的鼓励和支持是支撑我的写作计划的强大动力， 也 鞭策着我不断提高自身水平，谢谢你们！最后，感谢Emacs这一世界最强大的编辑器的所有贡献者，感谢它的插件 EmacsMuse的开发者们，本文的所有编辑工作都借助这两个卓越的自由软件完 成。谢谢你们一一自由软件社群一一为社会提供了如此有生产力的工具。我深深钦佩你们身上体现出的自由软件的精神， 没有你们的感召，我不能完成本文。在 你们的影响下，采用自由文档的方式发布本文档， 也是我对自由社会事业的微薄 努力。P01: 01 背包问题题目有N件物品和一个

6、容量为V的背包。第i件物品的重量是ci，价值是wi。 求解将哪些物品装入背包可使价值总和最大。基本思路这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。用子问题定义状态： 即 fiv 表示前 i 件物品恰放入一个容量为 v 的背包可以 获得的最大价值。则其状态转移方程便是：fiv=maxfi-1v,fi-1v-ci+wi这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。 所以有必要将它详细解释一下： “将前 i 件物品放入容量为 v 的背包中”这个子 问题，若只考虑第 i 件物品的策略 (放或不放)， 那么就可以转化为一个只牵扯 前 i-1 件物品的问题。

7、如果不放第 i 件物品，那么问题就转化为“前 i-1 件物品 放入容量为 v 的背包中”，价值为 fi-1v ；如果放第 i 件物品，那么问题就 转化为“前 i-1 件物品放入剩下的容量为 v-ci 的背包中”，此时能获得的最 大价值就是 fi-1v-ci 再加上通过放入第 i 件物品获得的价值 wi 。优化空间复杂度以上方法的时间和空间复杂度均为O(N*V)，其中时间复杂度基本已经不能再优化了，但空间复杂度却可以优化到 O(V)。先考虑上面讲的基本思路如何实现，肯定是有一个主循环i=1.N ，每次算出来二维数组 fi0.V的所有值。 那么， 如果只用一个数组 f0.V，能不能保证第i次循环结

8、束后fv中表示的就是我们定义的状态fiv 呢？ fiv 是由 fi-1v 和 fi-1v-ci 两个子问题递推而来， 能否保证在推 fiv 时(也 即在第 i 次主循环中推 fv 时)能够得到 fi-1v 和 fi-1v-ci 的值呢？ 事实上，这要求在每次主循环中我们以v=V.0 的顺序推 fv ，这样才能保证推fv 时 fv-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 就相当于

9、原来的fi-1v-ci 。如果将v的循环顺序从上面的逆序改成顺序的话，那么 则成了 fiv 由 fiv-ci 推知，与本题意不符， 但它却是另一个重要的背包问题P02最简捷的解决方案，故学习只用一维数组解01背包问题是十分必要的。事实上，使用一维数组解01背包的程序在后面会被多次用到，所以这里抽象出 一个处理一件01背包中的物品过程，以后的代码中直接调用不加说明。过程ZeroOnePacK表示处理一件01背包中的物品，两个参数 cost、weight分 别表明这件物品的费用和价值。procedure ZeroOn ePack(cost,weight)for v=V.costfv=max fv,

10、fv-cost+weight 注意这个过程里的处理与前面给出的伪代码有所不同。前面的示例程序写成 v=V.0是为了在程序中体现每个状态都按照方程求解了，避免不必要的思维复 杂度。而这里既然已经抽象成看作黑箱的过程了，就可以加入优化。费用为cost的物品不会影响状态f0.cost-1，这是显然的。有了这个过程以后，01背包问题的伪代码就可以这样写：for i=1.NZero On ePack(ci,wi);初始化的细节问题我们看到的求最优解的背包问题题目中，事实上有两种不太相同的问法。有的题目要求“恰好装满背包”时的最优解，有的题目则并没有要求必须把背包装满。 一种区别这两种问法的实现方法是在初

11、始化的时候有所不同。如果是第一种问法，要求恰好装满背包，那么在初始化时除了 f0为0其它 f1.V均设为-X,这样就可以保证最终得到的fN是一种恰好装满背包的最 优解。如果并没有要求必须把背包装满，而是只希望价格尽量大，初始化时应该将f0.V全部设为0。为什么呢？可以这样理解：初始化的f数组事实上就是在没有任何物品可以放入 背包时的合法状态。如果要求背包恰好装满，那么此时只有容量为0的背包可能 被价值为0的nothing “恰好装满”，其它容量的背包均没有合法的解，属于未 定义的状态，它们的值就都应该是-%了。如果背包并非必须被装满，那么任何 容量的背包都有一个合法解“什么都不装”，这个解的价

12、值为 0,所以初始时状 态的值也就全部为0 了。这个小技巧完全可以推广到其它类型的背包问题，后面也就不再对进行状态转移 之前的初始化进行讲解。小结01背包问题是最基本的背包问题，它包含了背包问题中设计状态、方程的最基 本思想，另外，别的类型的背包问题往往也可以转换成 01背包问题求解。故一 定要仔细体会上面基本思路的得出方法， 状态转移方程的意义，以及最后怎样优 化的空间复杂度。首页P02:完全背包问题题目有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费 用是ci，价值是wi。求解将哪些物品装入背包可使这些物品的费用总和不 超过背包容量，且价值总和最大。基本思路这个问题非

13、常类似于01背包问题，所不同的是每种物品有无限件。也就是从每 种物品的角度考虑，与它相关的策略已并非取或不取两种，而是有取0件、取1件、取2件,，等很多种。如果仍然按照解01背包时的思路，令fiv 表示前i种物品恰放入一个容量为v的背包的最大权值。仍然可以按照每种物品不同 的策略写出状态转移方程，像这样：fiv=maxfi-1v-k*ci+k*wi|0=k*civ=v这跟01背包问题一样有O(N*V)个状态需要求解，但求解每个状态的时间已经不 是常数了，求解状态fiv 的时间是O(v/ci)，总的复杂度是超过 O(VN)的。将01背包问题的基本思路加以改进，得到了这样一个清晰的方法。这说明 0

14、1 背包问题的方程的确是很重要，可以推及其它类型的背包问题。 但我们还是试图 改进这个复杂度。一个简单有效的优化完全背包问题有一个很简单有效的优化，是这样的：若两件物品i、j满足ci=wj，则将物品j去掉，不用考虑。这个优化的正确性显 然：任何情况下都可将价值小费用高得j换成物美价廉的i，得到至少不会更差 的方案。对于随机生成的数据，这个方法往往会大大减少物品的件数，从而加快速度。然而这个并不能改善最坏情况的复杂度，因为有可能特别设计的数据可以一件物品也去不掉。这个优化可以简单的O(NT)地实现，一般都可以承受。另外，针对背包问题而 言，比较不错的一种方法是：首先将费用大于V的物品去掉，然后使

15、用类似计数 排序的做法，计算出费用相同的物品中价值最高的是哪个，可以O(V+N地完成这个优化。这个不太重要的过程就不给出伪代码了，希望你能独立思考写出伪代码或程序。转化为01背包问题求解既然01背包问题是最基本的背包问题，那么我们可以考虑把完全背包问题转化 为01背包问题来解。最简单的想法是，考虑到第i种物品最多选V/ci件，于 是可以把第i种物品转化为V/ci件费用及价值均不变的物品，然后求解这个 01背包问题。这样完全没有改进基本思路的时间复杂度，但这毕竟给了我们将 完全背包问题转化为01背包问题的思路：将一种物品拆成多件物品。更高效的转化方法是：把第i种物品拆成费用为ci*2Ak 、价值

16、为wi*2Ak的 若干件物品，其中k满足ci*2Ak=V。这是二进制的思想，因为不管最优策略 选几件第i种物品，总可以表示成若干个2Ak件物品的和。这样把每种物品拆成 O(log(V/ci)件物品，是一个很大的改进。但我们有更优的O(VN)的算法。O(VN)的算法这个算法使用一维数组，先看伪代码：for i=1.Nfor v=0.Vfv=maxfv,fv-cost+weight你会发现，这个伪代码与P01的伪代码只有v的循环次序不同而已。为什么这样 一改就可行呢？首先想想为什么 P01中要按照v=V.O的逆序来循环。这是因为 要保证第i次循环中的状态fiv是由状态fi-1v-ci递推而来。换句

17、话说，这正是为了保证每件物品只选一次，保证在考虑“选入第i件物品”这件策略时，依据的是一个绝无已经选入第i件物品的子结果fi-1v-ci 。而现 在完全背包的特点恰是每种物品可选无限件，所以在考虑“加选一件第 i种物 品”这种策略时，却正需要一个可能已选入第i种物品的子结果fiv-ci，所以就可以并且必须采用v=0.V的顺序循环。这就是这个简单的程序为何成立 的道理。这个算法也可以以另外的思路得出。例如，基本思路中的状态转移方程可以等价地变形成这种形式：fiv=maxfi-1v,fiv-ci+wi将这个方程用一维数组实现，便得到了上面的伪代码。最后抽象出处理一件完全背包类物品的过程伪代码，以后

18、会用到：procedure CompletePack(cost,weight)for v=cost.Vfv=maxfv,fv-ci+wi总结完全背包问题也是一个相当基础的背包问题，它有两个状态转移方程，分别在“基本思路”以及“ O(VN)的算法“的小节中给出。希望你能够对这两个状态转移方程都仔细地体会，不仅记住，也要弄明白它们是怎么得出来的，最好能够自 己想一种得到这些方程的方法。事实上，对每一道动态规划题目都思考其方程的 意义以及如何得来，是加深对动态规划的理解、提高动态规划功力的好方法。首页P03:多重背包问题题目有N种物品和一个容量为V的背包。第i种物品最多有ni件可用，每件费用 是ci

19、，价值是wi。求解将哪些物品装入背包可使这些物品的费用总和不超 过背包容量，且价值总和最大。基本算法这题目和完全背包问题很类似。基本的方程只需将完全背包问题的方程略微一改 即可，因为对于第i种物品有ni+1种策略：取0件，取1件,，取 ni件。 令fiv 表示前i种物品恰放入一个容量为v的背包的最大权值，则有状态转 移方程：fiv=maxfi-1v-k*ci+k*wi|0=k0的最大整数。例如，如果ni为13,就将这种物品分成系数分别为1,2,4,6的四件物品。分成的这几件物品的系数和为ni，表明不可能取多于ni件的第i种物品。 另外这种方法也能保证对于0. ni间的每一个整数，均可以用若干个

20、系数的和 表示，这个证明可以分0.2Ak-1和2Ak.ni两段来分别讨论得出，并不难, 希望你自己思考尝试一下。这样就将第i种物品分成了 O(log ni)种物品，将原问题转化为了复杂度为O(V*X log ni) 的01背包问题，是很大的改进。下面给出O(log amount)时间处理一件多重背包中物品的过程，其中amount表示物品的数量：procedure MultiplePack(cost,weight,am ount)if cost*am oun t=VCompletePack(cost,weight)returnin teger k=1while k numZeroO nePack

21、(k*cost,k*weight)amoun t=am oun t-kk=k*2Zero On ePack(am oun t*cost,amou nt*weight)希望你仔细体会这个伪代码，如果不太理解的话，不妨翻译成程序代码以后，单 步执行几次，或者头脑加纸笔模拟一下，也许就会慢慢理解了。O(VN)的算法多重背包问题同样有O(VN)的算法。这个算法基于基本算法的状态转移方程，但 应用单调队列的方法使 每个状态的值可以以均摊 O(1)的时间求解。由于用单调 队列优化的DP已超出了 NOIP的范围，故本文不再展开讲解。我最初了解到这个 方法是在楼天成的“男人八题”幻灯片上。小结这里我们看到了将

22、一个算法的复杂度由O(V*X ni)改进到O(V*X log ni) 的过程，还知道了存在应用超出 NOIP范围的知识的O(VN算法。希望你特别注意“拆分物品”的思想和方法，自己证明一下它的正确性，并将完整的程序代码写 出来。首页P04:混合三种背包问题冋题如果将P01、P02、P03混合起来。也就是说，有的物品只可以取一次(01背包)， 有的物品可以取无限次(完全背包)，有的物品可以取的次数有一个上限 (多重 背包)。应该怎么求解呢？01背包与完全背包的混合考虑到在P01和P02中给出的伪代码只有一处不同，故如果只有两类物品：一类 物品只能取一次，另一类物品可以取无限次，那么只需在对每个物品

23、应用转移方 程时，根据物品的类别选用顺序或逆序的循环即可，复杂度是O(VN)。伪代码如下：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;再加上多重背包如果再加上有的物品最多可以取有限次，那么原则上也可以给出0(VN)的解法：遇到多重背包类型的物品用单调队列解即可。但如果不考虑超过NOIP范围的算法的话，用P03中将每个这类物品分成O(log ni) 个01背包的物品的方法也 已经很优了。当然，更清晰的写法是调用我们前面给出的三个相关过程。for i=1.

24、Nif 第i件物品是01背包ZeroO nePack(ci,wi)else if第i件物品是完全背包CompletePack(ci,wi)else if第i件物品是多重背包MultiplePack(ci,wi, n i)在最初写出这三个过程的时候，可能完全没有想到它们会在这里混合应用。我想这体现了编程中抽象的威力。如果你一直就是以这种“抽象出过程”的方式写每 一类背包问题的，也非常清楚它们的实现中细微的不同，那么在遇到混合三种背包问题的题目时，一定能很快想到上面简洁的解法，对吗？小结有人说，困难的题目都是由简单的题目叠加而来的。 这句话是否公理暂且存之不 论，但它在本讲中已经得到了充分的体现。

25、本来 01背包、完全背包、多重背包 都不是什么难题，但将它们简单地组合起来以后就得到了这样一道一定能吓倒不 少人的题目。但只要基础扎实，领会三种基本背包问题的思想， 就可以做到把困 难的题目拆分成简单的题目来解决。首页P05:二维费用的背包问题问题二维费用的背包问题是指：对于每件物品，具有两种不同的费用；选择这件物品 必须同时付出这两种代价；对于每种代价都有一个可付出的最大值 （背包容量）。 问怎样选择物品可以得到最大的价值。设这两种代价分别为代价1和代价2,第i件物品所需的两种代价分别为 ai和bi。两种代价可付出的最大值（两种 背包容量）分别为V和UL物品的价值为wi。算法费用加了一维，只

26、需状态也加一维即可。设fivu 表示前i件物品付出两种代价分别为v和u时可获得的最大价值。状态转移方程就是：fivu=maxfi-1vu,fi-1v-aiu-bi+wi如前述方法，可以只使用二维的数组：当每件物品只可以取一次时变量V和u采用逆序的循环，当物品有如完全背包问题时采用顺序的循环。当物品有如多重背包问题时拆分物品。这里就不再给出伪代码了，相信有了前面的基础，你能够 自己实现出这个问题的程序。物品总个数的限制（精辟）有时，“二维费用”的条件是以这样一种隐含的方式给出的：最多只能取M件物品。这事实上相当于每件物品多了一种“件数”的费用，每个物品的件数费用均为1,可以付出的最大件数费用为

27、M换句话说，设fvm表示付出费用V、最 多选m件时可得到的最大价值，则根据物品的类型（01、完全、多重）用不同的 方法循环更新，最后在f0.V0.M范围内寻找答案。小结当发现由熟悉的动态规划题目变形得来的题目时，在原来的状态中加一纬以满足新的限制是一种比较通用的方法。希望你能从本讲中初步体会到这种方法。首页P06:分组的背包问题冋题有N件物品和一个容量为V的背包。第i件物品的费用是ci，价值是wi。 这些物品被划分为若干组，每组中的物品互相冲突，最多选一件。求解将哪些物 品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。算法这个问题变成了每组物品有若干种策略：是选择本组的某一件，

28、还是一件都不选 也就是说设fkv表示前k组物品花费费用v能取得的最大权值，则有：fkv=maxfk-1v,fk-1v-ci+wi|物品 i 属于第 k 组使用一维数组的伪代码如下：for所有的组kfor v=V.0for 所有的i属于组kfv=maxfv,fv-ci+wi注意这里的三层循环的顺序，甚至在本文的 beta版中我自己都写错了。“forv=V.0 ”这一层循环必须在“for所有的i属于组k”之外。这样才能保证每- 组内的物品最多只有一个会被添加到背包中。另外，显然可以对每组内的物品应用 P02中“一个简单有效的优化”小结分组的背包问题将彼此互斥的若干物品称为一个组，这建立了一个很好的

29、模型。不少背包问题的变形都可以转化为分组的背包问题（例如P07），由分组的背包问题进一步可定义“泛化物品”的概念，十分有利于解题。首页P07:有依赖的背包问题简化的冋题这种背包问题的物品间存在某种“依赖”的关系。也就是说，i依赖于j，表示 若选物品i，则必须选物品j。为了简化起见，我们先设没有某个物品既依赖于 别的物品，又被别的物品所依赖；另外，没有某件物品同时依赖多件物品。算法这个问题由NOIP2006金明的预算方案一题扩展而来。遵从该题的提法，将不依 赖于别的物品的物品称为“主件”， 依赖于某主件的物品称为“附件”。由这个问题的简化条件可知所有的物品由若干主件和依赖于每个主件的一个附件集合

30、 组成。按照背包问题的一般思路，仅考虑一个主件和它的附件集合。可是，可用的策略非常多，包括：一个也不选，仅选择主件，选择主件后再选择一个附件，选择主 件后再选择两个附件,无法用状态转移方程来表示如此多的策略。（事实上， 设有n个附件，则策略有2An+1个，为指数级。）考虑到所有这些策略都是互斥的（也就是说，你只能选择一种策略），所以一个 主件和它的附件集合实际上对应于 P06中的一个物品组，每个选择了主件又选择 了若干个附件的策略对应于这个物品组中的一个物品，其费用和价值都是这个策 略中的物品的值的和。但仅仅是这一步转化并不能给出一个好的算法， 因为物品 组中的物品还是像原冋题的策略一样多。再

31、考虑P06中的一句话： 可以对每组中的物品应用 P02中“一个简单有效的优 化”。这提示我们，对于一个物品组中的物品，所有费用相同的物品只留一个 价值最大的，不影响结果。所以，我们可以对主件i的“附件集合”先进行一次 01背包，得到费用依次为O.V-ci 所有这些值时相应的最大价值 f0.V-ci。那么这个主件及它的附件集合相当于 V-ci+1个物品的物品组，其中费用为ci+k的物品的价值为fk+wi。也就是说原来指数级的策 略中有很多策略都是冗余的，通过一次 01背包后，将主件i转化为V-ci+1 个物品的物品组，就可以直接应用 P06的算法解决问题了。较一般的问题更一般的问题是：依赖关系以

32、图论中“森林”的形式给出（森林即多叉树的集 合），也就是说，主件的附件仍然可以具有自己的附件集合，限制只是每个物品最多只依赖于一个物品（只有一个主件）且不出现循环依赖。解决这个问题仍然可以用将每个主件及其附件集合转化为物品组的方式。唯一不同的是，由于附件可能还有附件，就不能将每个附件都看作一个一般的 01背包 中的物品了。若这个附件也有附件集合，则它必定要被先转化为物品组，然后用 分组的背包问题解出主件及其附件集合所对应的附件组中各个费用的附件所对 应的价值。事实上，这是一种树形DP其特点是每个父节点都需要对它的各个儿子的属性 进行一次DP以求得自己的相关属性。这已经触及到了 “泛化物品”的思

33、想。看 完P08后，你会发现这个“依赖关系树”每一个子树都等价于一件泛化物品，求某节点为根的子树对应的泛化物品相当于求其所有儿子的对应的泛化物品之和。小结NOIP2006的那道背包问题我做得很失败，写了上百行的代码，却一分未得。后 来我通过思考发现通过引入“物品组”和“依赖”的概念可以加深对这题的理 解,还可以解决它的推广问题。用物品组的思想考虑那题中极其特殊的依赖关系： 物品不能既作主件又作附件，每个主件最多有两个附件，可以发现一个主件和它 的两个附件等价于一个由四个物品组成的物品组，这便揭示了问题的某种本质。我想说：失败不是什么丢人的事情，从失败中全无收获才是。首页P08:泛化物品定义考虑

34、这样一种物品，它并没有固定的费用和价值，而是它的价值随着你分配给它 的费用而变化。这就是泛化物品的概念。更严格的定义之。在背包容量为V的背包问题中，泛化物品是一个定义域为0.V 中的整数的函数h,当分配给它的费用为V时，能得到的价值就是h(v)。这个定义有一点点抽象，另一种理解是一个泛化物品就是一个数组h0.V，给它费用v,可得到价值hV。一个费用为c价值为w的物品，如果它是01背包中的物品，那么把它看成泛化 物品，它就是除了 h(c)=w其它函数值都为0的一个函数。如果它是完全背包中 的物品，那么它可以看成这样一个函数，仅当v被c整除时有h(v)=v/c*w，其它函数值均为0。如果它是多重背

35、包中重复次数最多为n的物品，那么它对应的泛化物品的函数有h(v)=v/c*w 仅当v被c整除且v/c=n，其它情况函数值均为 0。一个物品组可以看作一个泛化物品h0对于一个0.V中的v，若物品组中不存在费用为v的的物品，贝U h(v)=0，否则h(v)为所有费用为v的物品的最大价值。 P07中每个主件及其附件集合等价于一个物品组，自然也可看作一个泛化物品。泛化物品的和如果面对两个泛化物品h和I ,要用给定的费用从这两个泛化物品中得到最大的 价值，怎么求呢？事实上，对于一个给定的费用v,只需枚举将这个费用如何分配给两个泛化物品就可以了。同样的，对于0.V的每一个整数v,可以求得费用v分配到h和I

36、中的最大价值f(v)。也即f(v)=maxh(k)+l(v-k)|0=kv=v可以看到，f也是一个由泛化物品h和I决定的定义域为0.V的函数，也就是 说，f是一个由泛化物品h和I决定的泛化物品。由此可以定义泛化物品的和：h、l都是泛化物品，若泛化物品f满足 f(v)=maxh(k)+l(v-k)|0=k0） if（giv=0） print 未选第 i 项物品else if（giv=1）print 选了第 i 项物品v=v-ci 另外，采用方程的前一项或后一项也可以在输出方案的过程中根据 fiv 的值 实时地求出来，也即不须纪录 g 数组，将上述代码中的 giv=0 改成 fiv=fi-1v，g

37、iv=1 改成 fiv=fi-1v-ci+wi也可。输出字典序最小的最优方案 这里“字典序最小”的意思是 1.N 号物品的选择方案排列出来以后字典序最 小。以输出 01 背包最小字典序的方案为例。一般而言， 求一个字典序最小的最优方案， 只需要在转移时注意策略。 首先，子 问题的定义要略改一些。 我们注意到， 如果存在一个选了物品 1 的最优方案，那 么答案一定包含物品 1，原问题转化为一个背包容量为 v-c1 ，物品为 2.N 的 子问题。反之，如果答案不包含物品1,则转化成背包容量仍为 V,物品为2.N 的子问题。 不管答案怎样， 子问题的物品都是以 i.N 而非前所述的 1.i 的形式

38、来定义的， 所以状态的定义和转移方程都需要改一下。 但也许更简易的方法是先 把物品逆序排列一下，以下按物品已被逆序排列来叙述。在这种情况下， 可以按照前面经典的状态转移方程来求值， 只是输出方案的时候 要注意：从 N 到 1 输入时，如果 fiv=fi-v 及fiv=fi-1f-ci+wi同时成立，应该按照后者（即选择了物品 i ）来输出方案。求方案总数 对于一个给定了背包容量、物品费用、物品间相互关系（分组、依赖等）的背包 问题，除了再给定每个物品的价值后求可得到的最大价值外， 还可以得到装满背 包或将背包装至某一指定容量的方案总数。对于这类改变问法的问题，一般只需将状态转移方程中的 max

39、改成sum即可。例 如若每件物品均是完全背包中的物品，转移方程即为fiv=sumfi-1v,fiv-ci初始条件 f00=1 。事实上，这样做可行的原因在于状态转移方程已经考察了所有可能的背包组成方 案。最优方案的总数这里的最优方案是指物品总价值最大的方案。以 01 背包为例。结合求最大总价值和方案总数两个问题的思路，最优方案的总数可以这样求： fiv 意义同前述， giv 表示这个子问题的最优方案的总数， 则在求 fiv 的同时求 giv 的伪代码如下：for i=1.Nfor v=0.V fiv=maxfi-1v,fi-1v-ci+wi giv=0 if(fiv=fi-1v) inc(gi

40、v,gi-1v if(fiv=fi-1v-ci+wi) inc(giv,gi-1v-ci)如果你是第一次看到这样的问题，请仔细体会上面的伪代码。求次优解、第K优解对于求次优解、第K优解类的问题，如果相应的最优解问题能写出状态转移方程、 用动态规划解决，那么求次优解往往可以相同的复杂度解决， 第K优解则比求最 优解的复杂度上多一个系数K。其基本思想是将每个状态都表示成有序队列，将状态转移方程中的max/min转化成有序队列的合并。这里仍然以01背包为例讲解一下。首先看01背包求最优解的状态转移方程：fiv=maxfi-1v,fi-1v-ci+wi。如果要求第 K优解，那么状态fiv就应该是一个大

41、小为 K的数组fiv1.K 。其中fivk 表示前i个物品、背包大小为v时，第k优解的值。“fiv是一个大小为K的数组”这一句，熟悉C语言的同学可能比较好理解，或者也可以简单地理解为在原来的 方程中加了一维。显然fiv1.K 这K个数是由大到小排列的，所以我们把 它认为是一个有序队列。然后原方程就可以解释为：fiv 这个有序队列是由fi-1v 和 fi-1v-ci+wi这两个有序队列合并得到的。有序队列fi-1v 即fi-1v1.K，fi-1v-ci+wi则理解为在 fi-1v-ci1.K的每个数上加上wi后得到的有序队列。合并这两个有序队列并将结果（的前 K 项）储存到fiv1.K中的复杂度

42、是0（K）。最后的答案是fNVK。总的复杂度是O（NVK。为什么这个方法正确呢？实际上，一个正确的状态转移方程的求解过程遍历了所 有可用的策略，也就覆盖了问题的所有方案。只不过由于是求最优解，所以其它 在任何一个策略上达不到最优的方案都被忽略了。如果把每个状态表示成一个大小为K的数组，并在这个数组中有序的保存该状态可取到的前 K个最优值。那么, 对于任两个状态的max运算等价于两个由大到小的有序队列的合并。另外还要注意题目对于“第 K优解”的定义，将策略不同但权值相同的两个方案 是看作同一个解还是不同的解。如果是前者，则维护有序队列时要保证队列里的 数没有重复的。小结显然，这里不可能穷尽背包类

43、动态规划问题所有的问法。甚至还存在一类将背包类动态规划问题与其它领域（例如数论、图论）结合起来的问题，在这篇论背包 问题的专文中也不会论及。但只要深刻领会前述所有类别的背包问题的思路和状 态转移方程，遇到其它的变形问法，只要题目难度还属于NOIP,应该也不难想出算法。触类旁通、举一反三，应该也是一个 OIer应有的品质吧。首页附：USAC中的背包问题USAC是USA Computing Olympiad的简称，它组织了很多面向全球的计算机竞 赛活动。USACCTrainng是一个很适合初学者的题库，我认为它的特色是题目质量高，循 序渐进，还配有不错的课文和题目分析。其中关于背包问题的那篇课文(

44、TEXTKn apsack Problems)也值得一看。另外，USACOontest是USAC常年组织的面向全球的竞赛系列，在此也推荐NOIP 选手参加。我整理了 USACO Training中涉及背包问题的题目，应该可以作为不错的习题。 其中标加号的是我比较推荐的，标叹号的是我认为对NOIP选手比较有挑战性的。题目列表 Inflate (+)(基本 01 背包)* Stamps (+)(!)(对初学者有一定挑战性)* Money* Nuggets* Subsets Rockers (+)(另一类有趣的“二维”背包问题)* Milk4 (!)(很怪的背包问题问法，较难用纯DP求解)题目简解以

45、下文字来自我所撰的USAC心得一文，该文的完整版本，包括我的程序， 可在DD的USAC征程中找到。Inflate是加权01背包问题，也就是说：每种物品只有一件，只可以选择放或者不放；而且每种物品有对应的权值，目标是使总权值最大或最小。它最朴素的 状态转移方程是：fki= maxfk-1i, fk-1i-vk+wk。fki表示前k件物品花费代价i可以得到的最大权值。vk和wk分别是第k件物 品的花费和权值。可以看到，fk的求解过程就是使用第k件物品对fk-1 进行更新的过程。那么事实上就不用使用二维数组，只需要定义fi，然后对于每件物品k，顺序地检查fi与fi-vk+wk的大小，如果后者更大，就

46、对前者进行更新。这是背包问题中典型的优化方法。题目stamps中，每种物品的使用量没有直接限制，但使用物品的总量有限制。 求第一个不能用这有限个物品组成的背包的大小。(可以这样等价地认为)设 fki 表示前k件物品组成大小为i的背包，最少需要物品的数量。则 fki= minfk-1i,fk-1i-j*sk+j，其中 j 是选择使用第 k 件物品的数目，这个方程运用时可以用和上面一样的方法处理成一维的。求解时先设置一个粗糙的循环上限，即最大的物品乘最多物品数。Money是多重背包问题。也就是每个物品可以使用无限多次。要求解的是构成一 种背包的不同方案总数。基本上就是把一般的多重背包的方程中的 m

47、in改成sum 就行了。Nuggets的模型也是多重背包。要求求解所给的物品不能恰好放入的背包大小的 最大值(可能不存在)。只需要根据“若i、j互质，则关于x、y的不定方程i*x+y*j=n 必有正整数解，其中ni*j ”这一定理得出一个循环的上限。Subsets子集和问题相当于物品大小是前 N个自然数时求大小为N*(N+1)/4的 01背包的方案数。Rockers可以利用求解背包问题的思想设计解法。我的状态转移方程如下：fijt=maxfijt-1 , fi-1jt , fi-1jt-timei+1 , fi-1j-1T+(t=timei)。其中 fijt 表示前 i 首歌用 j 张完整的盘

48、和一张录了 t分钟的盘可以放入的最多歌数，T是一张光盘的最大容量， t=timei是一个bool值转换成int取值为0或1。但我后来发现我当时设计 的状态和方程效率有点低，如果换成这样：fij=(a,b) 表示前i首歌中选了 j首需要用到a张完整的光盘以及一张录了 b分钟的光盘，会将时空复杂度都 大大降低。这种将状态的值设为二维的方法值得注意。Milk4是这些类背包问题中难度最大的一道了。很多人无法做到将它用纯DP方法求解，而是用迭代加深搜索枚举使用的桶，将其转换成多重背包问题再DF。由于USAC0的数据弱，迭代加深的深度很小，这样也可以AC，但我们还是可以用纯DP方法将它完美解决的。设fk为

49、称量出k单位牛奶需要的最少的桶数。 那么可以用类似多重背包的方法对 f数组反复更新以求得最小值。然而困难在 于如何输出字典序最小的方案。我们可以对每个i记录pre_fi和pre_vi。表示得到i单位牛奶的过程是用pre_fi单位牛奶加上若干个编号为pre_vi 的桶的牛奶。这样就可以一步步求得得i单位牛奶的完整方案。为了使方案 的字典序最小，我们在每次找到一个耗费桶数相同的方案时对已储存的方案和新 方案进行比较再决定是否更新方案。为了使这种比较快捷，在使用各种大小的桶 对f数组进行更新时先大后小地进行。USACO勺官方题解正是这一思路。如果 认为以上文字比较难理解可以阅读官方程序或我的程序。首

50、页Copyright (c) 2007 Tianyi CuiPermissi on is gran ted to copy, distribute an d/or modify this docume nt under the terms of the GNUFree Documentation License , Version 1.2 or any later versi on published by the Free Software Foun dati on.整理 by stntwm多次背包多次背包问题：给定 n 种物品和一个背包。第 i 种物品 的价值是 Wi ，其体 积为 Vi

51、，数量是 Ki 件，背包的容量为 C 。可以任意选择装入背包中的物品，求 装入背包中物品的最大总价值。方法一：可以把此物品拆分成 Ki 个只能用一次的物品， 直接套用 0-1 背包问题 的经典动规实现， 但是效率太低了， 需要寻找更高效的算法。 此算法时间复杂度 为 0(C*刀(Ki)倍的几方法二：拆分成体积和价值分别为原来1,2,4. 2Am, Ki-2Am个物品，用0-1背包求解。时间复杂度为O(C*刀(log2Ki) 方法三(本文重点) ：(对单调队列没有了解的请参见原论文 本文结尾链接 ) 对于第i种物品来说，已知体积v ,价值w，数量k，那么可以按照当前枚举 的体积 j 对 v 的余

52、数把整个动规数组分成 v 份，以下是 v=3 的情况：j0 1 2 3 4 5 6 7 8 ,j mod v 0 1 2 0 1 2 0 1 2 ,我们可以把每一份分开处理，假设余数为 d 。编号j 012345J J对应体积 d d+v d+2*vd+3*v d+4*vd+5*v,现在看到分组以后， 编号 j 可以从 j-k 到 j-1 中的任意一个编号转移而来 (因 为相邻的体积正好相差 v ) ，这看上去已经和区间最大值有点相似了。但是注 意到由于体积不一样， 显然体积大的价值也会大于等于体积小的， 直接比较是没 有意义的， 所以还需要把价值修正到同一体积的基础上。 比如都退化到 d ，

53、也就 是说用 Fj*v+d- j*w 来代替原来的价值进入队列。对于物品 i ，伪代码如下1.FOR d: = 0 TO v-1/2.清空队列3.FOR j: = 0 TO(C-d)div v/j4.INSERT j , F j*v+d -j * w/5.IF A L j -k THEN L + 1 L /6.B L + j * w F j*v+d /7.END FOR8. END FOR枚举余数，分开处理枚举标号，对应体积为 j*v+d插入队列 如果队列的首元素已经失效取队列头更新已知单调队列的效率是 O(n) ，那么加上单调队列优化以后的多次背包，效率就是 O(n*C) 了。 (详细请参见

54、原论文)完整程序如下 (Pascal) ：vara,b,f:array0.100000 of longint;m,s,c,n,t,i,j,l,r,d:longint;procedure insert(x,y:longint);beginwhile (l=r)and(br=y) do dec(r);inc(r);ar:=x;br:=y;end;beginreadln(n,t); / 读入数据 n 为物品个数 t 为背包容量for i:=1 to n dobeginread(m,s,c); / 读入当前物品 m 为物品体积、 s 为物品价值、 c 为物品可用次数( 0 表示无限制)if (c=0)or(t div mc) then c:=t di