经典动态规划问题举例详解
需积分: 50 29 浏览量
2011-06-04
10:34:43
上传
评论
收藏 61KB DOC 举报
动态规划之经典 01 背包问题
经典的 01 背包问题
对于动态规划，每个刚接触的人都需要一段时间来理解，特别是第一次接触的时候总
是想不通为什么这种方法可行，这篇文章就是为了帮助大家理解动态规划，并通过讲解基
本的 01 背包问题来引导读者如何去思考动态规划。本文力求通俗易懂，无异性，不让读
者感到迷惑，引导读者去思考，所以如果你在阅读中发现有不通顺的地方，让你产生错误
理解的地方，让你难得读懂的地方，请跟贴指出，谢谢！
----第一节----初识动态规划--------
经典的 01 背包问题是这样的：
有一个包和 n 个物品，包的容量为 m，每个物品都有各自的体积和价值，问当从这 n
个物品中选择多个物品放在包里而物品体积总数不超过包的容量 m 时，能够得到的最大价
值是多少？[对于每个物品不可以取多次，最多只能取一次，之所以叫做 01 背包，0 表示不
取，1 表示取]
为了用一种生动又更形象的方式来讲解此题，我把此题用另一种方式来描述，如下：
有一个国家，所有的国民都非常老实憨厚，某天他们在自己的国家发现了十座金矿，
并且这十座金矿在地图上排成一条直线，国王知道这个消息后非常高兴，他希望能够把这
些金子都挖出来造福国民，首先他把这些金矿按照在地图上的位置从西至东进行编号，依
次为 0、1、2、3、4、5、6、7、8、9，然后他命令他的手下去对每一座金矿进行勘测，以
便知道挖取每一座金矿需要多少人力以及每座金矿能够挖出多少金子，然后动员国民都来
挖金子。
题目补充 1：挖每一座金矿需要的人数是固定的，多一个人少一个人都不行。国王知
道每个金矿各需要多少人手，金矿 i 需要的人数为 p[i]。
题目补充 2：每一座金矿所挖出来的金子数是固定的，当第 i 座金矿有 p[i]人去挖的话，
就一定能恰好挖出 g[i]个金子。否则一个金子都挖不出来。
题目补充 3：开采一座金矿的人完成开采工作后，他们不会再次去开采其它金矿，因
此一个人最多只能使用一次。
题目补充 4：国王在全国范围内仅招募到了 10000 名愿意为了国家去挖金子的人，因
此这些人可能不够把所有的金子都挖出来，但是国王希望挖到的金子越多越好。
题目补充 5：这个国家的每一个人都很老实（包括国王），不会私吞任何金子，也不
会弄虚作假，不会说谎话。
题目补充 6：有很多人拿到这个题后的第一反应就是对每一个金矿求出平均每个人能
挖出多少金子，然后从高到低进行选择，这里要强调这种方法是错的，如果你也是这样想
的，请考虑背包模型，当有一个背包的容量为 10，共有 3 个物品，体积分别是 3、3、5，
价值分别是 6、6、9，那么你的方法取到的是前两个物品，总价值是 12，但明显最大值是
后两个物品组成的 15。
第 1 页 共 12 页
剩余11页未读，继续阅读
资源评论
