【免费】背包问题九讲1_完全背包空间优化资源-CSDN文库

需积分: 0 102 浏览量 2022-08-03 11:33:42 上传评论收藏 8.79MB PDF 举报

资源详情

资源评论

资源推荐

背包问题九讲 2.0 alpha1

崔添翼 (Tianyi Cui, a.k.a. dd_engi)

September 15, 2011

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

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

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

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

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

到的是2.0 alpha1版本，修订历史及最新版本请访问 https://github.com/tianyicui/

pack 查阅。

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

Contents

1 01背包问题 2

1.1 题目 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1.2 基本思路 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

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

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

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

1.6 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

2 完全背包问题 4

2.1 题目 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

2.2 基本思路 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

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

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

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

2.6 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

3 多重背包问题 6

3.1 题目 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

3.2 基本算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

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

3.4 O(VN)的算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

3.5 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

4 混合三种背包问题 8

4.1 问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

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

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

4.4 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

5 二维费用的背包问题 9

5.1 问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

5.2 算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

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

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

5.5 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

6 分组的背包问题 10

6.1 问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

6.2 算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

6.3 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

7 有依赖的背包问题 10

7.1 简化的问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

7.2 算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

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

7.4 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

8 泛化物品 11

8.1 定义 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

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

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

8.4 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

9 背包问题问法的变化 13

9.1 输出方案 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

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

9.3 求方案总数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

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

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

9.6 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

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

}

其中的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背包问题的伪代码就可以这样写：

for i = 1 to N

ZeroOnePack(F, C

, W

)

1.4 初始化的细节问题

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

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

包装满。一种区别这两种问法的实现方法是在初始化的时候有所不同。

剩余14页未读，继续阅读

评论收藏

内容反馈

glowlaw

粉丝: 22
资源: 275

背包问题九讲1

评论0

最新资源

背包问题九讲1

评论0

背包问题九讲

背包问题九讲 2.0 RC1

背包问题九讲.pdf

背包 问题 九讲

背包问题九讲2.0最新版

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

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

ACM背包问题九讲

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

背包九讲1

背包九讲，背包问题九讲

背包九讲问题

背包问题九讲 v1.0

经典背包问题九讲.exe

背包九讲.docx

背包九讲完整版.pdf

背包问题九讲.chm

最新资源

背包问题九讲