背包问题九讲
version 1.1 build 20071115
前言
目录
第一讲 01
背包问题
第二讲 完全背包问题
第三讲 多重背包问题
第四讲 混合三种背包问题
第五讲 二维费用的背包问题
第六讲 分组的背包问题
第七讲 有依赖的背包问题
第八讲 泛化物品
第九讲 背包问题问法的变化
附录一： USACO
中的背包问题
附录二：背包问题的搜索解法
联系方式
致谢
前言
本篇文章是我(dd_engi)正在进行中的一个雄心勃勃的写作计划的一部分，这
个计划的内容是写作一份较为完善的 NOIP 难度的动态规划总结，名为《解动
态规划题的基本思考方式》。现在你看到的是这个写作计划最先发布的一部分。
背包问题是一个经典的动态规划模型。它既简单形象容易理解，又在某种程度
上能够揭示动态规划的本质，故不少教材都把它作为动态规划部分的第一道例
题，我也将它放在我的写作计划的第一部分。
读本文最重要的是思考。因为我的语言和写作方式向来不以易于理解为长，思
路也偶有跳跃的地方，后面更有需要大量思考才能理解的比较抽象的内容。更
重要的是：不大量思考，绝对不可能学好动态规划这一信息学奥赛中最精致的
部分。
你现在看到的是本文的 v1.1 版，发布于 2007 年 11 月 15 日。我会长期维护
这份文本，把大家的意见和建议融入其中，也会不断加入我在 OI 学习以及将来
可能的 ACM-ICPC 的征程中得到的新的心得。但目前本文还没有一个固定的发
布页面，想了解本文是否有更新版本发布，可以在 OIBH
论坛 中以“背包问题九
讲”为关键字搜索贴子，每次比较重大的版本更新都会在这个论坛里发贴公布。
也可以用“背包问题九讲”为关键字在搜索引擎中搜索以得到最新版本。
目录
评论1