背包九讲完整详解.pdf资源-CSDN文库

需积分: 50 194 浏览量 2020-02-29 20:40:33 上传评论收藏 287KB PDF 举报

资源详情

资源评论

背包问题九讲 2.0 beta1.2

崔添翼 (Tianyi Cui)

2012-05-08

†

本文题为《背包问题九讲》，从属于《动态规划的思考艺术》系列。

这系列文章的第一版于 2007 年下半年使用 EmacsMuse 制作，以 HTML 格式发布

到网上，转载众多，有一定影响力。

2011 年 9 月，本系列文章由原作者用 L

X 重新制作并全面修订，您现在看到的是

2.0 beta 版本，修订历史及最新版本请访问 https://github.com/tianyicui/pack 查阅。

本文版权归原作者所有，采用 CC BY-NC-SA 协议发布。

Contents

1 01 背包问题 3

1.1 题目 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.2 基本思路 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.3 优化空间复杂度 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.4 初始化的细节问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

1.5 一个常数优化 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

1.6 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

2 完全背包问题 5

2.1 题目 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

2.2 基本思路 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

2.3 一个简单有效的优化 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

2.4 转化为 01 背包问题求解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

2.5 O(V N) 的算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

2.6 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

3 多重背包问题 7

3.1 题目 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

3.2 基本算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

3.3 转化为 01 背包问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

3.4 可行性问题 O(V N) 的算法 . . . . . . . . . . . . . . . . . . . . . . . . . . 8

a.k.a. dd_engi

†

Build 20120508120900

3.5 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

4 混合三种背包问题 9

4.1 问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

4.2 01 背包与完全背包的混合 . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

4.3 再加上多重背包 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

4.4 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

5 二维费用的背包问题 10

5.1 问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

5.2 算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

5.3 物品总个数的限制 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

5.4 复整数域上的背包问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

5.5 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

6 分组的背包问题 11

6.1 问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

6.2 算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

6.3 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

7 有依赖的背包问题 12

7.1 简化的问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

7.2 算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

7.3 较一般的问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

7.4 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

8 泛化物品 13

8.1 定义 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

8.2 泛化物品的和 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

8.3 背包问题的泛化物品 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

8.4 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

9 背包问题问法的变化 14

9.1 输出方案 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

9.2 输出字典序最小的最优方案 . . . . . . . . . . . . . . . . . . . . . . . . . . 15

9.3 求方案总数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

9.4 最优方案的总数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

9.5 求次优解、第 K 优解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

9.6 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

1 01 背包问题

1.1 题目

有 N 件物品和一个容量为 V 的背包。放入第 i 件物品耗费的费用是 C

，得到的

价值是 W

。求解将哪些物品装入背包可使价值总和最大。

1.2 基本思路

这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。

用子问题定义状态：即 F [i, v] 表示前 i 件物品恰放入一个容量为 v 的背包可以获得

的最大价值。则其状态转移方程便是：

F [i, v] = max{F [i − 1, v], F [i − 1, v − C

] + W

}

这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。所

以有必要将它详细解释一下：“将前 i 件物品放入容量为 v 的背包中”这个子问题，若

只考虑第 i 件物品的策略（放或不放），那么就可以转化为一个只和前 i − 1 件物品相关

的问题。如果不放第 i 件物品，那么问题就转化为“前 i − 1 件物品放入容量为 v 的背

包中”，价值为 F [i − 1, v]；如果放第 i 件物品，那么问题就转化为“前 i − 1 件物品放

入剩下的容量为 v − C

的背包中”，此时能获得的最大价值就是 F [i − 1, v − C

] 再加上

通过放入第 i 件物品获得的价值 W

。

伪代码如下：

F [0, 0..V ] ← 0

for i ← 1 to N

for v ← C

to V

F [i, v] ← max{F [i − 1, v], F [i − 1, v − C

] + W

}

1.3 优化空间复杂度

以上方法的时间和空间复杂度均为 O(V N )，其中时间复杂度应该已经不能再优化

了，但空间复杂度却可以优化到 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

] 两个子问题递推而来，能否保证在推 F [i, v] 时（也即在第 i 次主循环中

推 F [v] 时）能够取用 F [i − 1, v] 和 F [i − 1, v − C

] 的值呢？

事实上，这要求在每次主循环中我们以 v ← V . . . 0 的递减顺序计算 F [v]，这样才

能保证计算 F [v] 时 F [v − C

] 保存的是状态 F [i − 1, v − C

的值。伪代码如下：

F [0..V ] ←0

for i ← 1 to N

for v ← V to C

F [v] ← max{F [v], F [v − C

] + W

}

也即占用背包的空间容量，后文统一称之为“费用 (cost)”

其中的 F [v] ← max{F [v], F [v − C

] + W

} 一句，恰就对应于我们原来的转移方程，因

为现在的 F [v − C

] 就相当于原来的 F [i − 1, v − C

]。如果将 v 的循环顺序从上面的逆

序改成顺序的话，那么则成了 F [i, v] 由 F [i, v − C

] 推导得到，与本题意不符。

事实上，使用一维数组解 01 背包的程序在后面会被多次用到，所以这里抽象出一

个处理一件 01 背包中的物品过程，以后的代码中直接调用不加说明。

def ZeroOnePack(F, C, W )

for v ← V to C

F [v] ← max(F [v], F [v − C] + W )

有了这个过程以后，01 背包问题的伪代码就可以这样写：

F [0..V ] ←0

for i ← 1 to N

ZeroOnePack(F, C

, W

)

1.4 初始化的细节问题

我们看到的求最优解的背包问题题目中，事实上有两种不太相同的问法。有的题目

要求“恰好装满背包”时的最优解，有的题目则并没有要求必须把背包装满。一种区别

这两种问法的实现方法是在初始化的时候有所不同。

如果是第一种问法，要求恰好装满背包，那么在初始化时除了 F [0] 为 0，其它

F [1..V ] 均设为 −∞，这样就可以保证最终得到的 F [V ] 是一种恰好装满背包的最优解。

如果并没有要求必须把背包装满，而是只希望价格尽量大，初始化时应该将 F [0..V ]

全部设为 0。

这是为什么呢？可以这样理解：初始化的 F 数组事实上就是在没有任何物品可以放

入背包时的合法状态。如果要求背包恰好装满，那么此时只有容量为 0 的背包可以在什

么也不装且价值为 0 的情况下被“恰好装满”，其它容量的背包均没有合法的解，属于

未定义的状态，应该被赋值为 -∞ 了。如果背包并非必须被装满，那么任何容量的背包

都有一个合法解“什么都不装”，这个解的价值为 0，所以初始时状态的值也就全部为 0

了。

这个小技巧完全可以推广到其它类型的背包问题，后面不再对进行状态转移之前的

初始化进行讲解。

1.5 一个常数优化

上面伪代码中的

for i ← 1 to N

for v ← V to C

中第二重循环的下限可以改进。它可以被优化为

for i ← 1 to N

for v ← V to max(V − Σ

, C

)

这个优化之所以成立的原因请读者自己思考。（提示：使用二维的转移方程思考较易。）

剩余16页未读，继续阅读

评论收藏

内容反馈

背包九讲完整详解.pdf

评论0

最新资源

背包九讲完整详解.pdf

评论0

最新资源

相关推荐

背包九讲完整版.pdf

背包九讲完整版

背包九讲(pdf格式)

背包九讲(tianyi cui)

动态规划之背包九讲崔添翼版本

背包九讲完整版c++

背包九讲PDF格式。

背包九讲完整版_背包九讲

《背包九讲》.pdf

背包问题九讲.pdf

背包问题九讲

背包问题九讲背包九讲背包九讲

背包九讲，各种背包问题的分析

背包九讲算法及实现.pdf

经典的背包问题九讲，必看

背包九讲--崔天翼 犇犇 orz

dp 动态规划 背包 专项练习题目

dd大牛的背包九讲 动态规划

背包九讲-2.0

背包问题九讲（非常不错的动态规划讲解，搞ACM必备）

(15页) 背包九讲.pdf

背包九讲最新版pdf

背包九讲V2.pdf

背包问题九讲2.0(13年修订版).pdf

背包九讲--崔天翼犇犇 orz

dp 动态规划背包专项练习题目

dd大牛的背包九讲动态规划