背包问题九讲pdf

背包问题九讲 作者：崔添翼

背包问题九讲 内容简介：

本文题为《背包问题九讲》，从属于《动态规划的思考艺术》系列。这系列文章的第一版于2007年下半年使用EmacsMuse制作，以HTML格式发布到网上，转载众多，有一定影响力。2011年9月，本系列文章由原作者用LATEX重新制作并全面修订，您现在看到的是2.0 alpha1版本，修订历史及最新版本请访问https://github.com/tianyicui/pack查阅。本文版权归原作者所有，采用CC BY-NC-SA协议发布。

01背包问题21.1题目

21.2基本思路

21.3优化空间复杂度

31.4初始化的细节问题

31.5一个常数优化

41.6小结

42完全背包问题

42.1题目

42.2基本思路.

42.3一个简单有效的优化

52.4转化为01

52.5O(V N)的算法

52.6小结

63多重背包问题63.1题目

63.2基本算法

63.3转化为01背包问题.

.73.4O(VN)的算法

73.5小结

74混合三种背包问题

84.1问题

84.201背包与完全背包的混合

84.3再加上多重背包

84.4小结.....

二维费用的背包问题

95.1问题

95.2算法

95.3物品总个数的限制

95.4复整数域上的背包问题

95.5小结

96分组的背包问题

106.1问题

106.2算法

106.3小结

107有依赖的背包问题

107.1简化的问题

107.2算法

107.3较一般的问题

117.4小结

118泛化物品

118.1定义

118.2泛化物品的和

128.3背包问题的泛化物品

128.4小结

139背包问题问法的变化

139.1输出方案

139.2输出字典序最小的最优方案

139.3求方案总数

149.4最优方案的总数

149.5求次优解、第K优解

149.6小结....