背包问题全解（背包九讲）

偶然看到了一个非常好的学习背包相关动态规划的资料，基本涵盖了背包问题的所有内容。跟大家分享，希望有帮助，如果觉得有用也求留个米~

作者 崔添翼
背包问题九讲2.0 beta1.2
https://github.com/tianyicui/pack

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
1
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

zdj199583 发表于 2019-9-12 14:25
是不是逐渐都会抛弃leetcode转向noip母题？

不太清楚 我觉得不会  企业招人 拿 leetcode 作为一杆尺子 已经 能达到筛选人的标准了,
作为面试者 蜗觉得没必要 上纲上线到NOIP的题目 吧
崔添翼  jane street  香港 本科毕业 100w年薪
当时 学校论坛还很轰动   
直到  我看到DP 九讲之后  我一搜 才知道 原来是那位大佬  

我看了V2版本    我觉得 如他所说  理解他的这篇 写作  也需要花费很长时间的  

yanjinbin 发表于 2019-9-11 20:32
看到了 崔添翼 是个 大佬

是不是逐渐都会抛弃leetcode转向noip母题？

请问下 楼主 你现在发的背包问题是全的吗?  是目前最新修改版本吗?   

谢谢分享!

这个很有用，谢谢分享。

正好在看背包，感谢楼主！

看到了 崔添翼 是个 大佬   

谢谢分享 祝福祝福

感谢分享！！