背包问题九讲v1.doc

背包问题九讲 v1.0  HYPERLINK Pack/Pack/Index.html \l sec2#sec2目录 HYPERLINK \l _P01:_01背包问题第一讲 01背包问题 HYPERLINK \l _P02:_完全背包问题第二讲 完全背包问题 HYPERLINK \l _P03:_多重背包问题第三讲 多重背包问题 HYPERLINK \l _P04:_混合三种背包问题第四讲 混合三种背包问题 HYPERLINK \l _P05:_二维费用的背包问题第五讲 二维费用的背包问题 HYPERLINK \l sec12第六讲 分组的背包问题 HYPERLINK \l _P07:_有依赖的背包问题第七讲 有依赖的背包问题 HYPERLINK \l _P08:_泛化物品第八讲 泛化物品 HYPERLINK \l _P09:_背包问题问法的变化第九讲 背包问题问法的变化 HYPERLINK \l _附：USACO中的背包问题附：USACO中的背包问题 前言 本篇文章???我(dd_engi)正在进行中的一个雄心勃勃的写作计划的一部分，这个计划的内容是写作一份较为完善的NOIP难度的动态规划总结，名为《解动态规划题的基本思考方式》。现在你看到的是这个写作计划最先发布的一部分。 背包问题是一个经典的动态规划模型。它既简单形象容易理解，又在某种程度上能够揭示动态规划的本质，故不少教材都把它作为动态规划部分的第一道例题，我也将它放在我的写作计划的第一部分。 读本文最重要的是思考。因为我的语言和写作方式向来不以易于理解为长，思路也偶有跳跃的地方，后面更有需要大量思考才能理解的比较抽象的内容。更重要的是：不大量思考，绝对不可能学好动态规划这一信息学奥赛中最精致的部分。 你现在看到的是本文的1.0正式版。我会长期维护这份文本，把大家的意见和建议融入其中，也会不断加入我在OI学习以及将来可能的ACM-ICPC的征程中得到的新的心得。但目前本文还没有一个固定的发布页面，想了解本文是否有更新版本发布，可以在 HYPERLINK /bbs/ OIBH论坛中以“背包问题九讲”为关键字搜索贴子，每次比较重大的版本更新都会在这里发贴公布。 目录 HYPERLINK \l _P01:_01背包问题 \o p01第一讲 01背包问题 这是最基本的背包问题，每个物品最多只能放一次。 HYPERLINK \l _P02:_完全背包问题第二讲 完全背包问题 第二个基本的背包问题模型，每种物品可以放无限多次。 HYPERLINK \l _P03:_多重背包问题第三讲 多重背包问题 每种物品有一个固定的次数上限。 HYPERLINK \l _P04:_混合三种背包问题第四讲 混合三种背包问题 将前面三种简单的问题叠加成较复杂的问题。 HYPERLINK \l _P05:_二维费用的背包问题第五讲 二维费用的背包问题 一个简单的常见扩展。 HYPERLINK \l sec12 \o P06第六讲 分组的背包问题 一种题目类型，也是一个有用的模型。后两节的基础。 HYPERLINK \l _P07:_有依赖的背包问题第七讲 有依赖的背包问题 另一种给物品的选取加上限制的方法。 HYPERLINK \l _P08:_泛化物品第八讲 泛化物品 我自己关于背包问题的思考成果，有一点抽象。 HYPERLINK \l _P09:_背包问题问法的变化第九讲 背包问题问法的变化 试图触类旁通、举一反三。 HYPERLINK \l _附：USACO中的背包问题附：USACO中的背包问题 给出 USACO Training 上可供练习的背包问题列表，及简单的解答。 联系方式 如果有任何意见和建议，特别是文章的错误和不足，或者希望为文章添加新的材料，可以通过 HYPERLINK /user/tianyi/ /user/tianyi/这个网页联系我。 致谢 感谢以下名单： 阿坦 jason911 donglixp 他们每人都最先指出了本文第一个beta版中的某个并非无关紧要的错误。谢谢你们如此仔细地阅读拙作并弥补我的疏漏。 感谢 XiaQ，它针对本文的第一个beta版发表了用词严厉的六条建议，虽然我只认同并采纳了其中的两条。在所有读者几乎一边倒的赞扬将我包围的当时，你的贴子是我的一剂清醒剂，让我能清醒起来并用更严厉的眼光审视自己的作品。 当然，还有用各种方式对我表示鼓励和支持的几乎无法计数的同学。不管是当面赞扬，或是在论坛上回复我的贴子，不管是发来热情洋溢的邮件，或是在即时聊天的窗口里竖