ACM讲座一：平台输入动态规划 (2).ppt
48页
ACM讲座一袁文亮 2010.10 主要内容v平台的使用v时间控制v输入v动态规划 讲在前面的话v一方面天天上网玩，一方面觉的无聊空虚v今天你AC了吗？v坚持，再坚持 1 平台的使用v中国第一个OJ平台： v中文题目比较多的OJ平台： v先注册v打开 problems 选项，将看到很多题目v用本机的编译器编译无错误后，submitv查看Status ，是否AC，没有AC，看返回的信息是什么，修改再提交 题目是英文的问题v使用翻译v习惯英文题目，有助于英语水平的提高 2 时间的控制v每个题目都有时间限制 尽可能的少使用for的3级嵌套循环 尽可能的少使用三维数组 尽可能的少使用浮点型计算 v#include 主要有如下几种：直接输入：Int a ,b;while(cin >> a >> b) cout << a+b << endl; for(int a, b;cin>>a>>b;) cout<< a+b;int a,b; while(scanf("%d %d",&a, &b) != EOF) printf("%d\n",a+b); 文件输入： 输入的文件名为“shuru.in”v输入样例：v100 5v77 92v22 22v29 87v50 46v99 90 v ifstream inputFile("shuru.in");v inputFile>>peopleTotal>>n;v for(int i=0; i v动态规划是一种用途很广泛的问题求解方法，它本身并不是一个特定的算法，而是一种思想，一种手段 经典的01背包问题 v经典的01背包问题是这样的：v有一个包和n个物品，包的容量为m，每个物品都有各自的体积和价值，问当从这n个物品中选择多个物品放在包里而物品体积总数不超过包的容量m时，能够得到的最大价值是多少？[对于每个物品不可以取多次，最多只能取一次，之所以叫做01背包，0表示不取，1表示取]v为了用一种生动又更形象的方式来讲解此题，我把此题用另一种方式来描述，如下：v有一个国家，所有的国民都非常老实憨厚，某天他们在自己的国家发现了十座金矿，并且这十座金矿在地图上排成一条直线，国王知道这个消息后非常高兴，他希望能够把这些金子都挖出来造福国民，首先他把这些金矿按照在地图上的位置从西至东进行编号，依次为0、1、2、3、4、5、6、7、8、9，然后他命令他的手下去对每一座金矿进行勘测，以便知道挖取每一座金矿需要多少人力以及每座金矿能够挖出多少金子，然后动员国民都来挖金子 v题目补充1：挖每一座金矿需要的人数是固定的，多一个人少一个人都不行国王知道每个金矿各需要多少人手，金矿i需要的人数为peopleNeeded[i]。 v题目补充2：每一座金矿所挖出来的金子数是固定的，当第i座金矿有peopleNeeded[i]人去挖的话，就一定能恰好挖出gold[i]个金子否则一个金子都挖不出来v题目补充3：开采一座金矿的人完成开采工作后，他们不会再次去开采其它金矿，因此一个人最多只能使用一次v题目补充4：国王在全国范围内仅招募到了10000名愿意为了国家去挖金子的人，因此这些人可能不够把所有的金子都挖出来，但是国王希望挖到的金子越多越好v题目补充5：这个国家的每一个人都很老实（包括国王），不会私吞任何金子，也不会弄虚作假，不会说谎话v题目补充6：有很多人拿到这个题后的第一反应就是对每一个金矿求出平均每个人能挖出多少金子，然后从高到低进行选择，这里要强调这种方法是错的，如果你也是这样想的，请考虑背包模型，当有一个背包的容量为10，共有3个物品，体积分别是3、3、5，价值分别是6、6、9，那么你的方法取到的是前两个物品，总价值是12，但明显最大值是后两个物品组成的15v题目补充7：我们只需要知道最多可以挖出多少金子即可，而不用关心哪些金矿挖哪些金矿不挖v那么，国王究竟如何知道在只有10000个人的情况下最多能挖出多少金子呢？国王是如何思考这个问题的呢？ v国王首先来到了第9个金矿的所在地（注意，第9个就是最后一个，因为是从0开始编号的，最西边的那个金矿是第0个），他的臣子告诉他，如果要挖取第9个金矿的话就需要1500个人，并且第9个金矿可以挖出8888个金子。 听到这里国王哈哈大笑起来，因为原先他以为要知道十个金矿在仅有10000个人的情况下最多能挖出多少金子是一件很难思考的问题，但是，就在刚才听完他的臣子所说的那句话时，国王已经知道总共最多能挖出多少金子了，国王是如何在不了解其它金矿的情况下知道最多能挖出多少金子的呢？他的臣子们也不知道这个谜，因此他的臣子们就问他了：“最聪明的国王陛下，我们都没有告诉您其它金矿的情况，您是如何知道最终答案的呢？”v得意的国王笑了笑，然后把他最得意的“左、右手”叫到跟前，说到：“我并不需要考虑最终要挖哪些金矿才能得到最多的金子，我只需要考虑我面前的这座金矿就可以了，对于我面前的这座金矿不外乎仅有两种选择，要么挖，要么不挖，对吧？”v“当然，当然”大臣们回答倒v国王继续说道：“如果我挖取第9座金矿的话那么我现在就能获得8888个金子，而我将用去1500个人，那么我还剩下8500个人我亲爱的左部下，如果你告诉我当我把所有剩下的8500个人和所有剩下的其它金矿都交给你去开采你最多能给我挖出多少金子的话，那么我不就知道了在第9个金矿一定开采的情况下所能得到的最大金币数吗？”v国王的左部下听后回答道：“国王陛下，您的意思是如果我能用8500个人在其它金矿最多开采出x个金币的话，那您一共就能够获得x + 8888个金子，对吗？”v“是啊，是啊……如果第9座金矿一定开采的话……”大臣们点头说到。 v国王笑着继续对着他的右部下说到：“亲爱的右部下，也许我并不打算开采这第9座金矿，那么我依然拥有10000个人，如果我把这10000个人和剩下的金矿都给你的话，你最多能给我挖出多少个金子呢？”v国王的右部下聪明地说道：“尊敬的国王陛下，我明白您的意思了，如果我回答最多能购开采出y个金币的话，那您就可以在y和x+8888之间选择一个较大者，而这个较大者就是最终我们能获得的最大金币数，您看我这样理解对吗？” v国王笑得更灿烂了，问他的左部下：“那么亲爱的左部下，我给你8500个人和其余金矿的话你能告诉我最多能挖出多少金子吗？”v“请您放心，这个问题难不倒我”左部下向国王打包票说到v国王高兴地继续问他的右部下：“那右部下你呢，如果我给你10000个人和其余金矿的话你能告诉我最多能挖出多少金子吗？”v“当然能了！交给我吧！”右部下同左部下一样自信地回答道v“那就拜托给你们两位了，现在我要回到我那舒适的王宫里去享受了，我期待着你们的答复国王说完就开始动身回去等消息了，他是多么地相信他的两个大臣能够给他一个准确的答复，因为国王其实知道他的两位大臣要比他聪明得多v故事发展到这里，你是否在想国王的这两个大臣又是如何找到让国王满意的答案的呢？他们为什么能够如此自信呢？事实上他们的确比国王要聪明一些，因为他们从国王的身上学到了一点，就是这一点让他们充满了自信。 v国王走后，国王的左、右部下来到了第8座金矿，早已在那里等待他们的金矿勘测兵向两位大臣报道：“聪明的两位大臣，您们好，第8座金矿需要1000个人才能开采，可以获得7000个金子”v因为国王仅给他的左部下8500个人，所以国王的左部下叫来了两个人，对着其中一个人问到：“如果我给你7500个人和除了第8、第9的其它所有金矿的话，你能告诉我你最多能挖出多少金子吗？” v然后国王的左部下继续问另一个人：“如果我给你8500个人和除了第8、第9的其它所有金矿的话，你能告诉我你最多能挖出多少金子吗？”v国王的左部下在心里想着：“如果他们俩都能回答我的问题的话，那国王交给我的问题不就解决了吗？哈哈哈！”v因为国王给了他的右部下10000个人，所以国王的右部下同样也叫来了两个人，对着其中一个人问：“如果我给你9000个人和除了第8、第9的其它所有金矿的话，你能告诉我你最多能挖出多少金子吗？”v然后国王的右部下继续问他叫来的另一个人：“如果我给你10000个人和除了第8、第9的其它所有金矿的话，你能告诉我你最多能挖出多少金子吗？”v此时，国王的右部下同左部下一样，他们都在为自己如此聪明而感到满足v当然，这四个被叫来的人同样自信地回答没有问题，因为他们同样地从这两个大臣身上学到了相同的一点，而两位自认为自己一样很聪明的大臣得意地笑着回到了他们的府邸，等着别人回答他们提出来的问题，现在你知道了这两个大臣是如何解决国王交待给他们的问题了吗？v那么你认为被大臣叫去的那四个人又是怎么完成大臣交给他们的问题的呢？答案当然是他们找到了另外八个人！v没用多少功夫，这个问题已经在全国传开了，更多人的人找到了更更多的人来解决这个问题，而有些人却不需要去另外找两个人帮他，哪些人不需要别人的帮助就可以回答他们的问题呢？v很明显，当被问到给你z个人和仅有第0座金矿时最多能挖出多少金子时，就不需要别人的帮助，因为你知道，如果z大于等于挖取第0座金矿所需要的人数的话，那么挖出来的最多金子数就是第0座金矿能够挖出来的金子数，如果这z个人不够开采第0座金矿，那么能挖出来的最多金子数就是0，因为这唯一的金矿不够人力去开采。 让我们为这些不需要别人的帮助就可以准确地得出答案的人们鼓掌吧，这就是传说中的底层劳动人民！v故事讲到这里先暂停一下，我们现在重新来分析一下这个故事，让我们对动态规划有个理性认识 v子问题：v国王需要根据两个大臣的答案以及第9座金矿的信息才能判断出最多能够开采出多少金子为了解决自己面临的问题，他需要给别人制造另外两个问题，这两个问题就是子问题v思考动态规划的第一点----最优子结构：v国王相信，只要他的两个大臣能够回答出正确的答案（对于考虑能够开采出的金子数，最多的也就是最优的同时也就是正确的），再加上他的聪明的判断就一定能得到最终的正确答案我们把这种子问题最优时母问题通过优化选择后一定最优的情况叫做“最优子结构”v思考动态规划的第二点----子问题重叠：v实际上国王也好，大臣也好，所有人面对的都是同样的问题，即给你一定数量的人，给你一定数量的金矿，让你求出能够开采出来的最多金子数我们把这种母问题与子问题本质上是同一个问题的情况称为“子问题重叠”然而问题中出现的不同点往往就是被子问题之间传递的参数，比如这里的人数和金矿数 v思考动态规划的第三点----边界：v想想如果不存在前面我们提到的那些底层劳动者的话这个问题能解决吗？永远都不可能！我们把这种子问题在一定时候就不再需要提出子子问题的情况叫做边界，没有边界就会出现死循环。 v思考动态规划的第四点----子问题独立：v要知道，当国王的两个大臣在思考他们自己的问题时他们是不会关心对方是如何计算怎样开采金矿的，因为他们知道，国王只会选择两个人中的一个作为最后方案，另一个人的方案并不会得到实施，因此一个人的决定对另一个人的决定是没有影响的我们把这种一个母问题在对子问题选择时，当前被选择的子问题两两互不影响的情况叫做“子问题独立”v这就是动态规划，具有“最优子结构”、“子问题重叠”、“边界”和“子问题独立”，当你发现你正在思考的问题具备这四个性质的话，那么恭喜你，你基本上已经找到了动态规划的方法 v有了上面的这几点，我们就可以写出动态规划的转移方程式，现在我们来写出对应这个问题的方程式，如果用vgold[mineNum]表示第mineNum个金矿能够挖出的金子数，v用peopleNeeded[mineNum]表示挖第mineNum个金矿需要的人数，v用函数f(people,mineNum)表示当有people个人和编号为0、1、2、3、……、mineNum的金矿时能够得到的最大金子数的话，f(people,mineNum)等于什么呢？或者说f(people,mineNum)的转移方程是怎样的呢？ v当mineNum = 0且people>= peopleNeeded[mineNum]时 f(people,mineNum) = gold[mineNum]v当mineNum = 0且people v#include 讲的通俗一点就是，我们可以把问题的解放在一个变量中，如果再次遇到这个问题就直接从变量中获得答案，因此每一个问题仅会计算一遍，如果不做备忘的话，动态规划就没有任何优势可言了v思考动态规划的第六点----时间分析： 正如上面所说，如果我们用穷举的方法，至少需要2^n个常数时间，因为总共有2^n种情况需要考虑，如果在背包问题中，包的容量为1000，物品数为100，那么需要考虑2^100种情况,这个数大约为10的30次方 而如果用动态规划，最多大概只有1000*100 = 100000个不同的问题，这和10的30次方比起来优势是很明显的而实际情况并不会出现那么多不同的问题，比如在金矿模型中，如果所有的金矿所需人口都是1000个人，那么问题总数大约只有100个 非正式地，我们可以很容易得到动态规划所需时间，如果共有questionCount个相同的子问题，而每一个问题需要面对chooseCount种选择时，我们所需时间就为questionCount * chooseCount个常数在金矿模型中，子问题最多有大概people * n个(其中people是用于开采金矿的总人数，n是金矿的总数)，因此questionCount = people * n，而就像国王需要考虑是采用左部下的结果还是采用右部下的结果一样，每个问题面对两个选择，因此chooseCount = 2,所以程序运行时间为T = O(questionCount * chooseCount) =O(people * n)，别忘了实际上需要的时间小于这个值，根据所遇到的具体情况有所不同。 v那么什么是动态规划呢？我个人觉得，如果一个解决问题的方法满足上面六个思考点中的前四个，那么这个方法就属于动态规划而在思考动态规划方法时，后两点同样也是需要考虑的v面对问题要寻找动态规划的方法，首先要清楚一点，动态规划不是算法，它是一种方法，它是在一件事情发生的过程中寻找最优值的方法，因此，我们需要对这件事情所发生的过程进行考虑而通常我们从过程的最后一步开始考虑，而不是先考虑过程的开始 那么遇到问题如何用动态规划去解决呢？根据上面的分析我们可以按照下面的步骤去考虑：v1、构造问题所对应的过程v2、思考过程的最后一个步骤，看看有哪些选择情况v3、找到最后一步的子问题，确保符合“子问题重叠”，把子问题中不相同的地方设置为参数v4、使得子问题符合“最优子结构”v5、找到边界，考虑边界的各种处理方式v6、确保满足“子问题独立”，一般而言，如果我们是在多个子问题中选择一个作为实施方案，而不会同时实施多个方案，那么子问题就是独立的v7、考虑如何做备忘录v8、分析所需时间是否满足要求v9、写出转移方程式 v例：有一书店引进了一套书，共有3卷，每卷书定价是60元，书店为了搞促销，推出一个活动，活动如下：如果单独购买其中一卷，那么可以打9.5折。 如果同时购买两卷不同的，那么可以打9折如果同时购买三卷不同的，那么可以打8.5折如果小明希望购买第1卷x本，第2卷y本，第3卷z本，那么至少需要多少钱呢？（x、y、z为三个已知整数） v1、过程为一次一次的购买，每一次购买也许只买一本（这有三种方案），或者买两本（这也有三种方案），或者三本一起买（这有一种方案），最后直到买完所有需要的书v2、最后一步我必然会在7种购买方案中选择一种，因此我要在7种购买方案中选择一个最佳情况v3、子问题是，我选择了某个方案后，如何使得购买剩余的书能用最少的钱？并且这个选择不会使得剩余的书为负数母问题和子问题都是给定三卷书的购买量，求最少需要用的钱，所以有“子问题重叠”，问题中三个购买量设置为参数，分别为i、j、kv4、的确符合v5、边界是一次购买就可以买完所有的书，处理方式请读者自己考虑 v6、每次选择最多有7种方案，并且不会同时实施其中多种，因此方案的选择互不影响，所以有“子问题独立”v7、我可以用minMoney[i][j][k]来保存购买第1卷i本，第2卷j本，第3卷k本时所需的最少金钱v8、共有x * y * z个问题，每个问题面对7种选择，时间为：O( x * y * z * 7) = O( x * y* z )。 v9、用函数MinMoney(i,j,k)来表示购买第1卷i本，第2卷j本，第3卷k本时所需的最少金钱，那么有：vMinMoney(i,j,k)=min(s1,s2,s3,s4,s5,s6,s7),其中s1,s2,s3,s4,s5,s6,s7分别为对应的7种方案使用的最少金钱：vs1 = 60 * 0.95 + MinMoney(i-1,j,k)vs2 = 60 * 0.95 + MinMoney(i,j-1,k)vs3 = 60 * 0.95 + MinMoney(i,j,k-1)vs4 = (60 + 60) * 0.9 + MinMoney(i-1,j-1,k)vs5 = (60 + 60) * 0.9 + MinMoney(i-1,j,k-1)vs6 = (60 + 60) * 0.9 + MinMoney(i-1,j,k-1)vs7 = (60 + 60 + 60) * 0.85 + MinMoney(i-1,j-1,k-1) vHDU 1421 搬寝室v搬寝室是很累的,xhd深有体会.时间追述2006年7月9号,那天xhd迫于无奈要从27号楼搬到3号楼,因为10号要封楼了.看着寝室里的n件物品,xhd开始发呆,因为n是一个小于2000的整数,实在是太多了,于是xhd决定随便搬2*k件过去就行了.但还是会很累,因为2*k也不小是一个不大于n的整数.幸运的是xhd根据多年的搬东西的经验发现每搬一次的疲劳度是和左右手的物品的重量差的平方成正比(这里补充一句,xhd每次搬两件东西,左手一件右手一件).例如xhd左手拿重量为3的物品,右手拿重量为6的物品,则他搬完这次的疲劳度为(6-3)^2 = 9.现在可怜的xhd希望知道搬完这2*k件物品后的最佳状态是怎样的(也就是最低的疲劳度),请告诉他吧.Input 每组输入数据有两行,第一行有两个数n,k(2<=2*k<=n<2000).第二行有n个整数分别表示n件物品的重量(重量是一个小于2^15的正整数).Output 对应每组输入数据,输出数据只有一个表示他的最少的疲劳度,每个一行. Sample Input 2 1 1 3 Sample Output 4 给定给定n个物品，每个物品有重量，个物品，每个物品有重量， 从中选出从中选出m对，使得这对，使得这m对物品重量差的平方和最小。 对物品重量差的平方和最小 疲劳度：疲劳度：m对物品重量差的平方和对物品重量差的平方和 分析与解题思路分析与解题思路 先对先对n中物品的重量排序中物品的重量排序 令令dp[i][j]表示前表示前i个物品中选个物品中选j对的最小疲劳度对的最小疲劳度 则则dp[i][j]可能含有第可能含有第i个物品个物品(这种情况下这种情况下,第第i种物品一定是和第种物品一定是和第i-1个物品配个物品配对对)，， 则则dp[i][j]=dp[i-2][j-1]+(w[i]-w[i-1])*(w[i]-w[i-1]) dp[i][j]的的j对也可能不含有第对也可能不含有第i个物品，此时有个物品，此时有 dp[i][j]=dp[i-1][j] 状态转移方程状态转移方程 dp[i][j]=min{dp[i-2][j-1]+(w[i]-w[i-1])*(w[i]-w[i-1]),dp[i-1][j]} v#include 每一步可沿左斜线向下或右斜线向下走 7 5 3 4 2 1 2 1 3 7这个问题的实质实际上是一个有向图中最长路经问题，可以用经典的图论算法或者搜索来解决考虑如何用搜索法来解这道题，从第一个点开始扩展，每次扩展2个可行节点，直到达到数字三角形的底部，从所有的可行路径中找出最优值，这样做的复杂度是o(2^n)，当n很大的时候，普通的搜索法将不可行观察发现，搜索的效率低下很大程度上是因为做了大量的重复运算，因为对于任何一个节点，从他开始向下拓展的最优值是确定的，这启发了我们应当充分利用之前的运算结果下面我们来进行深入的分析，假如已经走第I行第J列，此时最大累加和S[I，J]应选S[I-1，J]，S[I-1，J+1]中较大者再加上（I，J）处的值A[I，J]，即下式S[I，J]=A[I，J]+MAX（S[I-1，J]，S[I-1，J+1]）所以我们可以从第一行开始，向下逐行推出每一处位置的最大累加和S，最后从底行的N个S中选出最大的一个即为所求，这种算法的复杂度为o(n^2)，比较搜索法，已经大大的降低了，这种充分利用已经计算出结果的方法，就叫做动态规划 要确定一个问题是否能用动态规划，需要考虑两个方面：一：最优子结构 即一个问题的最优解只取决于其子问题的最优解，也就是说，非最优解对问题的求解没有影响。 我们再来看一个问题：例二：有4个点，分别是A、B、C、D，相邻两点用两条连线，表示两条通行的道路，给出每条道路的长度我们定义从A到D的所有路径中，长度除以4所得余数最小的路径为最优路径求一条最优路径很多初学者往往会认为这道题也可以采用动态规划的方法，但实际并不如此，考虑这种情况假如A-B的两条道路分别为2，3,B-C的两条道路分别为1，4如果采用动态规划，节点B的最优值为2，节点C的最优值2，但际上到达C的最优值应该是0，即3-1这条线路也就是说，C的最优取值不是由B的最优取值决定的，其不具有最优子结构由此可见，并不是所有的“决策问题”都可以用“动态规划”来解决所以，只有当一个问题呈现出最优子结构时，“动态规划”才可能是一个合适的侯选方法二：无后效性即一个问题被划分阶段后，阶段I中的状态只能由阶段I-1中的状态通过状态转移方程得来，与其他状态没有关系，特别是与未发生的状态没有关系，这就是无后效性 Description:某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统但是这种导弹拦截系统有一个缺陷：虽然它能拦截任意高度的导弹，但是每拦截一发导弹，其拦截能力就下降到只能拦截上一次拦截的导弹高度。 某天，雷达捕捉到敌国的导弹来袭，导弹依次飞来，该拦截系统最多能拦截多少导弹呢？Input:输入若干组数据每组数据包括：导弹总个数（正整数<1000），导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数，用空格分隔）若导弹个数为0，则处理结束Output:输出这套系统最多能拦截多少导弹Sample Input:8 3890 2070 1550 3000 2990 1700 1580 650 0 Sample Output:6 问题:递减的,非连续的最长子序列 f[i]:导弹1‥导弹i中可被拦截的最多导弹数(包括拦截导弹i)(1≤i≤n)显然: f[i]={f[j]|导弹j的高度>=导弹i的高度}+1； v01 #include
