动态规划复习

1、1软件软件701周数周数5678910111213141516周二周二下午下午67节节TTTTTTTTTTP PTTTTTTTTTT考查考查TT周四周四12节节P PP PP PP PP PP PP PP PP PP PP P2计算机计算机05级级-软件方向软件方向周数周数56789101112周二周二12节节TTTTTTTTTTTTP PP P周四周四34节节P PP PP PP PP PP PTTTT3租用游艇问题租用游艇问题 长江游艇俱乐部在长江上设置了长江游艇俱乐部在长江上设置了n 个游艇出租站个游艇出租站1，2，n。游客可在这些游艇出租站租用游艇，并在下游的任何。游客可在这些游艇出租

2、站租用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站一个游艇出租站归还游艇。游艇出租站i 到游艇出租站到游艇出租站j 之之间的租金为间的租金为r(i,j),1=ij=n。试设计一个算法，计算出从。试设计一个算法，计算出从游艇出租站游艇出租站1 到游艇出租站到游艇出租站n 所需的最少租金。所需的最少租金。编程任务：编程任务：对于给定的游艇出租站对于给定的游艇出租站i 到游艇出租站到游艇出租站j 之间的租金为之间的租金为r(i,j),1=ij=n，编程计算从游艇出租站，编程计算从游艇出租站1 到游艇出租站到游艇出租站n所需的最少租金。所需的最少租金。4租用游艇问题租用游艇问题数据输入：数据

3、输入：第第1 行中有行中有1 个正整数个正整数n（n=200），表示有），表示有n个游艇个游艇出租站。接下来的出租站。接下来的n-1 行是行是r(i,j),1=ij=n。结果输出结果输出:程序运行结束时，输出从游艇出租站程序运行结束时，输出从游艇出租站1 到游艇出租站到游艇出租站n所需的最少租金。所需的最少租金。输入示例输入示例35 157输出示例输出示例121 2 351575input:713 15 24 44 29 50 16 18 8 21 53 7 26 4 38 12 1 29 9 4 11 Output:25租用游艇问题租用游艇问题1 2 3 4 5 6 713152444295

4、001234560131524442950116188215327264383121294945116原始数据原始数据6租用游艇问题租用游艇问题012345601315244429501161882153272643831212949451160123456013152221192510161881712200719415300012112400009450000011601234560131522212950101618817532007194383000121124000094500000116012345601315224429501016188215320071943830001212

5、94000094500000116原始数据原始数据运算结束运算结束7租用游艇问题租用游艇问题void dyna() for (int k=2; kn; k+)for (int i=0; in-k; i+) int j=i+k;for (int p=i+1; ptemp) fij = temp;最优值在最优值在f0n-1中中.9完全加括号的矩阵连乘积可递归地定义为：完全加括号的矩阵连乘积可递归地定义为：n 单个矩阵是完全加括号的；单个矩阵是完全加括号的；n 矩阵连乘积矩阵连乘积A是完全加括号的，则是完全加括号的，则A可表示为可表示为2个完全加个完全加括号的矩阵连乘积括号的矩阵连乘积B和和C的乘积

6、并加括号，即的乘积并加括号，即A=(BC) 设有四个矩阵设有四个矩阵A, B, C, D，总共有五中完全加括号的方式，总共有五中完全加括号的方式:(A(BC)D)(A(B(CD)(AB)(CD)(AB)C)D)(A(BC)D)10设有四个矩阵设有四个矩阵A, B, C, D，它们的维数分别是：，它们的维数分别是：A=5010, B=1040, C=4030, D=305矩阵矩阵A和和B可乘的条件是可乘的条件是: 矩阵矩阵A的列数等于矩阵的列数等于矩阵B的行数的行数.设设A是是pq的矩阵的矩阵, B是是qr的矩阵的矩阵, 则乘积是则乘积是pr的矩阵的矩阵;计算量是计算量是pqr.上述上述5种完全

7、加括号方式的计算工作量为种完全加括号方式的计算工作量为:(A(BC)D), (A(B(CD), (AB)(CD), (AB)C)D), (A(BC)D)16000, 10500, 36000, 87500, 34500BC: 104030 = 12000, (BC)D: 10305 = 1500,(A(BC)D): 50105 = 250011穷举法穷举法动态规划动态规划将矩阵连乘积将矩阵连乘积AiAi+1Aj 简记为简记为Ai:j, 这里这里ij;考察计算考察计算Ai:n的最优计算次序。的最优计算次序。设这个计算次序在矩阵设这个计算次序在矩阵Ak和和Ak+1之间将矩阵链断开，之间将矩阵链断开

8、，1kn，则其相应完全加括号方式为，则其相应完全加括号方式为(A1A2Ak)(Ak+1Ak+2An)计算量：计算量：A1:k的计算量加上的计算量加上Ak+1:n的计算量，再的计算量，再加上加上A1:k和和Ak+1:n相乘的计算量相乘的计算量12设计算设计算Ai:j，1ijn，所需要的最少数乘次数，所需要的最少数乘次数mi,j，则，则原问题的最优值为原问题的最优值为m1,n 当当i=j时，时，Ai:j=Ai，因此，因此，mi,i=0，i=1,2,n当当ij 时，时，这里这里Ai的维数是的维数是Pi-1Pi可以递归地定义可以递归地定义mi,j为：为：jkipppjkmkimjim1, 1,jipp

9、pjkmkimjijimjki, 1,min0,1jki 的位置只有的位置只有 种种可能可能kij 13rj void MatrixChain(int *p，int n，int *m，int *s) for (int i = 1; i = n; i+) mii = 0; for (int r = 2; r = n; r+) for (int i = 1; i = n - r+1; i+) int j=i+r-1; mij = mi+1j+ pi-1*pi*pj; sij = i; for (int k = i+1; k j; k+) int t = mik + mk+1j + pi-1*pk*

10、pj; if (t mij) mij = t; sij = k; 14A1A2A3A4A5A630 3535 1515 55 1010 2020 25113752010350437555427125205351000262554 3213000201535250005322min52541531521pppmmpppmmpppmmm15void MatrixChain(int *p，int n，int *m，int *s) for (int i = 1; i = n; i+) mii = 0; for (int r = 2; r = n; r+) for (int i = 1; i = n -

11、 r+1; i+) int j=i+r-1; mij = mi+1j+ pi-1*pi*pj; sij = i; for (int k = i+1; k j; k+) int t = mik + mk+1j + pi-1*pk*pj; if (t 0时时bj=bj-1+aj，否则，否则bj=aj。则计算则计算bj的动态规划递归式的动态规划递归式bj=maxbj-1+aj，aj，1jn。jnjjikkjinjjkknjijikkjijbaanjab111111maxmaxmaxmax1max为，则所求的最大子段和，若记123456ai-211-413-5-2b(初值初值=0)-211720151

12、3sum01111202020203. 动态规划方法求解动态规划方法求解据此，可设计出求最大子段和的动态规划算法如下：据此，可设计出求最大子段和的动态规划算法如下：int MaxSum(int n, int a)int sum=0; /sum是是bj(1jn)的最大值的最大值int b=0;for (int i=1;i0) b+=ai; else b=ai;if (bsum) sum=b;return sum;显然该算法的计算时间为显然该算法的计算时间为O(n)。123456ai-211-413-5-2b(初值初值=0)-2117201513sum0111120202021若给定序列若给定序列

13、X=x1,x2,xm，则另一序列，则另一序列Z=z1,z2,zk，是是X的子序列是指存在一个严格递增下标序列的子序列是指存在一个严格递增下标序列i1,i2,ik使得对于所有使得对于所有j=1,2,k有：有：zj=xij。例如，序列例如，序列Z=B，C，D，B是序列是序列X=A，B，C，B，D，A，B的子序列，相应的递增下标序列为的子序列，相应的递增下标序列为2，3，5，7。给定给定2个序列个序列X和和Y，当另一序列，当另一序列Z既是既是X的子序列又是的子序列又是Y的的子序列时，称子序列时，称Z是序列是序列X和和Y的的公共子序列公共子序列。给定给定2个序列个序列X=x1,x2,xm和和Y=y1,

14、y2,yn，找出，找出X和和Y的最长公共子序列。的最长公共子序列。 222个序列的最长公共子序列包含了这个序列的最长公共子序列包含了这2个序列的个序列的前缀的最长公共子序列前缀的最长公共子序列。最长公共子序列问题具有最长公共子序列问题具有最优子结构性质最优子结构性质。 设序列设序列X=x1,x2,xm和和Y=y1,y2,yn的最长公共子序的最长公共子序列为列为Z=z1,z2,zk ，则，则q 若若xm=yn，则，则zk=xm=yn，且，且zk-1是是xm-1和和yn-1的最长公共的最长公共子序列。子序列。q 若若xmyn且且zkxm，则，则Z是是xm-1和和Y的最长公共子序列。的最长公共子序列

15、。q 若若xmyn且且zkyn，则，则Z是是X和和yn-1的最长公共子序列。的最长公共子序列。23jijiyxjiyxjijijicjicjicjic; 0,; 0,0, 01,1max1 110由最长公共子序列问题的最优子结构性质建立子问题最优由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。值的递归关系。用用cij记录序列和的最长公共子序列的长度。记录序列和的最长公共子序列的长度。 Xi=x1,x2,xi；Yj=y1,y2,yj。当当i=0或或j=0时，空序列是时，空序列是Xi和和Yj的最长公共子序列。的最长公共子序列。故此时故此时Cij=0。其它情况下，由最优子结构性质可建

16、立递归关系如下：其它情况下，由最优子结构性质可建立递归关系如下：24void LCSLength(int m，int n，char *x，char *y，int *c，int *b) int i，j; for (i = 1; i = m; i+) ci0 = 0; for (i = 1; i = n; i+) c0i = 0; for (i = 1; i = m; i+) for (j = 1; j =cij-1) cij=ci-1j; bij=2; else cij=cij-1; bij=3; 由于在所考虑的子问题空间中，总共有由于在所考虑的子问题空间中，总共有(mn)个不同的子问题，个不同

17、的子问题，用动态规划算法自底向上地计算最优值能提高算法的效率。用动态规划算法自底向上地计算最优值能提高算法的效率。01234.n000000 010203040 m 0ij25void LCSLength(int m，int n，char *x，char *y，int *c，int *b) int i，j; for (i = 1; i = m; i+) ci0 = 0; for (i = 1; i = n; i+) c0i = 0; for (i = 1; i = m; i+) for (j = 1; j =cij-1) cij=ci-1j; bij=2; else cij=cij-1; bi

18、j=3; 0123456yiBDCABA0 xi00000001A00001112B01111223C01122224B01122335D01222336A01223347B0122344ij26由数组由数组b构造最长公共子序列构造最长公共子序列void LCS(int i，int j，char *x，int *b) if (i =0 | j=0) return; if (bij= 1) LCS(i-1，j-1，x，b); coutxi; else if (bij= 2) LCS(i-1，j，x，b); else LCS(i，j-1，x，b);0123456yiBDCABA0 xi000000

19、01A00001112B01111223C01122224B01122335D01222336A01223347B0122344ij0123456yiBDCABA0 xi1A 2B 3C 4B 5D 6A 7B ij27n个作业个作业1，2，n要在由要在由2台机器台机器M1和和M2组成的流水线上组成的流水线上完成加工。完成加工。每个作业加工的顺序都是先在每个作业加工的顺序都是先在M1上加工，然后在上加工，然后在M2上加工。上加工。M1和和M2加工加工作业作业i所需的时间分别为所需的时间分别为ai和和bi。流水作业调度问题要求确定这流水作业调度问题要求确定这n个作业的最优加工顺序，使得从个作业的

20、最优加工顺序，使得从第一个作业在机器第一个作业在机器M1上开始加工，到最后一个作业在机器上开始加工，到最后一个作业在机器M2上上加工完成所需的加工完成所需的时间最少时间最少。123456A2571052B384113428流水作业调度问题的流水作业调度问题的Johnson算法算法(1) 令令(2) 将将N1中作业依中作业依ai的非减序排序；的非减序排序； 将将N2中作业依中作业依bi的非增序排序；的非增序排序；(3) N1中作业接中作业接N2中作业构成满足中作业构成满足Johnson法则的最优调度。法则的最优调度。;|,|21iiiibaiNbaiNN1中作业依中作业依ai的非减序排序的非减序

21、排序N2中作业依中作业依bi的非增序排序的非增序排序123456A2571052B384113429int FlowShop(int n, int *a, int *b, int *c) class Jobtype public: int operator= (Jobtype a) const /排序重载函数排序重载函数 return key=a.key; int key; int index; bool job; ; Jobtype *d=new Jobtypen; for(int i=0; ibi?bi:ai; di.job = ai=bi; di.index = i; sort(d,n)

22、;012345A2571052B3841134key2541032jobTTFTFTindex01234530int j=0, k=n-1; for(int i=0; in; i+) if(di.job) cj+ = di.index; else ck- - = di.index; j = ac0; k = j+bc0; for(int i=1; in; i+) j += aci;k = jj,无法装入无法装入背包容量背包容量: j1. 0jwi;2. jwi34C=6123wi234vi125xi1010123456100000062000255530000555jiiiiiwjwjjimv

23、wjimjimjim0), 1(), 1(), 1(max),(nnnwjwjvjnm00),(m23=max(m33,m30+2)=2;m24=max(m34,m31+2)=5;m25=max(m35,m32+2)=5;m26=max(m36,m33+2)=5;m16=max(m26,m24+1)=6;cn35代码分析代码分析#define NUM 100void knapsack(int v , int w , int c, int n, int m NUM) int jMax=min(wn-1,c); for( int j=0; j=jMax; j+) mnj=0; for( int j

24、=wn; j1; i-) jMax=min(wi-1,c); for( int j=0; j=jMax; j+) mij=mi+1j; for(int j=wi; j=w1) m1c=max(m1c, m2c-w1+v1); nnnwjwjvjnm00),(iiiiwjwjjimvwjimjimjim0), 1(), 1(), 1(max),(36代码分析代码分析void traceback( int m NUM, int w , int c, int n, int x ) for(int i=1; i0)? 1:0; C=6123wi234vi125xi1010123456100000062

25、000255530000555ic37最长单调递增子序列最长单调递增子序列(习题习题3-1)设计一个设计一个O(n2)时间的算法时间的算法, 找出由找出由n个数组成的序列的最个数组成的序列的最长单调递增子序列。长单调递增子序列。输入输入第第1个整数个整数n(0n100),表示后面有表示后面有n个数据，全部为整数个数据，全部为整数输出输出输出最长单调递增子序列的长度；输出最长单调递增子序列的长度；样例输入样例输入8 65 158 170 155 239 300 207 389样例输出样例输出638最长单调递增子序列最长单调递增子序列用数组用数组b0:n-1记录以记录以ai (0in) 为结尾元素

26、的最长递增子为结尾元素的最长递增子序列的长度。序列的长度。序列序列a的最长递增子序列的长度为：的最长递增子序列的长度为：max bi显然，显然，bi满足最优子结构性质，可以递归的定义为：满足最优子结构性质，可以递归的定义为：b0 = 1;bi = max bk + 1即即k在在0(i-1)范围内范围内, 若若ak ai, 寻找最大的寻找最大的bk.据此将计算据此将计算bi转化为转化为i个规模更小的子问题。个规模更小的子问题。0in0kiak ai6515817015523930020738912324546ik39最长单调递增子序列最长单调递增子序列int main() int n;scanf

27、(%d, &n);int a100;for (int i=0; in; i+) scanf(%d, &ai);printf(%dn, LISdyna( a, n);样例输入样例输入8 65 158 170 155 239 300 207 38940最长单调递增子序列最长单调递增子序列int main() int n;scanf(%d, &n);int a100;for (int i=0; in; i+) scanf(%d, &ai);printf(%dn, LISdyna(a, n);int LISdyna(int a , int n) int b100=0;i

28、nt i,j;b0 = 1;for (i=1;in; i+) int k = 0;/0i-1之间，之间，b的最大值的最大值for (j=0; ji; j+) if (aj=ai & kbj) k=bj;bi = k+1;int max = 0;for (i=0; imax) max = bi;return max;41编辑距离问题编辑距离问题设设A 和和B 是是2 个字符串。要用最少的字符操作将字符串个字符串。要用最少的字符操作将字符串A 转换为字符串转换为字符串B。这里所说的字符操作包括：。这里所说的字符操作包括：q 删除一个字符；删除一个字符；q 插入一个字符；插入一个字符；q 将

29、一个字符改为另一个字符。将一个字符改为另一个字符。将字符串将字符串A变换为字符串变换为字符串B 所用的最少字符操作数称为字所用的最少字符操作数称为字符串符串A到到B 的的编辑距离编辑距离，记为，记为d(A,B)。试设计一个有效算。试设计一个有效算法，对任给的法，对任给的2 个字符串个字符串A和和B，计算出它们的编辑距离，计算出它们的编辑距离d(A,B)。编程任务：编程任务：对于给定的字符串对于给定的字符串A和字符串和字符串B，编程计算其编辑距离，编程计算其编辑距离d(A,B)。42编辑距离问题编辑距离问题数据输入：数据输入：第一行是字符串第一行是字符串A，第二行是字符串，第二行是字符串B。结果输出结果输出:程序运行结束时，输出编辑距离程序运行结束时，输出编辑距离d(A,B) 。输入文件示例输入文件示例fxpimuxwrs输出文件示例输出文件示例543编辑距离问题编辑距离问题设所给的设所给的2个字符串为个字符串为A1m和和B1n，定义，定义:Di, j=(A1i, B1j)，单字符，单字符a, b之间的距离为：之间的距离为：考察从字符串考察从字符串A1i到字符串到字符串B1j的变换：的变换：q 字符字符Ai改为字符改为字符Bj，需要，需要(Ai, Bj)次操作；次操作；q 删除字符删除字符Ai，需要，需要1次操作；次操作；q 插