实验二：动态规划

1、实验二：动态规划实验目的：理解动态规划的基本思想，理解动态规划算法的两个基本要素最优子结构性质和 子问题的重叠性质。熟练掌握典型的动态规划问题。掌握动态规划思想分析问题的 一般方法，对较简单的问题能正确分析，设计出动态规划算法，并能快速编程实现。实验内容：编程实现讲过的例题：最长公共子序列问题、滑雪问题、投资问题等。最长公共子序列一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说，若给定 序列X=，则另一序列Z=是X的子序列是指存在一个严格递增 的下标序列 ，使得对于所有户1,2,.,k有解答如下：a)最长公共子序列的结构若用穷举搜索法，耗时太长，算法需要指数时间。易证最长公共

2、子序列问题也有最优子结构性质设序列 X= 和 Y=的一个最长公共子序列 Z=，则：若xm=yn，则zk=xm=yn且Zk1是Xm1和Yn1的最长公共子序列；若x：受且z芦xm %Z是Xm 1和Y的最长公共子序列；若x：手y；且zky：，则Z是X和Yn-1的最长公共子序列。其中 Xm-1=， Yn- 1=， Zk - 1=。最长公共子序列问题具有最优子结构性质。程序如下：#include#includeint lcs_length(char x, char y);int main()char x100,y100;int len;while(1)scanf(%s%s,x,y);if(x0=0)约定

3、第一个字符串以0开始表示结束break;len=lcs_length(x,y);printf(%dn,len);int lcs_length(char x, char y)int m,n,i,j,l100100;m=strlen(x);n=strlen(y);for(i=0;im+1;i+)li0=0;for(j=0;jn+1;j+)l0j=0;for(i=1;i=m;i+)for(j=1;jli-1j)lij=lij-1;elselij=li-1j;return lmn;防卫导弹一种新型的防卫导弹可截击多个攻击导弹。它可以向前飞行，也可以用很快的速度向下 飞行，可以毫无损伤地截击进攻导弹，但

4、不可以向后或向上飞行。但有一个缺点，尽管它发 射时可以达到任意高度，但它只能截击比它上次截击导弹时所处高度低或者高度相同的导 弹。现对这种新型防卫导弹进行测试，在每一次测试中，发射一系列的测试导弹(这些导弹 发射的间隔时间固定，飞行速度相同)，该防卫导弹所能获得的信息包括各进攻导弹的高度， 以及它们发射次序。现要求编一程序，求在每次测试中，该防卫导弹最多能截击的进攻导弹 数量，一个导弹能被截击应满足下列两个条件之一：它是该次测试中第一个被防卫导弹截击的导弹；它是在上一次被截击导弹的发射后发射，且高度不大于上一次被截击导弹的高度的导 弹。输入数据：第一行是一个整数n，以后的n各有一个整数表示导弹

5、的高度。输出数据：截击导弹的最大数目。分析：定义li为选择截击第i个导弹，从这个导弹开始最多能截击的导弹数目。由于选择了第i枚导弹，所以下一个要截击的导弹j的高度要小于等于它的高度，所以 li应该等于从i+1到n的每一个j，满足hj=hi的j中lj的最大值。程序如下：#includeint main()int i,j,n,max,h100,l100;scanf(%d”,&n);for(i=0;i=0;i-)max=0;for(j=i+1;jhj-1&maxlj)max=lj;li=max+1;printf(%d,l0);滑雪问题滑雪问题描述：Michael喜欢滑雪百这并不奇怪，因为滑雪的确很刺

6、激。可是为了获得速度， 滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降 机来载你。Michael想知道载一个区域中最长底滑坡。区域由一个二维数组给出。 数组的每个数字代表点的高度。下面是一个例子 TOC o 1-5 h z 12345161718196152425207142322218131211109一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小。在 上面的例子中，一条可滑行的滑坡为24-17-16-1。当然25-24-23-.-3-2-1更长。 事实上，这是最长的一条。Input输入的第一行表示区域的行数R和列数C(1 = R,C = 100)。下

7、面是R行， 每行有C个整数，代表高度h，0=h=10000。Output输出最长区域的长度。分析1、optxy = Max(optx-1y, optx+1y, optxy-1，optxy+1)2、在该点周围的点中，只要其比该点更低，则该点所能滑的最长距 离等于该点周围中能得最长距离加1，递归地执行这个操作，直至遍历 每个点。然后找也能滑得的最长距离即为所求。3、因为有备忘录，每个点所能滑的最长距离只求一次，算法复杂席为O (n)#include using namespace std;int matrix100100;int cnt100100;int row ,col;int DP(int

8、i, int j)int max = 0;if (cntij-1 0)return cntij-1;if (j-1 = 0)if (matrixij matrixij-1)if (max DP(i, j-1)max = DP(i, j-1);if (j+1 matrixij+1)if (max = 0)if (matrixij matrixi-1j) if (max DP(i-1, j)max = DP(i-1, j);if (i+1 matrixi+1j)if (max rowcol;for (i=0; i=row-1; i+)for (j=0; jmatrixij;cntij = 0;fo

9、r (i=0; i=row-1; i+)for (j=0; j=col-1; j+)DP(i, j);for (i=0; i=row-1; i+)for (j=0; j=col-1; j+)if (cnt00 cntij)cnt00 = cntij;coutcnt00endl;return 0;投资问题设有8 (万元)的投资可分给3个项目，每个项目的利润函数如下表(一)所示:表(一)利润函数表x012345678G1(x)05154080909598100G2(x)0515406070737475G3(x)0426404550515253解题步骤：第1步：设项目1是可用于投资的唯一项目，把x万

10、元投资到项目1，利润为f(x)= G1(x)这就得到表(二)的最后一行的值，投资到项目1的最优数量为d(x)=xx=0,18；第二步：设资金8万元可投资到项目1和项目2。由第1步已知任意数量的资源投资到项目1所产生的最优，所以下到各种和式中的最大值就是目前情况下的最大利润：G2(0)+ (8)=0+100=100G2(2)+ (6)=15+95=110G2(4)+ f1(4)=80+60=140G2(6)+ f1(2)=73+15=88G2(8)+ f1(0)=75+0=75可见将8万元投资于项目1和2G2(1)+ f1(7)=5+98=103 G2(3)+ f1(5)=40+90=130G2

11、(5)+ f1(3)=70+40=110G2+ f1(1)=74+5=79量分别为:，所能获得的最大利润f2(8)及投资到项目2的最优数f2(8)=maxG2(z)+ f1(8-z)=140z=0,18d2(8)=4；第三步：假设以任意x(尹8)万元投资到项目1和2,对每个x值，计算从项目1和2所产生 的最优利润，即：f2(x)=maxG2(z)+ f1(x-z)z=0,1 x;投资到项目2的数量为d2(x)=产生 f2(x)的 z 值。得到所表(二)的结果。第四步：将8万元投资于3个项目G3(0)+ f2(8)=0+140=140G3(2)+ f2(6)=26+96=126G3(4)+ f2(4)=45+80=125G (6)+ f (2)=51+15=66G (8)+ f(0)=53+0=53这就是原问题。则f3(8)应取下述各量的最大值:G3(1)+ f2( 7)=4+120=124G3(3)+ f2(5)=40+90=130G3(5)+ f2(3)=50+40=90G3(7)+ f2(1)=52+5=57因此将8万元以最优方式投资到3个项目时所获得的最大利润及投资到项目3的 分别为：f3(8) =G3(0)+ f2(8)=140d3(8)=0；表