第十四周递归与动态规划三.ppt

第十四讲,递归与动态规划(三),ACM算法与程序设计,2/28,Help Jimmy,1、问题描述,Help Jimmy 是在下图所示的场景上完成的游戏：,3/28,问题描述,场景中包括多个长度和高度各不相同的平台。地面是最低的平台，高度为零，长度无限。Jimmy 老鼠在时刻0 从高于所有平台的某处开始下落，它的下落速度始终为1 米/秒。当Jimmy 落到某个平台上时，游戏者选择让它向左还是向右跑，它跑动的速度也是1 米/秒。当Jimmy 跑到平台的边缘时，开始继续下落。Jimmy 每次下落的高度不能超过MAX 米，不然就会摔死，游戏也会结束。设计一个程序，计算Jimmy 到地面时可能的最早时间。,4/28,问题描述,输入数据 第一行是测试数据的组数t（0=t=20）。每组测试数据的第一行是四个整数N，X，Y，MAX，用空格分隔。N 是平台的数目（不包括地面），X 和Y 是Jimmy 开始下落的位置的横竖坐标，MAX 是一次下落的最大高度。接下来的N 行每行描述一个平台，包括三个整数，X1i，X2i和Hi。Hi表示平台的高度，X1i和X2i表示平台左右端点的横坐标。1=N=1000，-20000=X,X1i,X2i=20000，0 Hi Y=20000（i=1.N）。所有坐标的单位都是米。Jimmy 的大小和平台的厚度均忽略不计。如果Jimmy 恰好落在某个平台的边缘，被视为落在平台上。所有的平台均不重叠或相连。测试数据保Jimmy 一定能安全到达地面。,5/28,问题描述,输出要求对输入的每组测试数据，输出一个整数，Jimmy 到地面时可能的最早时间。输入样例13 8 17 200 10 80 10 134 14 3输出样例23,6/28,2、解题思路,此题目的“子问题”是什么呢？Jimmy 跳到一块板上后，可以有两种选择，向左走或向右走。走到左端和走到右端所需的时间，容易算出。如果我们能知道，以左端为起点到达地面的最短时间，和以右端为起点到达地面的最短时间，那么向左走还是向右走，就很容选择了。因此，整个问题就被分解成两个子问题，即Jimmy 所在位置下方第一块板左端为起点到地面的最短时间，和右端为起点到地面的最短时间。这两个子问题在形式上和原问题是完全一致的。将板子从上到下从1 开始进行无重复的编号(高度相同的板子，哪块编号在前无所谓)，那么，和上面两个子问题相关的变量就只有板子的编号。,7/28,2、解题思路,所以，本题目的“状态”就是板子编号，而一个“状态”对应的“值”有两部分，是两个子问题的解，即从该板子左端出发到达地面的最短时间，和从该板子右端出发到达地面的最短时间。不妨认为Jimmy 开始的位置是一个编号为0，长度为0 的板子，假设LeftMinTime(k)表示从k 号板子左端到地面的最短时间，RightMinTime(k)表示从k 号板子右端到地面的最短时间，那么，求板子k 左端点到地面的最短时间的方法如下：if(板子k 左端正下方没有别的板子)if(板子k 的高度 h(k)大于Max)LeftMinTime(k)=;else LeftMinTime(k)=h(k);else if(板子k 左端正下方的板子编号是m)LeftMinTime(k)=h(k)-h(m)+Min(LeftMinTime(m)+Lx(k)-Lx(m),RightMinTime(m)+Rx(m)-Lx(k);,8/28,2、解题思路,上面，h(i)就代表i 号板子的高度，Lx(i)就代表i 号板子左端点的横坐标，Rx(i)就代表i号板子右端点的横坐标。那么 h(k)-h(m)当然就是从k 号板子跳到m 号板子所需要的时间，Lx(k)-Lx(m)就是从m 号板子的落脚点走到m 号板子左端点的时间，Rx(m)-Lx(k)就是从m号板子的落脚点走到右端点所需的时间。求RightMinTime(k)的过程类似。不妨认为Jimmy 开始的位置是一个编号为0，长度为0 的板子，那么整个问题就是要求LeftMinTime(0)。输入数据中，板子并没有按高度排序，所以程序中一定要首先将板子排序。,9/28,3、参考程序,#include#include#include#define MAX_N 1000#define INFINITE 1000000int t,n,x,y,max;struct Platform int Lx,Rx,h;Platform aPlatformMAX_N+10;int aLeftMinTimeMAX_N+10;int aRightMinTimeMAX_N+10;int MyCompare(const void*e1,const void*e2)Platform*p1,*p2;p1=(Platform*)e1;p2=(Platform*)e2;return p2-h-p1-h;/从大到小排列,10/28,3、参考程序,int MinTime(int L,bool bLeft)int y=aPlatformL.h;int i,x;if(bLeft)x=aPlatformL.Lx;else x=aPlatformL.Rx;for(i=L+1;i=x)break;if(i max)/太高 return INFINITE;,11/28,3、参考程序,else/没找到 if(y max)/离地面太高 return INFINITE;else return y;/特殊情况处理完毕 int nLeftTime=y-aPlatformi.h+x-aPlatformi.Lx;int nRightTime=y-aPlatformi.h+aPlatformi.Rx-x;if(aLeftMinTimei=-1)/还没有存储值 aLeftMinTimei=MinTime(i,true);if(aRightMinTimei=-1)aRightMinTimei=MinTime(i,false);nLeftTime+=aLeftMinTimei;nRightTime+=aRightMinTimei;if(nLeftTime nRightTime)return nLeftTime;return nRightTime;,12/28,3、参考程序,int main(void)scanf(%d,思考题：重新编写此程序，要求不使用递归函数,13/28,最长公共子序列,1、问题描述,我们称序列Z=是序列X=的子序列当且仅当存在严格上升的序列，使得对j=1,2,.,k,有xij=zj。比如Z=是X=的子序列。现在给出两个序列X 和Y，你的任务是找到X 和Y 的最大公共子序列，也就是说要找到一个最长的序列Z，使得Z 既是X 的子序列也是Y 的子序列。输入数据输入包括多组测试数据。每组数据包括一行，给出两个长度不超过200 的字符串，表示两个序列。两个字符串之间由若干个空格隔开。,14/28,问题描述,输出要求 对每组输入数据，输出一行，给出两个序列的最大公共子序列的长度。输入样例 abcfbc abfcab programming contest abcd mnp 输出样例 4 2 0,15/28,2、解题思路,用字符数组s1、s2存放两个字符串，用s1i表示s1中的第i 个字符，s2j表示s2中的第j个字符（字符编号从1 开始），用s1i表示s1的前i个字符所构成的子串，s2j表示s2的前j个字符构成的子串，MaxLen(i,j)表示s1i 和s2j 的最长公共子序列的长度，那么递推关系如下：if(i=0|j=0)MaxLen(i,j)=0/两个空串的最长公共子序列长度是0else if(s1i=s2j)MaxLen(i,j)=MaxLen(i-1,j-1)+1;else MaxLen(i,j)=Max(MaxLen(i,j-1),MaxLen(i-1,j);,16/28,2、解题思路,显然本题目的“状态”就是s1 中的位置i 和s2 中的位置j。“值”就是MaxLen(i,j)。状态的数目是s1 长度和s2 长度的乘积。可以用一个二维数组来存储各个状态下的“值”。本问题的两个子问题，和原问题形式完全一致的，只不过规模小了一点。,17/28,3、参考程序,#include#include#define MAX_LEN 1000char sz1MAX_LEN;char sz2MAX_LEN;int aMaxLenMAX_LENMAX_LEN;int main(void)while(scanf(%s%s,sz1+1,sz2+1)0)int nLength1=strlen(sz1+1);int nLength2=strlen(sz2+1);int i,j;for(i=0;i=nLength1;i+)aMaxLeni0=0;for(j=0;j=nLength2;j+)aMaxLen0j=0;,18/28,3、参考程序,for(i=1;i nLen2)aMaxLenij=nLen1;else aMaxLenij=nLen2;printf(%dn,aMaxLennLength1nLength2);return 0;,19/28,陪审团的人选,1、问题描述,在遥远的国家佛罗布尼亚，嫌犯是否有罪，须由陪审团决定。陪审团是由法官从公众中挑选的。先随机挑选n 个人作为陪审团的候选人，然后再从这n 个人中选m 人组成陪审团。选m 人的办法是：控方和辩方会根据对候选人的喜欢程度，给所有候选人打分，分值从0 到20。为了公平起见，法官选出陪审团的原则是：选出的m 个人，必须满足辩方总分和控方总分的差的绝对值最小。如果有多种选择方案的辩方总分和控方总分的之差的绝对值相同，那么选辩控双方总分之和最大的方案即可。最终选出的方案称为陪审团方案。,20/28,问题描述,输入数据输入包含多组数据。每组数据的第一行是两个整数n 和m，n 是候选人数目，m 是陪审团人数。注意，1=n=200,1=m=20 而且 m=n。接下来的n 行，每行表示一个候选人的信息，它包含2 个整数，先后是控方和辩方对该候选人的打分。候选人按出现的先后从1开始编号。两组有效数据之间以空行分隔。最后一组数据n=m=0输出要求对每组数据，先输出一行，表示答案所属的组号,如 Jury#1,Jury#2,等。接下来的一行要象例子那样输出陪审团的控方总分和辩方总分。再下来一行要以升序输出陪审团里每个成员的编号，两个成员编号之间用空格分隔。每组输出数据须以一个空行结束。,21/28,问题描述,输入样例4 21 22 34 16 20 0输出样例Jury#1Best jury has value 6 for prosecution and value 4 for defence:2 3,22/28,2、解题思路,为叙述方便，将任一选择方案中，辩方总分和控方总分之差简称为“辩控差”，辩方总分和控方总分之和称为“辩控和”。第i 个候选人的辩方总分和控方总分之差记为V(i)，辩方总分和控方总分之和记为S(i)。现用f(j,k)表示，取j 个候选人，使其辩控差为k 的所有方案中，辩控和最大的那个方案（该方案称为“方案f(j,k)”）的辩控和。并且，我们还规定，如果没法选j 个人，使其辩控差为k，那么f(j,k)的值就为-1，也称方案f(j,k)不可行。本题是要求选出m 个人，那么，如果对k 的所有可能的取值，求出了所有的f(m,k)(-20m k 20m)，那么陪审团方案自然就很容易找到了。,23/28,2、解题思路,问题的关键是建立递推关系。显然，方案f(j,k)是由某个可行的方案f(j-1,x)(-20m x 20m)演化而来的。可行方案f(j-1,x)能演化成方案f(j,k)的必要条件是：存在某个候选人i，i 在方案f(j-1,x)中没有被选上，且x+V(i)=k。在所有满足该必要条件的f(j-1,x)中，选出 f(j-1,x)+S(i)的值最大的那个，那么方案f(j-1,x)再加上候选人i，就演变成了方案 f(j,k)。由上面知一个方案都选了哪些人需要全部记录下来。不妨将方案f(j,k)中最后选的那个候选人的编号，记在二维数组的元素pathjk中。那么方案f(j,k)的倒数第二个人选的编号，就是pathj-1k-Vpathjk。假定最后算出了方案的辩控差是k，那么从pathmk出发，就能顺藤摸瓜一步步求出所有被选中的候选人。,24/28,2、解题思路,初始条件，只能确定f(0,0)=0。由此出发，一步步自底向上递推，就能求出所有的可行方案f(m,k)(-20m k 20m)。实际解题的时候，会用一个二维数组f 来存放f(j,k)的值。而且，由于题目中辩控差的值k 可以为负数，而程序中数租下标不能为负数，所以，在程序中不妨将辩控差的值都加上20m，以免下标为负数导致出错，即题目描述中，如果辩控差为0，则在程序中辩控差为20m。,25/28,3、参考程序,#include#include#include int f301000;int Path301000;int P300;/控方打分int D300;/辩方打分int Answer30;/存放最终方案的人选int CompareInt(const void*e1,const void*e2)return*(int*)e1)-*(int*)e2);,26/28,3、参考程序,int main(void)int i,j,k;int t1,t2;int n,m;int nMinP_D;/辩控双方总分一样时的辩控差 int nCaseNo;/测试数据编号 nCaseNo=0;scanf(%d%d,/选0 个人辩控差为0 的方案，其辩控和就是0,27/28,3、参考程序,for(j=0;j=0)/方案 f(j,k)可行 for(i=1;ifj+1k+Pi-Di)/即时判别记住更合适的f(j,k)t1=j;t2=k;while(t10,28/28,3、参考程序,i=nMinP_D;j=0;while(fmi+jfmi-j)/绝对值相同时找辩控和最大的 k=i+j;else k=i-j;printf(Jury#%dn,nCaseNo);printf(Best jury has value%d for prosecution and value%d for defence:n,(k-nMinP_D+fmk)/2,(fmk-k+nMinP_D)/2);for(i=1;i=m;i+)Answeri=Pathm-i+1k;k-=PAnsweri-DAnsweri;/减去辩控差 qsort(Answer+1,m,sizeof(int),CompareInt);for(i=1;i=m;i+)printf(%d,Answeri);printf(n);printf(n);scanf(%d%d,