动态规划算法作业.pdf

1、1 nlength(t)2 create array x1:l 3 for j1 to l 4 do xjj/t15 for i2 to n6 do for jl to 1 7 do for k1 to j/ti 8 do if xj-k*x+k0 6 do for in to 17 do if cw=cw-ti+1 8 then yiyi+19 ww-ti 10 break 11 return y 时间复杂性分析： 算法 12行时间复杂度为o(1)，23 行时间复杂度为 o(n)，510 行时间复杂度为o(m n)，11 行时间复杂度为o(1)。故算法总的时间复杂度为o(m n)。2.设计一

2、个动态规划算法从n 个数构成的数列中找出最长单调递增子序列。答：（1）问题转化：设x1:n 为 n 个数构成的序列， y1:n 为将 x1:n中的数进行递增排序的结果。那么，原问题可以转化为求x 和 y 的最长公共子序列。设x 中的最长单调递增子序列为xi, xj, , xk, xm，那么在排序后的y 中，该子序列仍以这一顺序存在于y 中，显然该序列为 x 和 y 的公共子序列。假设其不是 x 和 y 的最长公共子序列，设其最长公共子序列为xi, xj, , xp, , xk, xm。由于 y 为递增序列，因此有 xixjxpxkxm。又因为 xi, xj, , xp, , xk, xm是 x

3、 的子序列，那么在x 序列中，有一个更长的单调递增子序列xi, xj, , xp, , xk, xm。产生了矛盾，因此x 的最长单调递增子序列即为x 和y 的最长公共子序列。（2）优化子结构x 和 y 的 lcs=(z1,z2, zk)的优化解结构为?= ?-1?-1+ ? ?= ?= ?-1? ? ?，z?= ?-1 ? ?，z?（3）递推方程ci,j=xi和 yj的 lcs 的长度? i, j = 0 ? ?= 0 或 j = 0? i, j = ci - 1,j - 1 + 1 ? ?,? 0 且?i= ?j? i, j = max (ci, j - 1,ci - 1,j) ? ?,?

4、0 且?i= ?j（4）算法伪代码input:数列 x1:n output：x 的最长单调递增子序列lis(x) 1 nlength(x)2 create array y1:n ,cn,n and bn,n 3 ysort(x)4 for i1 to n 5 do ci,00，c0,j0 6 for i1 to n7 do for j1 to n 8 if xi=yj 9 then ci,jci-1,j-1 +1;bi,j“”10 else if ci-1,j ci,j-1 11 then ci,jc i-1,j; bi,j“”12 else ci,jci,j-1; bi,j“”13 retu

5、rn b and c print-lis(b,x,i,j) 1 if i0 or j02 then return 3 if bi,j= “ ”4 then print-lis(b,x,i-1,j-1);print xi 5 else if bi,j= “ ”6 then print-lis(b,x,i-1,j); 7 else print-lis(b,x,i,j-1); 时间复杂度分析：计算代价算法 lis(x) 中， 12 行时间复杂度为 o(1)， 3 行为排序算法，时间复杂度最低为o(nlogn)，45 行时间复杂度为o(n)，612行时间复杂度为 o(n2)，13 行时间复杂度为o(1

6、)；构造算法 print-lis(b,x,i,j) 中，时间复杂度为o(2n)。故算法总的时间复杂度为o(n2)。3.给定一个 n n 的矩阵 a，矩阵中的元素只取0 或者 1。设计一个动态规划算法，求解得到a 中元素全是 1 的子方阵使其阶数达到最大值。答：（1）优化子结构：设n 阶矩阵表示为a1:n,1:n，bi,j 为 a 中前 i行，前 j 列中 1 的个数。则1aijif10aijif0b-bbb1-j1,-i1-ji,j1,-iji,如果 bi,j-bi-k,j- bi,j-k +bi-k,j-k=k2，那么在该位置存在一个k 阶矩阵。（2）递推方程：设 ci,j 表示 a 中前

7、i 行前 j 列中元素全为1 的子方阵的最大阶数。则递推方程为：ci,j = max ci - 1,j,ci, j - 1,maxkk max(ci - 1,j,ci, j - 1)|bi,j - bi - k, j - bi,j - k + bi - k j - k = k k（3）算法伪代码只要知道了cn,n的值，就知道了最优解的阶数，为了知道这个最优解的具体信息，我们还需一个结构s，si,j是 ci,j对应的方阵的右下角元素在 a 中对应的位置。因此， sn,n就是最优解方阵右下角元素的位置， cn,n是最优解的阶数。get-max-matrix(a,n) 1 create arrays

8、 b0:n0:n,c0:n0:n,s1:n1:n 2 for i0 to n 3 do bi0 0; b0i 0;ci0 0; c0i 0; 4 for i0 to n 5 do for j0 to n 6 do if aij=1 7 then bij 1 8 else bij 0 9 bij bij+bi-1j+bij-1+bi-1j-1 10if ci-1jcij-1 11 then cij ci-1j 12 sij ci-1j 13 else cij cij-1 14 sij cij-1 15 for kcij+1 to i16 do if i-k+11 or j-k+10 17 the

9、n break 18 if bij-bi-k+1j-bij-k+bi-kj-k=kk 19 then cij k 20 sij (i,j) 21 else break 22 return s and c 算法结束后， snn中有序实数对 (i,j)为 a 中最大全 1 矩阵右下角元素的坐标。该矩阵为ai-cnn:ij-cnn:j。时间复杂度分析： 算法第 1 行时间复杂度为o(1)，23 行时间复杂度为 o(n)，422 行时间复杂度为o(n3)，23 行时间复杂度为o(1)。故算法总的时间复杂度为o(n3)。4.集合划分问题描述如下：输入：正整数集合s=a1,a2,a3, an; 输出：是否

10、存在a ? s使得?= ? ?-? ?。试设计一个动态规划算法，求解集合划分问题。答：（1）问题转化：若集合划分a 使得 ?= ? ?-? ?，则有?= ?=12? ? ?-? ?。那么，该问题可转化为一个0-1 背包问题。 对于输入的正整数集合s=a1,a2,a3, an。 设 x=(x1, x2, , xn), xi 0, 1, 满 足 ?=112? ?,且 ?=1最 大 。 若此 时?=1=12? ?, 则存在这样的集合划分a，输出划分结果；否则不存在这样的集合a。（2）优化子结构： 如果(y1, y2, yn)是 0-1 背包问题的有化解， 则(y2, y3, yn)是如下子问题的优化

11、解：?=212? ?- ?1?1；xi0, 1 ，2in。（3）递推方程：设背包容量为j，m(i,j) 表示背包容量为j，可选物品为 ai,ai+1, an时，问题的最优解的代价。因此递归方程为：m(i,j) = m(i + 1, j) 0j aim(i, j) = max(m(i + 1,j),m(i + 1,j - ai) + ai) jaim(n,j) = 0 0j anm(n,j) = an jan（4）算法伪代码：input：正整数集合 s=a1,a2,a3, an output：若存在 a ? s使得?= ? ?-? ?, 则输出 x; 否则输出不存在。set-partition(

12、s) 1 nlength(s),sum0 2 for i1 to n 3 do sumsum+si 4 half-sumsum/2 5 create array m1:n,0: half-sum and x1:n 6 for j0 to min(sn-1, half-sum) 7 do mn,j0 8 for jsn to half-sum 9 do mn,jsn 10 for in-1 to 2 11 do for j0 to min(si-1, half-sum) 12 do mi,j mi+1,j 13 for jsi to half-sum 14 do mi,j maxmi+1,j,m

13、i+1,j-si+si 15 if half-sum s1 16 then m1, half-sum=m2, half-sum 17 else m1, half-sum= maxm2, half-sum,m2, half-sum -s1+s1 18 if m1, sum/2 0 （3）算法伪代码input：网格长 m 和宽 n，代价矩阵 amn和 bmnoutput：从(0,0)点到(m,n)点代价最小的路径l0:m+n-1 min-cost-itinerary(m,n,a,b) 1 create arrays l0:m+n2 and costmn 2 cost0,003 for i1 to

14、m 4 do costi0costi-10+bi-10 5 for j1 to n6 do cost0j cost0j-1+a0j-1 7 for j1 to m 8 do for i1 to n9 do if costij-1+aij-10 14 do lk0 x, lk1 y 15 if y=0|(x0&costx-1y+bx-1ycostxy-1+axy) 16 then x x-1 17 else y y-1 18 ss -1 19 l00 0, l01 0 20 return l 时间复杂度分析： 12 行时间复杂度为o(1)，34 行时间复杂度为o(m)，56 行时间复杂度

15、为 o(n)，711 行时间复杂度为 o(m n)，12行时间复杂度为o(1)，1218 行时间复杂度为o(m+n)，1920 行时间复杂度为 o(1)。故总的时间复杂度为o(m n)。p.s. 题出的是不是有点问题6.给定一个整数序列a1, , an。相邻两个整数可以合并，合并两个整数的代价是这两个整数之和。 通过不断合并最终可以将整个序列合并成一个整数，整个过程的总代价是每次合并操作代价之和。试设计一个动态规划算法给出a1, , an的一个合并方案使得该方案的总代价最大。你的答案应包括：（1）用简明的语言表述这个问题的优化子结构；（2）根据优化子结构写出代价方程；（3）根据代价方程写出动态

16、规划算法（伪代码）并分析算法的时间复杂性；答：定义记号如下， aij=aiai+1aj。sumi,j= ai+ai+1+aj（1）优化子结构：若计算aij的优化顺序在k 处断开整数数列，即a1n=a1k+ak+1n。则在 a1n的优化顺序中，对应于子问题a1k的解必须是 a1k的优化解，也对应于子问题ak+1n的解必须是 ak+1n的优化解。（2）优化结构的代价方程：设mi,j 为计算整数序列aij所需的代价的最小值，对于整个问题，计算a1n的最小代价就是m1,n。代价方程为mi, j = 0 ?= ?min? ? ?, ? + ? ? + 1,? + ?,? ? ?。（3）算法伪代码：input:整数序列 a output：序列 a 的一个最优加全部括号形式integer-sequence-order(a) 1 nle