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