动态规划算法第四章试验报告

实验报告实验目的：理解动态规划的基本思想，理解动态规划算法的两个基本要素最优子结构性质和子问题的重叠性质。熟练掌握典型的动态规划问题。掌握动态规划思想分析问题的一般方法，对较简单的问题能正确分析，设计出动态规划算法，并能快速编程实现。实验内容：编程实现讲过的例题：最长公共子序列问题、矩阵连乘问题、凸多边形最优三角剖分问题、电路布线问题等。本实验中的问题，设计出算法并编程实现。实验过程：1.最长公共子序列问题1.1问题描述若给定序列X=x1,x2,…,xm，则另一序列Z=z1,z2,…,zk是X的子序列是指存在一个严格递增的下标序列i1,i2,…,ik，使得对于所有j=1,2,…,k有即求它们的公共子序列。1.2算法分析设序列X=x1,x2,…,xm和Y=y1,y2,…,yn的一个最长公共子序列Z=z1,z2,…,zk，则：i.若xm=yn，则zk=xm=yn且Zk-1是Xm-1和Yn-1的最长公共子序列；ii.若xm≠yn且zk≠xm，则Z是Xm-1和Y的最长公共子序列；iii.若xm≠yn且zk≠yn，则Z是X和Yn-1的最长公共子序列。其中Xm-1=x1,x2,…,xm-1，Yn-1=y1,y2,…,yn-1，Zk-1=z1,z2,…,zk-1。最长公共子序列问题具有最优子结构性质。用c[i,j]记录序列Xi和Yj的最长公共子序列的长度。其中Xi=x1,x2,…,xi，Yj=y1,y2,…,yj。当i=0或j=0时，空序列是Xi和Yj的最长公共子序列，故c[i,j]=0。建立递归关系如下：时且当时且当时＝或当jii0,],1[],1,[max0,i1]1,1[0j0i0],[yxjijicjicyxjjicjicj1.3程序框图1.4程序源代码#includestdio.h#includestring.hintlcs_length(charx[],chary[]);intmain(){charx[100],y[100];intlen,i,n;scanf(%d,&n);for(i=0;in;i++){scanf(%s%s,x,y);len=lcs_length(x,y);printf(%d\n,len);}}intlcs_length(charx[],chary[]){intm,n,i,j,l[100][100];m=strlen(x);n=strlen(y);for(i=0;im+1;i++)l[i][0]=0;for(j=0;jn+1;j++)l[0][j]=0;for(i=1;i=m;i++)for(j=1;j=n;j++)if(x[i-1]==y[j-1])//i,j从1开始，但字符串是从0开始l[i][j]=l[i-1][j-1]+1;elseif(l[i][j-1]l[i-1][j])l[i][j]=l[i][j-1];elsel[i][j]=l[i-1][j];returnl[m][n];}2.矩阵连乘积问题2.1问题描述矩阵A和B可乘的条件是矩阵A的列数等于矩阵B的行数。若A是一个p×q的矩阵，B是一个q×r的矩阵，则其乘积C=AB是一个p×r的矩阵。由该公式知计算C=AB总共需要pqr次的数乘。其标准计算公式为：若给定n个矩阵{A1,A2,…,An}。其中Ai与Ai+1是可乘的，i=1,2,…,n-1。要求计算出这n个矩阵的连乘积A1A2…An。使得数乘的次数最少。2.2算法思想应用动态规划，得到递归公式：jipppjkmkimjijimjkijki}]][1[]][[{min0]][[12.3程序框图2.4程序源代码#includestdio.hintN;voidmain(){intp[101],i,j,k,r,t,v,n;intm[101][101];//为了跟讲解时保持一致数组从1开始ints[101][101];//记录从第i到第j个矩阵连乘的断开位置scanf(%d,&N);for(v=0;vN;v++){scanf(%d,&n);for(i=0;i=n;i++)scanf(%d,&p[i]);//读入p[i]的值(注意：p[0]到p[n]共n+1项)for(i=1;i=n;i++)//初始化m[i][i]=0m[i][i]=0;for(r=1;rn;r++)//r为i、j相差的值for(i=1;in;i++)//i为行{j=i+r;//j为列m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];//给m[i][j]赋初值s[i][j]=i;for(k=i+1;kj;k++){t=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];if(tm[i][j]){m[i][j]=t;//m[i][j]取最小值s[i][j]=k;}}}printf(%d\n,m[1][n]);}}3.田忌赛马问题3.1问题描述田忌与齐王赛马，双方各有n匹马参赛（n=100），每场比赛赌注为1两黄金，现已知齐王与田忌的每匹马的速度，并且齐王肯定是按马的速度从快到慢出场，现要你写一个程序帮助田忌计算他最好的结果是赢多少两黄金（输用负数表示）。3.2算法思想先排序，齐王的马的速度放在数组a中，田忌的马的速度放在数组b中。本问题应用的算法是动态规划和贪心算法相结合解决的。从两人的最弱的马入手：若田忌的马快，就让这两匹马比赛；若田忌的马慢，干脆就让他对付齐王最快的马；若两匹马的速度相等，这时有两种选择方案，或者它俩比赛，或者对付齐王最快的马。定义子问题：l(i，j)为齐王的从第i匹马开始的j匹马与田忌的最快的j匹马比赛，田忌所获得的最大收益。则：时当时＝当时当]1[]1[)1,1(]1[]1[)}1,(),1,1(max{]1[]1[)1,(),(jbjiajiljbjiajiljiljbjiajiljil程序具体实现时，为了适合c数据从0开始，稍加变动，定义子问题：l(i，j)为齐王的从第i匹马开始到第i＋j匹马共j+1匹马与田忌的最快的j+1匹马比赛，田忌所获得的最大收益。初始化时：l[i][0]表示齐王的第i匹马与田忌最快的马比赛的结果。3.3程序框图3.4程序源代码#includestdio.hvoidreaddata();voidinit();intN,n,a[100],b[100],l[100][100];voidmain(){inti,j,k;scanf(%d,&N);//测试例子得个数for(k=0;kN;k++){readdata();init();for(i=n-2;i=0;i--)for(j=1;jn-i;j++)if(a[i+j]b[j])l[i][j]=l[i][j-1]+1;elseif(a[i+j]b[j])l[i][j]=l[i+1][j-1]-1;elseif(l[i+1][j-1]-1l[i][j-1])l[i][j]=l[i+1][j-1]-1;elsel[i][j]=l[i][j-1];printf(%d\n,l[0][n-1]);}}voidreaddata(){inti;scanf(%d,&n);//马的个数：-for(i=0;in;i++)scanf(%d,&a[i]);//每只马的速度；for(i=0;in;i++)scanf(%d,&b[i]);//每只马的速度；}int*qsort(inta[100],intn)//对输入的马的速度的无序序列进行排序{inti,j,t;for(i=0;in;i++)for(j=i+1;jn;j++)if(a[i]a[j]){t=a[i];a[i]=a[j];a[j]=t;}//for(i=0;in;i++)//printf(%3d,a[i]);//printf(\n);returna;}voidinit(){inti;qsort(a,n);qsort(b,n);for(i=0;in;i++){if(a[i]b[0])l[i][0]=1;elseif(a[i]==b[0])l[i][0]=0;elsel[i][0]=-1;}}实验总结：1.总体的感觉是这次的试验比较难。很容易就与前面的内容混了，特别是在推导递归公式的时候，对于一些特定的问题找不到切入口，还有是在初始条件的缺东上也要好好想想才能相通。2.程序都很短，但对于动态规划的思想还是理解的不是很透彻。自己下来还要再仔细的研究一下。2006年3月3日星期五