资源描述：
《动态规划II(含详细c语言代码)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第十课动态规划(II)综合实践考核最长公共子序列1、问题描述我们称序列Z=是序列X=的子序列当且仅当存在严格上升的序列，使得对j=1,2,...,k,有xij=zj。比如Z=是X=的子序列。现在给出两个序列X和Y，你的任务是找到X和Y的最大公共子序列，也就是说要找到一个最长的序列Z，使得Z既是X的子序列也是Y的子序列。输入数据输入包括多组测试数据。每组数据包括一行，给出两个长度不超过20
2、0的字符串，表示两个序列。两个字符串之间由若干个空格隔开。问题描述输出要求对每组输入数据，输出一行，给出两个序列的最大公共子序列的长度。输入样例abcfbcabfcabprogrammingcontestabcdmnp输出样例4202、解题思路用字符数组s1、s2存放两个字符串，用s1[i]表示s1中的第i个字符，s2[j]表示s2中的第j个字符（字符编号从1开始），用s1i表示s1的前i个字符所构成的子串，s2j表示s2的前j个字符构成的子串，MaxLen(i,j)表示s1i和s2j的最长公共子序列的长度，那么
3、递推关系如下：if(i==0
4、
5、j==0)MaxLen(i,j)=0//两个空串的最长公共子序列长度是0elseif(s1[i]==s2[j])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长度的乘积。可以用一个二维数组来存储各个状态下的“值”。本问题的两个子问题，和原问题形式
6、完全一致的，只不过规模小了一点。3、参考程序#include#include#defineMAX_LEN1000charsz1[MAX_LEN];charsz2[MAX_LEN];intaMaxLen[MAX_LEN][MAX_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<=nL
7、ength1;i++)aMaxLen[i][0]=0;for(j=0;j<=nLength2;j++)aMaxLen[0][j]=0;3、参考程序for(i=1;i<=nLength1;i++){for(j=1;j<=nLength2;j++){if(sz1[i]==sz2[j])aMaxLen[i][j]=aMaxLen[i-1][j-1]+1;else{intnLen1=aMaxLen[i][j-1];intnLen2=aMaxLen[i-1][j];if(nLen1>nLen2)aMaxLen[i][j]=
8、nLen1;elseaMaxLen[i][j]=nLen2;}}}printf("%d",aMaxLen[nLength1][nLength2]);}return0;}陪审团的人选1、问题描述在遥远的国家佛罗布尼亚，嫌犯是否有罪，须由陪审团决定。陪审团是由法官从公众中挑选的。先随机挑选n个人作为陪审团的候选人，然后再从这n个人中选m人组成陪审团。选m人的办法是：控方和辩方会根据对候选人的喜欢程度，给所有候选人打分，分值从0到20。为了公平起见，法官选出陪审团的原则是：选出的m个人，必须满足辩方总分和控方总分的
9、差的绝对值最小。如果有多种选择方案的辩方总分和控方总分的之差的绝对值相同，那么选辩控双方总分之和最大的方案即可。最终选出的方案称为陪审团方案。问题描述输入数据输入包含多组数据。每组数据的第一行是两个整数n和m，n是候选人数目，m是陪审团人数。注意，1<=n<=200,1<=m<=20而且m<=n。接下来的n行，每行表示一个候选人的信息，它包含2个整数，先后是控方和辩方对该候选人的打分。候选人按出现的先后从1开始编号。两组有效数据之间以空行分隔。最后一组数据n=m=0输出要求对每组数据，先输出一行，表示答案所属的组
10、号,如'Jury#1','Jury#2',等。接下来的一行要象例子那样输出陪审团的控方总分和辩方总分。再下来一行要以升序输出陪审团里每个成员的编号，两个成员编号之间用空格分隔。每组输出数据须以一个空行结束。问题描述输入样例421223416200输出样例Jury#1Bestjuryhasvalue6forprosecutionandvalue4fordefence:232
