动态规划II(含详细c语言代码).ppt

第十课,动态规划(II),综合实践考核,最长公共子序列,1、问题描述,我们称序列Z=是序列X=的子序列当且仅当存在严格上升的序列，使得对j=1,2,.,k,有xij=zj。比如Z=是X=的子序列。现在给出两个序列X和Y，你的任务是找到X和Y的最大公共子序列，也就是说要找到一个最长的序列Z，使得Z既是X的子序列也是Y的子序列。输入数据输入包括多组测试数据。每组数据包括一行，给出两个长度不超过200的字符串，表示两个序列。两个字符串之间由若干个空格隔开。,问题描述,输出要求对每组输入数据，输出一行，给出两个序列的最大公共子序列的长度。输入样例abcfbcabfcabprogrammingcontestabcdmnp输出样例420,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/两个空串的最长公共子序列长度是0elseif(s1i=s2j)MaxLen(i,j)=MaxLen(i-1,j-1)+1;elseMaxLen(i,j)=Max(MaxLen(i,j-1),MaxLen(i-1,j);,2、解题思路,显然本题目的“状态”就是s1中的位置i和s2中的位置j。“值”就是MaxLen(i,j)。状态的数目是s1长度和s2长度的乘积。可以用一个二维数组来存储各个状态下的“值”。本问题的两个子问题，和原问题形式完全一致的，只不过规模小了一点。,3、参考程序,#include#include#defineMAX_LEN1000charsz1MAX_LEN;charsz2MAX_LEN;intaMaxLenMAX_LENMAX_LEN;intmain(void)while(scanf(%s%s,sz1+1,sz2+1)0)intnLength1=strlen(sz1+1);intnLength2=strlen(sz2+1);inti,j;for(i=0;i=nLength1;i+)aMaxLeni0=0;for(j=0;j=nLength2;j+)aMaxLen0j=0;,3、参考程序,for(i=1;inLen2)aMaxLenij=nLen1;elseaMaxLenij=nLen2;printf(%dn,aMaxLennLength1nLength2);return0;,陪审团的人选,1、问题描述,在遥远的国家佛罗布尼亚，嫌犯是否有罪，须由陪审团决定。陪审团是由法官从公众中挑选的。先随机挑选n个人作为陪审团的候选人，然后再从这n个人中选m人组成陪审团。选m人的办法是：控方和辩方会根据对候选人的喜欢程度，给所有候选人打分，分值从0到20。为了公平起见，法官选出陪审团的原则是：选出的m个人，必须满足辩方总分和控方总分的差的绝对值最小。如果有多种选择方案的辩方总分和控方总分的之差的绝对值相同，那么选辩控双方总分之和最大的方案即可。最终选出的方案称为陪审团方案。,问题描述,输入数据输入包含多组数据。每组数据的第一行是两个整数n和m，n是候选人数目，m是陪审团人数。注意，1=n=200,1=m=20而且m0,3、参考程序,i=nMinP_D;j=0;while(fmi+jfmi-j)/绝对值相同时找辩控和最大的k=i+j;elsek=i-j;printf(Jury#%dn,nCaseNo);printf(Bestjuryhasvalue%dforprosecutionandvalue%dfordefence: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,购物问题,1、问题描述,由于换季，ACM商场推出优惠活动，以超低价格出售若干种商品。但是，商场为避免过分亏本，规定某些商品不能同时购买，而且每种超低价商品只能买一件。身为顾客的你想获得最大的实惠，也就是争取节省最多的钱。经过仔细研究过，我们发现，商场出售的超低价商品中，不存在以下这种情况：N(3=n)种商品C1,C2,Cn，其中Ci和Ci+1是不能同时购买的(i=1,2,n-1)，而且C1和Cn也不能同时购买。请编程计算可以节省的最大金额数。,问题描述,输入数据第1行两个整数K,M(1=k=1000)，其中K表示超低价商品数，K种商品的编号依次为1,2,K；M表示不能同时购买的商品对数。接下来K行，第i行有一个整数Xi表示购买编号为i的商品可以节省的金额(1=Xi=100)。再接下来M行，每行两个数A和B，表示A和B不能同时购买，1=A=K，1km;/读入商品种类与不能同时购买商品对数for(i=1;isi;for(i=1;iv1v2;gv1=newnode(v2,gv1);/以插入形成邻接表gv2=newnode(v1,gv2);,3、参考程序,/对每个还没有被访问的结点，以该结点为根生成相应的有根树，对/该树用动态规划的方法求解目标函数，并累加起来作为最终答案for(i=1;igetg(i)?getf(i):getg(i);coutv=0)/该子女没有访问过node*pre=NULL,*temp;for(temp=gloop-v;temp!=NULL;temp=temp-next)if(temp-v=v)break;/邻结点是父亲，跳出pre=temp;if(temp)/从break退出/跳过可回到父亲的边(有根树，向下)if(pre=NULL)gloop-v=gloop-v-next;elsepre-next=temp-next;search(loop-v);/深度搜索下一层,3、参考程序,intgetf(intv)/计算以v为根的子树中选择v时，该子树的最大节省金额数if(funfv=0)/已经计算过returnfunfv;funfv=sv;for(node*loop=gv;loop!=NULL;loop=loop-next)funfv+=getg(loop-v);/逐个累加(不选子女)returnfunfv;intgetg(intv)/计算以i为根的子树中不选择i时，该子树的最大节省金额数if(fungv=0)