极好很全背背包包问问题题九九讲讲目录 第一讲 01 背包问题 第二讲 完全背包问题 第三讲 多重背包问题 第四讲 混合三种背包问题 第五讲 二维费用的背包问题 第六讲 分组的背包问题 第七讲 有依赖的背包问题 第八讲 泛化物品 第九讲 背包问题问法的变化 附：USACO 中的背包问题 前言前言本篇文章是我(dd_engi)正在进行中的一个雄心勃勃的写作计划的一部分，这个 计划的内容是写作一份较为完善的 NOIP 难度的动态规划总结，名为《解动态规 划题的基本思考方式》现在你看到的是这个写作计划最先发布的一部分背包问题是一个经典的动态规划模型它既简单形象容易理解，又在某种程度 上能够揭示动态规划的本质，故不少教材都把它作为动态规划部分的第一道例 题，我也将它放在我的写作计划的第一部分读本文最重要的是思考因为我的语言和写作方式向来不以易于理解为长，思 路也偶有跳跃的地方，后面更有需要大量思考才能理解的比较抽象的内容更 重要的是：不大量思考，绝对不可能学好动态规划这一信息学奥赛中最精致的 部分你现在看到的是本文的 1.0 正式版我会长期维护这份文本，把大家的意见和 建议融入其中，也会不断加入我在 OI 学习以及将来可能的 ACM-ICPC 的征程中 得到的新的心得。
但目前本文还没有一个固定的发布页面，想了解本文是否有 更新版本发布，可以在 OIBH 论坛中以“背包问题九讲”为关键字搜索贴子，每 次比较重大的版本更新都会在这里发贴公布目录目录第一讲第一讲 0101 背背包包问问题题这是最基本的背包问题，每个物品最多只能放一次第二讲第二讲 完全背包问题完全背包问题极好很全第二个基本的背包问题模型，每种物品可以放无限多次第三讲第三讲 多重背包问题多重背包问题每种物品有一个固定的次数上限第四讲第四讲 混合三种背包问题混合三种背包问题将前面三种简单的问题叠加成较复杂的问题第五讲第五讲 二维费用的背包问题二维费用的背包问题一个简单的常见扩展第六讲第六讲 分组的背包分组的背包问问题题一种题目类型，也是一个有用的模型后两节的基础第七讲第七讲 有依赖的背包问题有依赖的背包问题另一种给物品的选取加上限制的方法第八讲第八讲 泛化物品泛化物品我自己关于背包问题的思考成果，有一点抽象第九讲第九讲 背包问题问法的变化背包问题问法的变化试图触类旁通、举一反三附：附：USACOUSACO 中的背包问题中的背包问题给出 USACO Training 上可供练习的背包问题列表，及简单的解答。
联系方式联系方式如果有任何意见和建议，特别是文章的错误和不足，或者希望为文章添加新的 材料，可以通过 jason911 极好很全donglixp 他们每人都最先指出了本文第一个 beta 版中的某个并非无关紧要的错误谢谢 你们如此仔细地阅读拙作并弥补我的疏漏感谢 XiaQ，它针对本文的第一个 beta 版发表了用词严厉的六条建议，虽然我 只认同并采纳了其中的两条在所有读者几乎一边倒的赞扬将我包围的当时， 你的贴子是我的一剂清醒剂，让我能清醒起来并用更严厉的眼光审视自己的作 品当然，还有用各种方式对我表示鼓励和支持的几乎无法计数的同学不管是当 面赞扬，或是在论坛上回复我的贴子，不管是发来热情洋溢的邮件，或是在即 时聊天的窗口里竖起大拇指，你们的鼓励和支持是支撑我的写作计划的强大动 力，也鞭策着我不断提高自身水平，谢谢你们！最后，感谢 Emacs 这一世界最强大的编辑器的所有贡献者，感谢它的插件 EmacsMuse 的开发者们，本文的所有编辑工作都借助这两个卓越的自由软件完 成谢谢你们——自由软件社群——为社会提供了如此有生产力的工具我深 深钦佩你们身上体现出的自由软件的精神，没有你们的感召，我不能完成本文。
在你们的影响下，采用自由文档的方式发布本文档，也是我对自由社会事业的 微薄努力极好很全P01:P01: 0101 背包问题背包问题题目题目有 N 件物品和一个容量为 V 的背包第 i 件物品的费用是 c[i]，价值是 w[i] 求解将哪些物品装入背包可使价值总和最大基本思路基本思路这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放用子问题定义状态：即 f[i][v]表示前 i 件物品恰放入一个容量为 v 的背包可 以获得的最大价值则其状态转移方程便是：f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的 所以有必要将它详细解释一下：“将前 i 件物品放入容量为 v 的背包中”这个 子问题，若只考虑第 i 件物品的策略（放或不放），那么就可以转化为一个只 牵扯前 i-1 件物品的问题如果不放第 i 件物品，那么问题就转化为“前 i-1 件物品放入容量为 v 的背包中”，价值为 f[i-1][v]；如果放第 i 件物品，那 么问题就转化为“前 i-1 件物品放入剩下的容量为 v-c[i]的背包中”，此时能 获得的最大价值就是 f[i-1][v-c[i]]再加上通过放入第 i 件物品获得的价值 w[i]。
优化空间复杂度优化空间复杂度以上方法的时间和空间复杂度均为 O(N*V)，其中时间复杂度基本已经不能再优 化了，但空间复杂度却可以优化到 O(V)先考虑上面讲的基本思路如何实现，肯定是有一个主循环 i=1..N，每次算出来 二维数组 f[i][0..V]的所有值那么，如果只用一个数组 f[0..V]，能不能保 证第 i 次循环结束后 f[v]中表示的就是我们定义的状态 f[i][v]呢？f[i][v]是 由 f[i-1][v]和 f[i-1][v-c[i]]两个子问题递推而来，能否保证在推 f[i][v] 时（也即在第 i 次主循环中推 f[v]时）能够得到 f[i-1][v]和 f[i-1][v-c[i]] 的值呢？事实上，这要求在每次主循环中我们以 v=V..0 的顺序推 f[v]，这样 才能保证推 f[v]时 f[v-c[i]]保存的是状态 f[i-1][v-c[i]]的值伪代码如下：for i=1..Nfor v=V..0f[v]=max{f[v],f[v-c[i]]+w[i]}; 其中的 f[v]=max{f[v],f[v-c[i]]}一句恰就相当于我们的转移方程 f[i][v] =max{f[i-1][v],f[i-1][v-c[i]]}，因为现在的 f[v-c[i]]就相当于原来的极好很全f[i-1][v-c[i]]。
如果将 v 的循环顺序从上面的逆序改成顺序的话，那么则成 了 f[i][v]由 f[i][v-c[i]]推知，与本题意不符，但它却是另一个重要的背包 问题 P02 最简捷的解决方案，故学习只用一维数组解 01 背包问题是十分必要的事实上，使用一维数组解 01 背包的程序在后面会被多次用到，所以这里抽象出 一个处理一件 01 背包中的物品过程，以后的代码中直接调用不加说明过程 ZeroOnePack，表示处理一件 01 背包中的物品，两个参数 cost、weight 分别表明这件物品的费用和价值procedure ZeroOnePack(cost,weight)for v=V..costf[v]=max{f[v],f[v-cost]+weight} 注意这个过程里的处理与前面给出的伪代码有所不同前面的示例程序写成 v=V..0 是为了在程序中体现每个状态都按照方程求解了，避免不必要的思维复 杂度而这里既然已经抽象成看作黑箱的过程了，就可以加入优化费用为 cost 的物品不会影响状态 f[0..cost-1]，这是显然的有了这个过程以后，01 背包问题的伪代码就可以这样写：for i=1..NZeroOnePack(c[i],w[i]);初始化的细节问题初始化的细节问题我们看到的求最优解的背包问题题目中，事实上有两种不太相同的问法。
有的 题目要求“恰好装满背包”时的最优解，有的题目则并没有要求必须把背包装 满一种区别这两种问法的实现方法是在初始化的时候有所不同如果是第一种问法，要求恰好装满背包，那么在初始化时除了 f[0]为 0 其它 f[1..V]均设为-∞，这样就可以保证最终得到的 f[N]是一种恰好装满背包的最 优解如果并没有要求必须把背包装满，而是只希望价格尽量大，初始化时应该将 f[0..V]全部设为 0为什么呢？可以这样理解：初始化的 f 数组事实上就是在没有任何物品可以放 入背包时的合法状态如果要求背包恰好装满，那么此时只有容量为 0 的背包 可能被价值为 0 的 nothing“恰好装满”，其它容量的背包均没有合法的解， 属于未定义的状态，它们的值就都应该是-∞了如果背包并非必须被装满，那 么任何容量的背包都有一个合法解“什么都不装”，这个解的价值为 0，所以 初始时状态的值也就全部为 0 了极好很全这个小技巧完全可以推广到其它类型的背包问题，后面也就不再对进行状态转 移之前的初始化进行讲解小结小结01 背包问题是最基本的背包问题，它包含了背包问题中设计状态、方程的最基 本思想，另外，别的类型的背包问题往往也可以转换成 01 背包问题求解。
故一 定要仔细体会上面基本思路的得出方法，状态转移方程的意义，以及最后怎样 优化的空间复杂度首页极好很全P02:P02: 完全背包问题完全背包问题题目题目有 N 种物品和一个容量为 V 的背包，每种物品都有无限件可用第 i 种物品的 费用是 c[i]，价值是 w[i]求解将哪些物品装入背包可使这些物品的费用总和 不超过背包容量，且价值总和最大基本思路基本思路这个问题非常类似于 01 背包问题，所不同的是每种物品有无限件也就是从每 种物品的角度考虑，与它相关的策略已并非取或不取两种，而是有取 0 件、取 1 件、取 2 件……等很多种如果仍然按照解 01 背包时的思路，令 f[i][v]表 示前 i 种物品恰放入一个容量为 v 的背包的最大权值仍然可以按照每种物品 不同的策略写出状态转移方程，像这样：f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0=w[j]，则将物品 j 去掉，不用考虑这个优化的正确性显然： 任何情况下都可将价值小费用高得 j 换成物美价廉的 i，得到至少不会更差的 方案对于随机生成的数据，这个方法往往会大大减少物品的件数，从而加快 速度然而这个并不能改善最坏情况的复杂度，因为有可能特别设计的数据可 以一件物品也去不掉。
这个优化可以简单的 O(N^2)地实现，一般都可以承受另外，针对背包问题而 言，比较不错的一种方法是：首先将费用大于 V 的物品去掉，然后使用类似计 数排序的做法，计算出费用相同的物品中价值最高的是哪个，可以 O(V+N)地完 成这个优化这个不太重要的过程就不给出伪代码了，希望你能独立思考写出 伪代码或程序转化为转化为 0101 背包问题求解背包问题求解极好很全既然 01 背包问题是最基本的背包问题，那么我们可以考虑把完全背包问题转化 为 01 背包问题来解最简单的想法是，考虑到第 i 种物品最多选 V/c[i]件， 于是可以把第 i 种物品转化为 V/c[i]件费用及价值均不变的物品，然后求解这 个 01 背包问题这样完全没有改进基本思路的时间复杂度，但这毕竟给了我们 将完全背包问题转化为 01 背包问题的思路：将一种物品拆成多件物品更高效的转化方法是：把第 i 种物品拆成费用为 c[i]*2^k、价值为 w[i]*2^k 的若干件物品，其中 k 满足 c[i]*2^k0 的最大整数例如， 如果 n[i]为 13，就将这种物品分成系数分别为 1,2,4,6 的四件物品分成的这几件物品的系数和为 n[i]，表明不可能取多于 n[i]。