动态规划算法章试验报告

1、实验报告实验目的：理解动态规划的基本思想，理解动态规划算法的两个基本要素最优子结构性质 和子问题的重叠性质。熟练掌握典型的动态规划问题。掌握动态规划思想分析 问题的一般方法，对较简单的问题能正确分析，设计出动态规划算法，并能快 速编程实现。实验内容：编程实现讲过的例题：最长公共子序列问题、矩阵连乘问题、凸多边形最优三 角剖分问题、电路布线问题等。本实验中的问题，设计出算法并编程实现。实验过程：1. 最长公共子序列问题1.1问题描述若给定序列X=<Xi, X2,Xm>，则另一序列Z=< Zi , Z2,Zk>是X的子序列是指存在一一 个严格递增的下标序列<ii, i

2、2,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和Y n-1的最长公共子序列；ii. 若XmMy且Zkxn，则Z是X m-1和丫的最长公共子序列；iii. 若XmMy且ZkMy，则Z是X和Yn-1的最长公共子序列。其中 Xm-仁<x1, x2, ,xm1>, Yn-仁<y1, y2, ,yn1> , Zk-仁<z1, z2,

3、zkl>。最长公共子序列问题具有最优子结构性质。用ci,j记录序列Xi和Yj的最长公共子序列的长度。其中 Xi=<x1, x2,xi> Yj=<y1, y2,yj>。当i=0或j=0时，空序列是 Xi和Yj的最长公共子序列，故 ci,j=0。建立递归 关系如下：'0当i=0或j =0时ci,j=t ci -1, j -1 +1当i, j >0且Xj=yj时max® , j -1, ci -1, j p 当 i, j > 0且Xj 芒 yj时1.3程序框图1.4程序源代码#in clude<stdio.h>#i nclude

4、<stri ng.h>in t lcs_le ngth(char x, char y); int mai n()char x100,y100;int len ,i, n;sea nf("%d",&n);for(i=0;i< n;i+)scan f("%s%s",x,y);len=lcs_le ngth(x,y);prin tf("%dn",le n);in t lcs_le ngth(char x, char y) _int m,n ,i,j,l100100;m=strle n(x);n=strle n(y)

5、;for(i=0;i<m+1;i+)li0=0;for(j=0;j< n+1;j+)l0j=0;for(i=1;i<=m;i+)for(j=1;j<=n ;j+)if(xi-1=yj-1)i,j从1开始，但字符串是从 0开始lij=li-1j-1+1;else if(lij-1>li-1j)lij=lij-1;elselij=li-1j;return lm n;2. 矩阵连乘积问题2.1问题描述矩阵A和B可乘的条件是矩阵 A的列数等于矩阵 B的行数。若A是一个p利的矩阵，B是一个qM的矩阵，则其乘积 C=AB是一个p>f的矩阵。由该公式知计算 C=AB总共需

6、要pqr次的数乘。其标准计算公式为：%二£张覘其中1引Sp,若给定n个矩阵A1,A2,An。其中Ai与Ai+1是可乘的，i=1,2,n1。要求计算出这 n 个矩阵的连乘积 A1A2-An。使得数乘的次数最少。2.2算法思想应用动态规划，得到'0i = j递归公式：mij=.r r ir i i + ri +dir i +i -MJ minmik+mk+1j + pi_4PkPj i v ji空叮2.3程序框图2.4程序源代码#i nclude<stdio.h>int N; void main()in t p1O1,i,j,k,r,t,v, n; int m1011

7、01;/int s101101;/sca nf("%d",&N); for(v=0;v<N;v+) scan f("%d",&n);为了跟讲解时保持一致数组从1开始 记录从第i到第j个矩阵连乘的断开位置for(i=0;i<=n ;i+) sca nf("%d",&pi);/读入pi的值（注意：p0到pn共n+1 项)初始化mii=0为i、j相差的值 为行为列for(i=1;i<=n ;i+)/mii=0;for(r=1;r <n ;r+)rfor(i=1;i <n ;i+)/ij=

8、i+r;/j给mij 赋初mij=mi+1j+pi-1*pi*pj;/ sij=i;for(k=i+1;k<j;k+) t=mik+mk+1j+pi-1*pk*pj;if(t<mij)mij=t;/mij取最小值sij=k;prin tf("%dn",m1 n);3. 田忌赛马问题3.1问题描述田忌与齐王赛马，双方各有 n匹马参赛（*=100 ）,每场比赛赌注为 1两黄金，现已知 齐王与田忌的每匹马的速度，并且齐王肯定是按马的速度从快到慢出场，现要你写一个程序帮助田忌计算他最好的结果是赢多少两黄金（输用负数表示）。3.2算法思想先排序，齐王的马的速度放在数组a中

9、，田忌的马的速度放在数组b中。本问题应用的算法是动态规划和贪心算法相结合解决的。从两人的最弱的马入手：若田忌的马快，就让这两匹马比赛；若田忌的马慢，干脆就让他对付齐王最快的马；若两匹马的速度相等，这时有两种选择方案，或者它俩比赛，或者对付齐王最快的马。当 aij-1b：b j-1时当aij-1=b j-1时当 aij-1bj-1时定义子问题：l（i，j）为齐王的从第i匹马开始的j匹马与田忌的最快的j匹马比赛，田忌 所获得的最大收益。Il(i, j -1)l(i 1, j -1)则：l(i, j) =<maxl(i +1,j 1),l(i,j 1)程序具体实现时，为了适合c数据从0开始，稍

10、加变动，定义子问题： l（i , j）为齐王的从第i匹马开始到第i + j匹马共j+1匹马与田忌的最快的j+1匹马比赛，田忌所获得的最大 收益。初始化时：li0表示齐王的第i匹马与田忌最快的马比赛的结果。3.3程序框图#i nclude<stdio.h> void readdata();void ini t();int N, n,a100,b100,l100100;void main()int i,j,k;sca nf("%d",&N);测试例子得个数for(k=0;k<N;k+)readdata(); in it();for(i=n-2;i>

11、;=0;i-) for(j=1;j <n-i;j+)if(ai+j<bj) lij=lij-1+1； else if(ai+j>bj) lij=li+1j-1-1；else if(li+1j-1-1>lij-1) lij=li+1j-1-1； elselij=lij-1；prin tf("%dn",lO n-1);void readdata()int i;马的个数：-sca nf("%d",&n);/for(i=0;i< n;i+)每只马的速度；每只马的速度；对输入的马的速度的无序序列进行排序scan f("

12、;%d",&ai);/ for(i=0;i< n;i+)scan f("%d",&bi);/int* qsort(int a100,int n)/int i,j,t;for(i=0;i< n;i+) for(j=i+1;j <n ;j+) if(ai<aj)t=ai;ai=aj;aj=t;/ for(i=0;i< n;i+)/ prin tf("%3d",ai);/ prin tf("n"); return a; void in it()int i;qsort(a, n);qsort(b ,n);for(i=0;i< n;i+)if(ai<b