背包问题九讲 2.0 alpha1
崔添翼 (Tianyi Cui, a.k.a. dd_engi)
September 15, 2011
本文题为《背包问题九讲》，从属于《动态规划的思考艺术》系列。
这系列文章的第一版于2007年下半年使用EmacsMuse制作，以HTML格式发
布到网上，转载众多，有一定影响力。
2011年9月，本系列文章由原作者用L
A
T
E
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
1
