ACM讲座一平台输入动态规划.ppt

ACM讲座一 袁文亮 2010.10 主要内容 平台的使用 时间控制 输入 动态规划 讲在前面的话 一方面天天上网玩，一方面觉的无聊空虚 今天你AC了吗？ 坚持，再坚持 1 平台的使用 中国第一个OJ平台： 中文题目比较多的OJ平台： /index.php 2 时间的控制 每个题目都有时间限制 尽可能的少使用for的3级嵌套循环 尽可能的少使用三维数组 尽可能的少使用浮点型计算 3 输入问题 C++输入输出： #include iostream.h“ cini; couti“i”endl; 4 动态规划 动态规划（Dynamic Programming）是20世纪50年代由美国数学家贝尔曼（Richard Bellman）及他的学生们一同建立和发展起来的一种解多阶段决策问题的优化方法 。 动态规划是一种用途很广泛的问题求解方法，它本身并不是一个特定的算法，而是一种思想，一种手段。 经典的01背包问题 经典的01背包问题是这样的： 有一个包和n个物品，包的容量为m，每个物品都有各自的体积和价值，问当从这n个物品中选择多个物品放在包里而物品体积总数不超过包的容量m时，能够得到的最大价值是多少？[对于每个物品不可以取多次，最多只能取一次，之所以叫做01背包，0表示不取，1表示取] 为了用一种生动又更形象的方式来讲解此题，我把此题用另一种方式来描述，如下： 有一个国家，所有的国民都非常老实憨厚，某天他们在自己的国家发现了十座金矿，并且这十座金矿在地图上排成一条直线，国王知道这个消息后非常高兴，他希望能够把这些金子都挖出来造福国民，首先他把这些金矿按照在地图上的位置从西至东进行编号，依次为0、1、2、3、4、5、6、7、8、9，然后他命令他的手下去对每一座金矿进行勘测，以便知道挖取每一座金矿需要多少人力以及每座金矿能够挖出多少金子，然后动员国民都来挖金子。 题目补充1：挖每一座金矿需要的人数是固定的，多一个人少一个人都不行。国王知道每个金矿各需要多少人手，金矿i需要的人数为peopleNeeded[i]。 题目补充2：每一座金矿所挖出来的金子数是固定的，当第i座金矿有peopleNeeded[i]人去挖的话，就一定能恰好挖出gold[i]个金子。否则一个金子都挖不出来。 题目补充3：开采一座金矿的人完成开采工作后，他们不会再次去开采其它金矿，因此一个人最多只能使用一次。 题目补充4：国王在全国范围内仅招募到了10000名愿意为了国家去挖金子的人，因此这些人可能不够把所有的金子都挖出来，但是国王希望挖到的金子越多越好。 题目补充5：这个国家的每一个人都很老实（包括国王），不会私吞任何金子，也不会弄虚作假，不会说谎话。 题目补充6：有很多人拿到这个题后的第一反应就是对每一个金矿求出平均每个人能挖出多少金子，然后从高到低进行选择，这里要强调这种方法是错的，如果你也是这样想的，请考虑背包模型，当有一个背包的容量为10，共有3个物品，体积分别是3、3、5，价值分别是6、6、9，那么你的方法取到的是前两个物品，总价值是12，但明显最大值是后两个物品组成的15。 题目补充7：我们只需要知道最多可以挖出多少金子即可，而不用关心哪些金矿挖哪些金矿不挖。 那么，国王究竟如何知道在只有10000个人的情况下最多能挖出多少金子呢？国王是如何思考这个问题的呢？ 国王首先来到了第9个金矿的所在地（注意，第9个就是最后一个，因为是从0开始编号的，最西边的那个金矿是第0个），他的臣子告诉他，如果要挖取第9个金矿的话就需要1500个人，并且第9个金矿可以挖出8888个金子。听到这里国王哈哈大笑起来，因为原先他以为要知道十个金矿在仅有10000个人的情况下最多能挖出多少金子是一件很难思考的问题，但是，就在刚才听完他的臣子所说的那句话时，国王已经知道总共最多能挖出多少金子了，国王是如何在不了解其它金矿的情况下知道最多能挖出多少金子的呢？他的臣子们也不知道这个谜，因此他的臣子们就问他了：“最聪明的国王陛下，我们都没有告诉您其它金矿的情况，您是如何知道最终答案的呢？” 得意的国王笑了笑，然后把他最得意的“左、右手”叫到跟前，说到：“我并不需要考虑最终要挖哪些金矿才能得到最多的金子，我只需要考虑我面前的这座金矿就可以了，对于我面前的这座金矿不外乎仅有两种选择，要么挖，要么不挖，对吧？” “当然，当然”大臣们回答倒。 国王继续说道：“如果我挖取第9座金矿的话那么我现在就能获得8888个金子，而我将用去1500个人，那么我还剩下8500个人。我亲爱的左部下，如果你告诉我当我把所有剩下的8500个人和所有剩下的其它金矿都交给你去开采你最多能给我挖出多少金子的话，那么我不就知道了在第9个金矿一定开采的情况下所能得到的最大金币数吗