动态规划II含详细c语言代码

1、第十课动态规划(II)综合实践考核最长公共子序列 1、问题描述 我们称序列Z = 是序列X = 的子序列当且仅当存在严格上升的序列，使得对j = 1, 2, . ,k, 有xij = zj。比如Z = 是X = 的子序列。现在给出两个序列X 和Y，你的任务是找到X 和Y 的最大公共子序列，也就是说要找到一个最长的序列Z，使得Z 既是X 的子序列也是Y 的子序列。输入数据输入包括多组测试数据。每组数据包括一行，给出两个长度不超过200 的字符串，表示两个序列。两个字符串之间由若干个空格隔开。问题描述 输出要求 对每组输入数据，输出一行，给出两个序列的最大公共子序列的长度。 输入样例 abcfbc

2、 abfcab programming contest abcd mnp 输出样例 4 2 02、解题思路 用字符数组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

3、-1 ) + 1;else MaxLen(i,j) = Max(MaxLen(i, j-1), MaxLen(i-1, j);2、解题思路 显然本题目的“状态”就是s1 中的位置i 和s2 中的位置j。 “值”就是MaxLen(i, j)。 状态的数目是s1 长度和s2 长度的乘积。可以用一个二维数组来存储各个状态下的“值”。 本问题的两个子问题，和原问题形式完全一致的，只不过规模小了一点。3、参考程序#include #include #define MAX_LEN 1000char sz1MAX_LEN;char sz2MAX_LEN;int aMaxLenMAX_LENMAX_LEN;i

4、nt 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;3、参考程序 for( i = 1;i = nLength1;i + ) for( j = 1; j nLen2 ) aMaxLenij = nLen1; else aM

5、axLenij = nLen2; printf(%dn, aMaxLennLength1nLength2); return 0;陪审团的人选 1、问题描述 在遥远的国家佛罗布尼亚，嫌犯是否有罪，须由陪审团决定。陪审团是由法官从公众中挑选的。先随机挑选n 个人作为陪审团的候选人，然后再从这n 个人中选m 人组成陪审团。选m 人的办法是： 控方和辩方会根据对候选人的喜欢程度，给所有候选人打分，分值从0 到20。为了公平起见，法官选出陪审团的原则是：选出的m 个人，必须满足辩方总分和控方总分的差的绝对值最小。如果有多种选择方案的辩方总分和控方总分的之差的绝对值相同，那么选辩控双方总分之和最大的方案即

6、可。最终选出的方案称为陪审团方案。问题描述输入数据输入包含多组数据。每组数据的第一行是两个整数n 和m，n 是候选人数目，m 是陪审团人数。注意，1=n=200, 1=m=20 而且 m=n。接下来的n 行，每行表示一个候选人的信息，它包含2 个整数，先后是控方和辩方对该候选人的打分。候选人按出现的先后从1开始编号。两组有效数据之间以空行分隔。最后一组数据n=m=0输出要求对每组数据，先输出一行，表示答案所属的组号, 如 Jury #1, Jury #2, 等。接下来的一行要象例子那样输出陪审团的控方总分和辩方总分。再下来一行要以升序输出陪审团里每个成员的编号，两个成员编号之间用空格分隔。每组

7、输出数据须以一个空行结束。问题描述输入样例4 21 22 34 16 20 0输出样例Jury #1Best jury has value 6 for prosecution and value 4 for defence:2 32、解题思路 为叙述方便，将任一选择方案中，辩方总分和控方总分之差简称为“辩控差”，辩方总分和控方总分之和称为“辩控和”。第i 个候选人的辩方总分和控方总分之差记为V(i)，辩方总分和控方总分之和记为S(i)。现用f(j, k)表示，取j 个候选人，使其辩控差为k 的所有方案中，辩控和最大的那个方案（该方案称为“方案f(j, k)”）的辩控和。并且，我们还规定，如果没

8、法选j 个人，使其辩控差为k，那么f(j, k)的值就为-1，也称方案f(j, k)不可行。本题是要求选出m 个人，那么，如果对k 的所有可能的取值，求出了所有的f(m, k) (-20m k 20m)，那么陪审团方案自然就很容易找到了。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) +

9、S(i) 的值最大的那个，那么方案f(j-1, x)再加上候选人i，就演变成了方案 f(j, k)。由上面知一个方案都选了哪些人需要全部记录下来。不妨将方案f(j, k)中最后选的那个候选人的编号，记在二维数组的元素pathjk中。那么方案f(j, k)的倒数第二个人选的编号，就是pathj-1k-Vpathjk。假定最后算出了方案的辩控差是k，那么从pathmk出发，就能顺藤摸瓜一步步求出所有被选中的候选人。2、解题思路 初始条件，只能确定f(0, 0) = 0。由此出发，一步步自底向上递推，就能求出所有的可行方案f(m, k)( -20m k 20m)。实际解题的时候，会用一个二维数组f

10、来存放f(j, k)的值。而且，由于题目中辩控差的值k 可以为负数，而程序中数租下标不能为负数，所以，在程序中不妨将辩控差的值都加上20m，以免下标为负数导致出错，即题目描述中，如果辩控差为0，则在程序中辩控差为20m。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) - * (i

11、nt *) e2);3、参考程序int main(void) int i, j, k; int t1, t2; int n, m; int nMinP_D; /辩控双方总分一样时的辩控差 int nCaseNo;/测试数据编号 nCaseNo=0; scanf(%d%d, &n, &m); while(n+m) nCaseNo+; for(i=1;i=n;i+) scanf(%d%d, &Pi, &Di); memset(f, -1, sizeof(f); memset(Path, 0, sizeof(Path); nMinP_D=m*20; /题目中的辩控差为0 /对应到程序中辩控差就是m*

12、20 f0nMinP_D=0; /选0 个人辩控差为0 的方案，其辩控和就是03、参考程序 for(j=0;jm;j+) /每次循环选出第j 个人，共要选出m 人 for(k=0;k=0) /方案 f(j, k)可行 for(i=1;ifj+1k+Pi-Di) /即时判别记住更合适的f(j,k) t1=j; t2=k; while(t10&Patht1t2!=i) /t2减去编号为Patht1t2的辩控差 t2-=PPatht1t2-DPatht1t2; t1-;/减少1人 if(t1=0) /没有发现 fj+1k+Pi-Di=fjk+Pi+Di; Pathj+1k+Pi-Di=i; 3、参考

13、程序 i=nMinP_D; j=0; while(fmi+j0&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,

14、 sizeof(int), CompareInt); for(i=1;i=m;i+) printf( %d, Answeri); printf(n); printf(n); scanf(%d%d, &n, &m); return 0;购物问题 1、问题描述 由于换季，ACM商场推出优惠活动，以超低价格出售若干种商品。但是，商场为避免过分亏本，规定某些商品不能同时购买，而且每种超低价商品只能买一件。身为顾客的你想获得最大的实惠，也就是争取节省最多的钱。经过仔细研究过，我们发现，商场出售的超低价商品中，不存在以下这种情况：N(3=n)种商品C1,C2,Cn，其中Ci和Ci+1是不能同时购买的(i=

15、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，1=B=K，AB。 输出要求仅一个整数，表示能节省的最大金额数。问题描述输入样例3 11111 2输出样例22、解题思路 本题关键是构造一个结点带权的图，结点表示超低价商品，结点的权值表示购买该商品能节省的金额，边表示

16、边所连的两个点的商品不能同时购买。这样就相当于在图中找出一个点集，使该点集中任两点没有连边而且权值之和最大。 依题意，该图是无环图，所以该图由若干棵树组成。只要把每棵树的相应最大节省金额求出来再求和即得结果。2、解题思路 对于单棵树，可以用动态规划的方法求出结果，方法如下： (1)对该棵树广度或深度遍历生成相应的有向树；(2)对树中每个结点定义两个函数F(i)和G(i)，分别表示以i为根的子树中选择i和不选择i时，该子树的最大节省金额数。另外S(i)表示结点i权值。动态规划方法为： 对叶子结点：F(i)=S(i), G(i)=0 对非叶子结点：F(i)=sum(G(j)+S(i), G(i)=

17、sum(max(F(j),G(j)其中j为i的子女，sum表示对各个子树求和。(3)若该树的根为r，则该树的结果为max(F(r),G(r)。3、参考程序#include#includeusing namespace std;int k, s1001;/商品种类与其节省金额struct node /图结点定义 node(int vv=0, node* nn=NULL) v=vv; next=nn; int v; node *next; *g1001;/gi表示第i个结点相邻的结点组成的链表int tag1001;/标记结点是否搜索过没有,1表示已搜索，0则没有int funf1001, fun

18、g1001;/深度优先遍历该树并生成相应的有根树void search(int v);/搜索出以v为根生成的有根树int getf(int v);/计算以v为根的子树中选择v时，该子树的最大节省金额数int getg(int v);/计算以v为根的子树中不选择v时，该子树的最大节省金额数3、参考程序int main(void) int m, i, v1, v2; int ans = 0; memset(g, 0, sizeof(g);/每个指针初始化为NULL memset(tag, 0, sizeof(tag); memset(funf,-1,sizeof(funf); memset(fun

19、g,-1,sizeof(fung); cin k m;/读入商品种类与不能同时购买商品对数 for(i=1; i si; for(i=1; i v1 v2; gv1=new node(v2,gv1);/以插入形成邻接表 gv2=new node(v1,gv2); 3、参考程序 /对每个还没有被访问的结点，以该结点为根生成相应的有根树，对 /该树用动态规划的方法求解目标函数，并累加起来作为最终答案 for(i=1; i getg(i) ? getf(i) : getg(i); cout next)/对子女依次循环 if(tagloop-v = 0)/该子女没有访问过 node *pre=NULL, *