背包问题九讲.pdfVIP

目 录 前言 第一讲 01背包问题 第二讲 完全背包问题 第三讲 多重背包问题 第四讲 混合三种背包问题 第五讲 二维费用的背包问题 第六讲 分组的背包问题 第七讲 有依赖的背包问题 第八讲 泛化物品 第九讲 背包问题问法的变化 附录一 ：USACO中的背包问题 附录二 ：背包问题的有哪些信誉好的足球投注网站解法 联系方式 致谢 本文档使用 看云 构建 - 2 - 前言 前言 原文出处 ：http///pack 本篇文章是我(dd_engi)正在进行中的一个雄心勃勃的写作计划的一部分 ，这个计划的内容是写作一份较 为完善的NOIP难度的动态规划总结 ，名为 《解动态规划题的基本思考方式》。现在你看到的是这个写作 计划最先发布的一部分。 背包问题是一个经典的动态规划模型。它既简单形象容易理解 ，又在某种程度上能够揭示动态规划的本 质 ，故不少教材都把它作为动态规划部分的第一道例题 ，我也将它放在我的写作计划的第一部分。 读本文最重要的是思考。因为我的语言和写作方式向来不以易于理解为长 ，思路也偶有跳跃的地方 ，后面 更有需要大量思考才能理解的比较抽象的内容。更重要的是 ：不大量思考 ，绝对不可能学好动态规划这一 信息学奥赛中最精致的部分。 你现在看到的是本文的v1.1版 ，发布于2007年11月15日。我会长期维护这份文本 ，把大家的意见和建议 融入其中 ，也会不断加入我在OI学习以及将来可能的ACM-ICPC的征程中得到的新的心得。但目前本文还 没有一个固定的发布页面 ，想了解本文是否有更新版本发布 ，可以在OIBH论坛中以 “背包问题九讲”为 关键字有哪些信誉好的足球投注网站贴子 ，每次比较重大的版本更新都会在这个论坛里发贴公布。也可以用 “背包问题九讲”为关 键字在有哪些信誉好的足球投注网站引擎中有哪些信誉好的足球投注网站以得到必威体育精装版版本。 本文档使用 看云 构建 - 3 - 第一讲 01背包问题 第一讲 01背包问题 题目 有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(VN) ，其中时间复杂度应该已经不能再优化了 ，但空间复杂度却可以 优化到O。 先考虑上面讲的基本思路如何实现 ，肯定是有一个主循环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..N for v V ..0 f[v] max{f[v],f[v-c[i]]+w[i]}; 其中