背包问题九讲

背包问题是一个经典的动态规划模型。它既简单形象容易理解,又在某种程度上能够揭示 动态规划的本质,故不少教材都把它作为动态规划部分的第一道例题,我也将它放在我的写作 计划的第一部分。 读本文最重要的是思考。因为我的语言和写作方式向来不以易于理解为长,思路也偶有跳 跃的地方,后面更有需要大量思考才能理解的比较抽象的内容。更重要的是:不大量思考,绝对 不可能学好动态规划这一信息学奥赛中最精致的部分。