动态规划_背包九讲

《动态规划_背包九讲》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、背包问题九讲v1.1PDF版2007-7-15PDF修订版本:2010年11月9日目录第一章前言21.1前言...............................................21.2目录...............................................31.3关于PDF版本.........................................3第二章背包问题12.101背包问题......................................

2、.....12.2完全背包问题.........................................32.3多重背包问题.........................................52.4混合三种背包问题......................................62.5二维费用的背包问题.....................................72.6分组的背包问题........................................82.7

3、有依赖的背包问题......................................82.8泛化物品............................................92.9背包问题问法的变化.....................................10第三章附录143.1USACO中的背包问题.....................................143.2背包问题的搜索解法.....................................151

4、第一章前言x1.1前言本篇文章是我(ddengi)正在进行中的一个雄心勃勃的写作计划的一部分，这个计划的内容是写作一份较为完善的NOIP难度的动态规划总结，名为《解动态规划题的基本思考方式》。现在你看到的是这个写作计划最先发布的一部分。背包问题是一个经典的动态规划模型。它既简单形象容易理解，又在某种程度上能够揭示动态规划的本质，故不少教材都把它作为动态规划部分的第一道例题，我也将它放在我的写作计划的第一部分。读本文最重要的是思考。因为我的语言和写作方式向来不以易于理解为长，思路也偶有跳跃的地方，后面更有需要大量思考才能

5、理解的比较抽象的内容。更重要的是：不大量思考，绝对不可能学好动态规划这一信息学奥赛中最精致的部分。你现在看到的是本文的v1.1版，发布于2007年11月15日。我会长期维护这份文本，把大家的意见和建议融入其中，也会不断加入我在OI学习以及将来可能的ACM-ICPC的征程中得到的新的心得。但目前本文还没有一个固定的发布页面，想了解本文是否有更新版本发布，可以在OIBH论坛论坛中以“背包问题九讲”为关键字搜索贴子，每次比较重大的版本更新都会在这个论坛里发贴公布。也可以用“背包问题九讲”为关键字在搜索引擎中搜索以得到最新版本

6、。联系方式联系方式如果有任何意见和建议，特别是文章的错误和不足，或者希望为文章添加新的材料，可以通过http://kontactr.com/user/tianyi/这个网页联系我。值得说明的是，如果有OI方面的问题，例如不明白自己的程序为什么错了或者索要某种算法的源代码，使用这个联系方式可能得不到及时解答。请在OIBH论坛发问。感谢以下名单阿坦jason911donglixpLeafDuo他们每人都最先指出了本文曾经存在的某个并非无关紧要的错误。谢谢你们如此仔细地阅读拙作并弥补我的疏漏。感谢XiaQ，它针对本文的第一个

7、beta版发表了用词严厉的六条建议，虽然我只认同并采纳了其中的两条。在所有读者几乎一边倒的赞扬将我包围的当时，你的贴子是我的一剂清醒剂，让我能清醒起来并用更严厉的眼光审视自己的作品。sta提供了P01中的“一个常数优化”。当然，还有用各种方式对我表示鼓励和支持的几乎无法计数的同学。不管是当面赞扬，或是在论坛上回复我的贴子，不管是发来热情洋溢的邮件，或是在即时聊天的窗口里竖起大拇指，你们的鼓励和支持是支撑我的写作计划的强大动力，也鞭策着我不断提高自身水平，谢谢你们！最后，感谢Emacs这一世界最强大的编辑器的所有贡献者

8、，感谢它的插件EmacsMuse的开发者们，本文的所有编辑工作都借助这两个卓越的自由软件完成。谢谢你们――自由软件社群――为社会提供了如此有生产力的工具。我深深钦佩你们身上体现出的自由软件的精神，没有你们2第一章前言3的感召，我不能完成本文。在你们的影响下，采用自由文档的方式发布本文档，也是我对自由社会事业的微薄努力。x1.2目录