第3 章 动态规划 3.1 内容提要 1.基本概念 动态规划(dynamicprogramming)是一种求解多阶段决策(优化)问题的算法设计技 术,其主要思想是:将原问题归约为规模较小、结构相同的子问题,建立原问题与子问题优 化函数间的依赖关系.从规模最小的子问题开始,利用上述依赖关系求解规模更大的子问 题,直到得到原始问题的解为止. 动态规划算法的适用条件 适用于求解多阶段决策(优化)问题,该问题的解可以表示 为一个决策序列,且满足优化原则(或最优子结构性质),即一个最优决策序列的任何子序列 本身一定是相对于子序列的初始和结束状态的最优决策序列. 对于规模大的实例,对存储空间的需求是该算法的瓶颈. 主要设计步骤 (1)写出所要求解的组合优化问题的目标函数和约束条件. (2)确定子问题的结构与边界,将问题求解转变成多步判断的过程. (3)定义优化函数,以该函数的极大值或者极小值作为判断的依据,确定是否满足优化原则. (4)列出有关优化函数的递推关系和边界条件. (5)根据问题的解的不同情况,考虑是否需要设立标记函数. (6)从初值开始,自底向上计算每个子问题的优化函数值(有的需要同时计算标记函 数),并以备忘录的方式存储所有的中间结果. (7)如果有标记函数,则根据标记函数逐步追踪问题的解. 2.时间复杂度的分析方法 时间复杂度取决于备忘录(包括优化函数及标记函数)中每个项的计算工作量,以及用 标记函数追踪解的工作量.大多数情况下,追踪解的工作量不超过优化函数计算的工作量, 因此可以根据递推关系确定备忘录中每个项的计算工作量,然后对这些工作量求和. 3.典型的动态规划算法 矩阵链相乘 MatrixChain(P ,n)给定矩阵链A1..n=A1A2…An ,其行和列数为向量 P=,其中P0 是A1 的行数,Pi(i=1,2,…,n-1)是Ai 的列数和Ai+1的 行数,Pn 是An 的列数.通过加括号确定具有最少乘法次数的运算顺序. 动态规划 第 j Ai+1…Aj 的计算, i, j 数,则 设子问题Ai. 是矩阵链Ai令 m [j]是计算Ai. 的最少的乘法次 3 章 m[j]0 i= j 1≤ i ≤ j ≤ n i, = mi{m[k]+m[j]+Pi1PkPj}i< j , n i,k+1, 33 i≤kFk (-wk )+vk ,1< k ≤n,y=2,…, y)-y)Fk1( y 1,bk Fky)≤Fk (-wk )+vk - y 1 y ≥w1 i1(y) = 0 y ,yj >, j] Yj =0,xi =yj max{C[i,j-1],C[i-1,j]} 如果i,j >0,xi ≠yj i=1,2,…,m , j=1,2,…,n C[0,j]=C[i,0]=0 对一切1≤i ≤m ,1≤j ≤n 令B[i,j]为标记函数.在归约为子问题时,如果C [i,j]归约为C [i-1,j-1],则 B[i,j]=“↖”;若归约为C[i,j-1],则B[i,j]=“←”;若归约为C[i-1,j],则B[i,j]= “↑”.算法最坏情况下的时间复杂度为O(mn). 图像压缩Compress(P ,n) 给定图像的灰度值序列P =,其中pi 为第i 个像素的灰度值,采用变位压缩存储格式,如何对P 进行分段,以使得存储P 占用的 二进制位数达到最少? 设S[i]表示输入为时按最优分段存储所使用的二进制位数,则 S[i]=1≤j≤mmiinn{i,256}{S[i-j]+j*b[i-j+1,i]+11} i=2,3,…,n S[1]=b[1,1]+11 其中b[i-j+1,i]表示最后一段中的最大灰度值在存储时所占用的二进 制位数.11是存储该分段信息的额外开销.用标记函数l[i]记录进行最优划分时最后一段 的像素个数,可用于追踪达到最小存储位数时的分段位置.该算法最坏情况下的时间复杂 度为O(n). 最大子段和MaxSum(A ,n) 给定n 个整数的序列A =,求 max0,1≤mi≤ajx≤nΣj k=i { ak} 定义C[i]是输入A[1.. i]中必须包含元素A[i]的最大子段和,最优解为OPT(A),则 C[i]=max{C[i-1]+A[i],A[i]} i=2,…,n C[1]=A[1] OPT(A)=1m≤ia≤xn{C[i]} 该算法的时间复杂度是O(n). 最优二分检索树 设S =是数据集,称(-∞,x1),(x1,x2),…, (xn-1,xn),(xn ,+ ∞)为第0,1,2,…,n 个空隙.与S 相关的存取概率分布是P = ,其中x 处在xi 的概率是bi(i=1,2,…,n),处在 第j 个空隙的概率是aj(j=0,1,…,n).求一棵关于S 的二分检索树,使得平均比较次数为 t=Σn i=1 bi(1+d(xi))+ Σn j=0 ajd(Lj) 达到最小,其中d(xi)表示树中数据结点xi 的深度,d(Lj)表示树中空隙结点Lj 的深度. 令S [i,j]=表示S 以i 和j 作为边界的子数据集,P [i,j]= 是子数据集S[i,j]所对应的存取概率分布,P [i,j]与 S[i,j]一起构成以i 和j 作为边界的子问题.m [i,j]是针对这个子问题的最优二分检索树 的平均比较次数,则 m [i,j]= min i≤k≤j{m [i,k -1]+m [k +1,j]+w [i,j]} 1≤i ≤j ≤n m [i,i-1]=0 i=1,2,…,n 动态规划 第 其中 3 jj 章 i,b p=-1 q= i i,中所有元素( w[j] = Σap + Σq 是P[j] 包括数据元素与空隙)(i) 的概率之和.算法最坏情况下的时间复杂度 是O( . 35 n3) 3.习题 2 对于本章与算法设计有关的习题,解题要求如下:必须对优化函数和标记函数的含义 给出说明,列出子问题计算中所使用关于优化函数及标记函数的递推关系和初值.根据题 目要求给出迭代实现的伪码,并估计算法的复杂度.如果题目给出具体的输入实例,应该根 据给定实例进行计算,并给出相关的备忘录表和最后的解 . 3.用动态规划算法求解下面的组合优化问题, 1 max g1(x1)+g2(x2)+g3(x3) s.. x22+x2 t1+x23≤10 x1,x2,x3 为非负整数 其中,函数g1(g2(g3(x)的值在表3. x),x),1中给出 . 表3.函数值 1 x g1(x) g2(x) g3(x) x g1(x) g2(x) g3(x) 0 2 5 8 2 7 16 17 1 4 10 12 3 11 20 22 3.2 设A=是 n 个不等的整数构成的序列, A 的一个单调递增子序 列是序列,使得i1的长度是含有的整数个数k.例如,A=<1,5,3,8,10,6,4,9>,它的长为4的 递增子序列(k) 是:<1,5,8,10>,<1,5,8,9>,….设计一个算法求 A 的一个最长的单调递 增子序列,分析算法的时间复杂度.设算法的输入实例是A=<2,8,4,-4,5,9,11>,给出 算法的计算过程和最后的解 . 3.有 n 个底面为长方形的货柜需要租用库房存放.如果每个货柜都必须放在地面 3 上,且所有货柜的底面宽度都等于库房的宽度,那么第 i 个货柜占用库房面积大小只需要用 n 它的底面长度li 来表示,1,2,…,设库房总长度是Dll. i=n. i ≤ D 且Σi > D 设第 = i 号货柜的仓储收益是vi,若要求库房出租的收益达到最大,问如何选择放(i) 入(1) 库房的货柜? 若l1,ln ,设计一个算法求解这个问题,给出算法的伪码描述,并估计 l2,…, D 都是正整数 , 算法最坏情况下的时间复杂度 . t2,…, 从0时刻开始安排对这些任务的加工.规定只要有待加工的任务,任何机器就不得闲置.如 果直到时刻 T 所有任务都完成了,总的加工时间就等于T.设计一个算法找到使得总加工 3.4 设有 n 项任务,加工时间分别表示为正整数t1,tn.现有2台同样的机器, 36 算法设计与分析习题解答与学习指导(第3版) 时间 T 达到最小的调度方案.设给定实例如下 : t1=1,t2=5,t3=2,t4=10,t5= 3 试给出一个加工时间最少的调度方案.给出计算过程和问题的解 . 3.5 设有 n 种不同面值的硬币,第 i 种硬币的币值是vk (其中v1=1), 重量是wi, i= 1,2,…,n,且现在购买某些总价值为 y 的商品,需要用这些硬币付款,如果每种钱币使用的 个数不限,那么如何选择付款的方法使得付出钱币的总重量最轻? 设计一个求解该问题的 算法,给出算法的伪码描述,并分析算法的时间复杂度.假设问题的输入实例是: v1=1, v2=4, v3=6, v4=8 w1=1,w2=2,w3=4,w4=6 y=12 给出算法在该实例上计算的备忘录表和标记函数表,并说明付线的方法 . 3.x2,…,xn 如果每种币值的钱币至多使用1 6 n 种币值x1,和总钱数 M 都是正整数 . 次,问对于 M 是否可以有一种找零钱的方法? 设计一个算法求解上述问题.说明算法的设 计思想,分析算法最坏情况下的时间复杂度 . 3.在一条直线的公路两旁有 n 个位置x1,x2,…,xn 可以开商店,在位置xi 开商店 7 i1,2,… , 何选择开设商店的位置使得总收益达到最大 ? 的预期收益是pi,=n.如果任何两个商店之间的距离必须至少为 d 千米,那么如 (1)用组合最优化方法对该问题建模,写出目标函数与约束条件 . (2)设计一个算法求解该问题,说明算法设计思想,分析算法最坏情况下的时间复 杂度 . n 设A={a2,…,}是正整数的集合,且Σai= N ,设计一个算法判断是否能 3.a1,n 8 a =1 够把 A 划分成两个子集A1 和A2,使得A1 中的数之和(i) 与A2 中的数之和相等.说明算法的 设计思想,估计算法最坏情况下的时间复杂度 . 3.9 有 n 项作业的集合J={2,…,每项作业 i 有加工时间t(t( t(2)≤…≤t(i), 1,n}, 其中Z+ i)∈Z+,1)≤ n), 效益值v(任务的结束时间 D ∈Z+, 表示正整数集合.一个可 行调度是对 J 的子集 A 中任务的一个安排,对于i∈A,i) 且满足下述条件: f(i)≤f(j)+t( f(是开始时间, j ∈Ai)+t(j) 或者i), j ≠i,i, f(j)≤f( k)≤ D Σt( k∈ A 设机器从0时刻开动,只要有作业就不闲置,求具有最大总效益的调度.给出算法的伪码, 分析算法的时间复杂度 . 3.10 把0-1背包问题加以推广.设有 n 种物品,第 i 种物品的价值是vi,重量是wi, 体积是ci,且装入背包的重量限制是 W ,体积是V.问如何选择装入背包的物品使得其总重 不超过 W ,总体积不超过 V 且价值达到最大? 设计一个动态规划算法求解这个问题,说明 算法的时间复杂度 . 有 n 个分别排好序的整数数组A0,A1,…,其中Ai 含有xi 个整数, 3.11 An-1, i=0, 1,…,1. 现在要将这些数组合并成一个排好序的 n-已知这些数组顺序存放在一个圆环上, 大数组,且每次只能把两个在圆环上处于相邻位置的数组合并.问如何选择这n-1次合并 动态规划 第3章 3 7 的次序以使得合并时在最坏情况下总的比较次数达到最少? 设计一个动态规划算法求解这 个问题,说明算法的时间复杂度. 3.12 设A 是顶点为1,2,…,n 的凸多边形,可以用不在内部相交的n-3条对角线将 A 划分成三角形,图3.1就是五边形的所有的划分方案.假设凸n 边形的边及对角线的长度 dij都是给定的正整数,1≤i是顶点集为V ={x1,x2,…,xn },边集为E 的有向图. n×n 的0-1矩阵M =(rij)是D 的矩阵表示.考虑n+1个矩阵构成的序列M0,M1,…, Mn ,将矩阵Mk 的i 行j 列的元素记作Mk[i,j].对于k=0,1,…,n,Mk[i,j]=1当且仅当 在图中存在一条从xi 到xj 的路径,并且这条路径除端点外中间只经过{x1,x2,…,xk }中 的顶点.不难看出,M0 就是M ,而在Mn 中如果Mn[i,j]=1,则说明D 中xi 与xj 是连通 的.Warshall算法从M0 开始,顺序计算M1,M2,…,直到Mn 为止.利用动态规划的迭代实 现方法来实现Warshall算法,给出算法的伪码表示,并分析算法的时间复杂度.假设某有向 网络的结点是a,b,c,d,已知网络的矩阵表示是: M = 0 1 1 0 0 0 1 0 0 0 0 1 0 0 1 0 é . êêêêê ù . úúúúú 给出算法在这个实例的计算过程和结果. 3.14 考虑3.3.7节中提到的带权编辑距离问题.设S1[1..n]和S2[1..m ]表示两个序 列,假设插入和删除操作的权是d,替换操作的权是r.令C [i,j]表示序列S1[1..i]和 S2[1..j]的最小权编辑距离,设计一个算法求解该问题,给出关于C[i,j]的递推关系,并分 析算法的时间复杂度. 3.15 某机器每天接受大量加工任务,第i 天需要加工的任务数是xi.随着机器连续运 行时间的增加,处理能力越来越低,需要花1天时间对机器进行检修,以提高处理能力.检 修当天必须停工,重启后的第i 天能够加工的任务数是si,且满足 s1 >s2 > … >sn >0 我们的问题是:给定x1,x2,…,xn ,s1,s2,…,sn ,如何安排机器的检修时间,以使得在n 天 内加工的任务数达到最大? 设计一个算法求解该问题. 3.16 设P 是一台Internet上的Web服务器.T ={1,2,…,n}是n 个下载请求的集 合,.i∈T ,ai∈Z+ 表示下载请求i 所申请的带宽.已知服务器的最大带宽是正整数K .我 们的目标是使带宽得到最大限度的利用,即确定T 的一个子集S,使得Σi∈S ai ≤K ,且K - 算法设计与分析习题解答与学习指导(第3 版) 3 8 Σi∈S ai 的值达到最小.设计一个算法求解服务器下载问题,用文字说明算法的主要设计思想 和步骤,并给出最坏情况下的时间复杂度. 3.17 有正实数构成的数字三角形排列形式如图3.2所示.第一行的数为a11;第二行 图3.2 数字三角形 的数从左到右依次为a21,a22;以此类推,第n 行的数为an1,an2,…, ann .从a11开始,每一行的数aij 只有两条边可以分别通向下一行的 两个数a(i+1)j和a(i+1)(j+1).请设计一个算法,计算出从a11通到an1, an2,…,ann 中某个数的一条路径,并且使得该路径上的数之和达到 最小. 3.18 设集合A ={a,b,c},A 中元素的运算满足aa=ab= bb=b,ac=bc=ca=a,ba=cb=cc=c.给定A 中n 个字符组成的串x1x2…xn ,设计一个 算法,检查是否存在一种运算顺序使得这个串的运算结果等于a.如果存在,则回答“1”,否 则,回答“0”.例如,串x=bbbba,因为存在下述运算顺序,使得 (b(bb))(ba)=(bb)(ba)=b(ba)=bc=a 因此回答“1”.而对串bca,由于(bc)a=aa=b,b(ca)=ba=c,因此回答“0”.说明算法的设 计思想,并给出最坏情况下的时间复杂度. 3.3 习题解答与分析 3.1 设Fk(y)表示对x1,x2,…,xk 赋值,且x21+x22+…+x2k ≤y 时所得到的目标函 数的最大值,递推关系和初值是: Fk(y)= max 0≤xk ≤. y.{Fk-1(y -x2k)+gk(xk)} F1(y)=g1(. y . ) 针对给定实例的计算过程如下: k=1: F1(0)=2 x1=0 F1(1)=F1(2)=F1(3)=g1(1)=4 x1=1 F1(4)=F1(5)=F1(6)=F1(7)=F1(8)=g1(2)=7 x1=2 F1(9)=F1(10)=g1(3)=11 x1=3 k=2: F2(0)=max{F1(0)+g2(0)}=7 x2=0 F2(1)=max{F1(1)+g2(0),F1(0)+g2(1)}=12 x2=1 F2(2)=max{F1(2)+g2(0),F1(1)+g2(1)}=14 x2=1 F2(3)=max{F1(3)+g2(0),F1(2)+g2(1)}=14 x2=1 F2(4)=max{F1(4)+g2(0),F1(3)+g2(1),F1(0)+g2(2)}=18 x2=2 F2(5)=max{F1(5)+g2(0),F1(4)+g2(1),F1(1)+g2(2)}=20 x2=2 F2(6)=max{F1(6)+g2(0),F1(5)+g2(1),F1(2)+g2(2)}=20 x2=2 F2(7)=max{F1(7)+g2(0),F1(6)+g2(1),F1(3)+g2(2)}=20 x2=2 动态规划 F2(8)=max{F1(8)+g2(0),F1(7)+g2(1),F1(4)+g2(2)}=23 x2=2 F2(9)=max{F1(9)+g2(0),F1(8)+g2(1),F1(5)+g2(2),F1(0)+g2(3)}=23 x2=2 F2(10)=max{F1(10)+g2(0),F1(9)+g2(1),F1(6)+g2(2),F1(1)+g2(3)}=24x2=3 k=3: F3(0)=max{F2(0)+g3(0)}=15 x3=0 F3(1)=max{F2(1)+g3(0),F2(0)+g3(1)}=20 x3=0 F3(2)=max{F2(2)+g3(0),F2(1)+g3(1)}=24 x3=1 F3(3)=max{F2(3)+g3(0),F2(2)+g3(1)}=26 x3=1 F3(4)=max{F2(4)+g3(0),F2(3)+g3(1),F2(0)+g3(2)}=26 x3=1 F3(5)=max{F2(5)+g3(0),F2(4)+g3(1),F2(1)+g3(2)}=30 x3=1 F3(6)=max{F2(6)+g3(0),F2(5)+g3(1),F2(2)+g3(2)}=32 x3=1 F3(7)=max{F2(7)+g3(0),F2(6)+g3(1),F2(3)+g3(2)}=32 x3=1 F3(8)=max{F2(8)+g3(0),F2(7)+g3(1),F2(4)+g3(2)}=35 x3=2 F3(9)=max{F2(9)+g3(0),F2(8)+g3(1),F2(5)+g3(2),F2(0)+g3(3)}=37 x3=2 F3(10)=max{F2(10)+g3(0),F2(9)+g3(1),F2(6)+g3(2),F2(1)+g3(3)}=37x3=2 关于中间结果的备忘录如表3. 2所示 . 表3.备忘录 2 y k= 1 k= 2 k= 3 F1(y) x1 F2(y) x2 F3(y) x3 0 2 0 7 0 15 0 1 4 1 12 1 20 0 2 4 1 14 1 24 1 3 4 1 14 1 26 1 4 7 2 18 2 26 1 5 7 2 20 2 30 1 6 7 2 20 2 32 1 7 7 2 20 2 32 1 8 7 2 23 2 35 2 9 11 3 23 2 37 2 10 11 3 24 3 37 2 从而得到,F3(10)=37,此刻x31= + 2x, 2 于是 再查F2(6)=20,此刻x2=2,于是 x22≤10-22=6 x22 1≤6-2=2 再查F1(2)4得x1=问题的解是:在x1=1,2,2时,得到g1(x1)x2) =1.x2=x3=+g2(+ g3(x3)的最大值37. 3.=1,n, 2 使用动态规划设计技术.对于i2,…,考虑以xi 作为最后项的最长递增子 第 章 39 40 算法设计与分析习题解答与学习指导(第3版) 序列的长度C[如果在xi 项前面存在xj xi), i >1 C[1]=1 在计算C[时, i] i] 如果不存在这样的j, i]= i] 用k[记录C[取得最大值时的 j 的值; 令k[ 0.这个记录用于追踪解.所求的最长递增子序列的长度是 : C=max{i]|i=2,… , C[1,n} 对每个i,需要检索比 i 小的所有的j, n) i 的取值有 n 种,于是算法时间复杂 度是 W (n)O( 需要O(时间 , =n2) . 对于给定的实例A=<2,8,4,-4,5,9,11>,具体的计算过程如下 : C[ = 1 1] C[2] = max{C[ = 2 k[2] 1]+1} = 1 C[ = mx{1]+1} = 2 3] = 1 3]aC[k[ C[4] = 1 k[ = 0 4] C[5] = aC[C[C[ = 3 5] = 3 mx{1]+1,3]+1,4]+1}k[ C[6] = aC[C[C[C[C[ = 4 6] mx{1]+1,2]+1,3]+1,4]+1,5]+1}k[ = 5 C[ = mx{1]+1,2]+1,3]+1,4]+1,5]+1,6]+1} = 5 7] = 6 7]aC[C[C[C[C[C[k[ 在C[1],C[2],…,C[7]中,C[7]=5是最大值,这意味着 A 的第7项x7=11是最长 递增子序列的最后项,长度是5.子序列的构造从后向前进行,开始是11,追踪过程是: k[7]=6.x6=9,k[6]=5.x5=5,k[5]=3.x3=4,k[3]=1.x1=2 于是得到解是<2,5,11>,长度是5.本题可以有多个解. 4,9, 3.类似于01背包问题,库房的长度相当于背包的重量限制,每个货柜的收益相当 3 于物品的价值.于是问题是 : n maxΣvixi i=1 Σ(n) lixi ≤D,xi=0,1 i=1 令C[k,y]是只允许装前 k 个货柜,库房长度为 y 时的最大收益,那么有 C[y]= C[ x{C[ y] y],C[ k , k >1 k,mak-1k, -1,yly C[k-1,y] 8. thenC[k,y]←C[k-1,y-L[k]]+V[k] 9. i[k,y]←k 算法在第1行时间为O(D ),第3行和第4行的循环进行O(nD )次,循环内部是常数时 间的操作,于是算法最坏情况下的时间复杂度是O(nD ). 3.4 设任务集J={1,2,…,n},机器为M1 和M2.一个调度是函数f:J→{1,2},如 果f(i)=1,那么任务i 将分配到M1 上;如果f(i)=2,则分配在M2 上.因为任务之间的 安排没有偏序约束,所以只要f 给定,即安排在M1 和M2 上的任务确定,无论M1 和M2 上 的任务怎样排序,每台机器的加工时间都是不变的.两台机器的加工时间分别是: D1(f)= Σ f(i)=1 ti, D2(f)= Σ f(i)=2 ti 调度f 的总加工时间是: D (f)=max{D1,D2} 问题的解是求一个使得D (f)达到最小值的调度f. 命题3.1 令T = 12 Σn i=1 ti ,对于给定输入,一定存在一个最优解f* ,使得D1(f* )≤ T 且D1(f* )达到最大. 证 假设一个最优解f 满足D1(f)>D2(f).交换M1 和M2 的任务,得到解f* ,那 么f* 的总加工时间与f 的总加工时间相等,因此f* 也是最优解且D1(f* )≤D2(f* ). 由于 D1(f* )+D2(f* )=Σn i=1 ti 且D1(f* )≤D2(f* ),于是D1(f* )≤12Σn i=1 ti.由于所有任务的加工时间ti 都是正整数, 因此D1(f* )≤T . f* 的总加工时间为D (f* )=D2(f* ).作为最优调度,D2(f* )一定达到最小,而 D1(f* )+D2(f* )对所有的调度都是一样的,当D2(f* )达到最小时,D1(f* )必然达到 最大. 根据命题3.1,可以设计一个动态规划算法找一个解f* ,使得D1(f* )≤T 且D1(f* ) 达到最大.令xi=1当且仅当f(i)=1,原问题变成如下组合优化问题: maxΣn i=1 xiti xi =0,1, i=1,2,…,n Σn i=1 tixi ≤T , T =12 Σn i=1 ti 这是一个0-1背包问题,令F[k,y]表示考虑前k 个任务,在M1 的加工时间不超过y 的情 算法设计与分析习题解答与学习指导(第3 版) 4 2 况下其加工时间Σk i=1 tixi 的最大值.那么有如下公式: F[k,y]=max{F[k -1,y],F[k -1,y -tk]+tk}, k >1, T ≥y >0 F[1,y]= t1 如果y ≥t1 0 否则 F[k,0]=0 F[k,y]=-∞ 如果y <0 在F[k,y]计算时,设立标记函数i[k,y] i[k,y]= i[k -1,y] 如果F[k -1,y -tk]+tk 1,T ≥y >0 i[1,y]= 1 如果y ≥t1 0 否则 最坏情况下的时间复杂度为O(nT),其中T =12 Σn i=1 ti . 具体实例的计算过程如下: T =12 (1+5+2+10+3)=.10.5.=10 备忘录和标记函数分別如表3.3和表3.4所示. 表3.3 F[k,y] k y 1 2 3 4 5 6 7 8 9 10 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 5 6 6 6 6 6 3 1 2 3 3 5 6 7 8 8 8 4 1 2 3 3 5 6 7 8 8 10 5 1 2 3 3 5 6 7 8 9 10 表3.4 i[k,y] k y 1 2 3 4 5 6 7 8 9 10 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 2 2 2 2 2 2 3 1 3 3 3 2 2 3 3 3 3 4 1 3 3 3 2 2 3 3 3 4 5 1 3 3 3 5 5 3 5 5 5 由F[5,10]=10可知,M1 的加工时间D1(f)=10,于是f 的总加工时间是: 动态规划 D2(f)=21-D1(f)=21-10=11 由i[5,10]=5可知x5=1,接着查 i[4,10-t5]=i[4,7]=3 可知x3=1,接着查 i[2,7-t3]=i[2,5]=2 可知x2=1,接着查 追踪完成,于是调度是: i[1,5-t2]=i[1,0]=0 f(2)=f(3)=f(5)=1,f(1)=f(4)=2,D2=11 如果i[y] 可能得到另外一个解: k,的定义不同 , f(4)=1,f(1)=f(2)=f(3)=f(5)=2,D2=11 3.in. 5 设xi 表示第 i 种硬币使用的个数,=1,2,…,该问题的描述为 n minΣwixi i=1 Σ(n) vixi = y xi 为非负整数 i=1 令Fk (x)表示只允许使用前 k 种钱,总付款为 x 时所使用零钱的最轻重量,则 Fk (x)=min{Fk-1(x),Fk (x-vk )+wk }, k >1,0< x ≤ y x F1(x)=w1 =w1x v1 Fk (0)=0 Fk (x)= + ∞, x <0 设立标记函数tk (记录Fk (取得最小值时最大币值的标号是否为k. y) y) tk (x)= k Fk (x-vk )+wk ≤Fk-1(x), k >1,0< x ≤ytk-1(x) 否则 t1(x)=1,0< x ≤ y tk (0)=0,k=1,n 2,…, 算法的伪码如下: Coin n],1.y w, y 是付款数 输入:w[1. v[n],// v 分别为硬币的重量和币值数组 , i,t[=j=2,… , 输出:F[j],i,j],i1,2,…,n,1, y 1.forj←1toy do j]1] 2. F[1,←j*w[ 3. t[1, j]← 1 4.fori←2tondo 5. forj←1toy do 6. F[j]i1, i,←F[-j] 7. t[j]i1, i,←t[-j] fF[j-i]]i]≤F[-j] 8. ii,v[+w[i1, 9. tei,←F[j-i]]i] hnF[j]i,v[+w[ 第 章 43 算法设计与分析习题解答与学习指导(第3 版) 4 4 10. t[i,j]←i 11.return二维数组F,t 算法的时间复杂度主要取决于第4行和第5行的for循环,内部工作量是常数时间,算 法的时间是O(ny).通过数组t 追踪解的过程比较简单,时间不超过O(ny).于是算法最坏 情况下的时间复杂度是O(ny). 针对给定实例,算法的备忘录如表3.5和表3.6所示. 表3.5 Fk (x) k x 1 2 3 4 5 6 7 8 9 10 11 12 1 1 2 3 4 5 6 7 8 9 10 11 12 2 1 2 3 2 3 4 5 4 5 6 7 6 3 1 2 3 2 3 4 5 4 5 6 7 6 4 1 2 3 2 3 4 5 4 5 6 7 6 表3.6 tk (x) k x 1 2 3 4 5 6 7 8 9 10 11 12 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 2 2 2 2 2 2 2 2 2 3 1 1 1 2 2 3 3 2 2 3 3 2 4 1 1 1 2 2 3 3 2 2 3 3 2 问题实例的解是:最轻重量是6,由t4(12)=2知道x4=0,x3=0,x2≥1,再由 t2(12-4)=t2(8)=2.x2 ≥2 t2(8-4)=t2(4)=2.x2 ≥3 t2(4-4)=t2(0)=0.x2 =3, x1 =0 从而得到x1=x3=x4=0,x2=3,只用了3枚币值为4的硬币. 3.6 使用动态规划算法.令Fk(y)=0,1. Fk(y)=1.用前k 种钱币、总钱数为y 时可以付款 那么Fk(y)满足如下递推方程: Fk(y)=max{Fk-1(y),Fk-1(y -vk)}, k =2,3,…,n,y =1,2,…,M F1(y)= 1 若y =v1 0 否则 Fk(y)=0 若y <0,k =2,3,…,M 设立标记函数ik(y) ik(y)= k 若Fk-1(y -vk)=1 ik-1(y) 否则 动态规划 第3章 4 5 算法计算出Fn(M ).如果Fn(M )=1,则存在一种找零钱的方法.所使用的零钱币值可根据 ik(n)的值向前追踪得到.算法的时间复杂度为T(n)=O(nM ). 3.7 (1)设yi=1表示选择了位置i,yi=0表示没有选位置i,问题的目标函数和约 束条件是: maxΣn i=1 piyi |xi -xj|≥d, i,j=1,2,…,n, i ≠j, yi =yj =1 (2)排序使得x1d Nj(0)=0 Nj(d)=-∞ d <0 自底向上计算,存储使用备忘录方法.可以使用标记函数B(j)记录使得Nj(d)达到最大时是否 Nj-1(d -t(j))+vj >Nj-1(d) 46 算法设计与分析习题解答与学习指导(第3版) 如果是,则B(=否则B(=j-1). j)j; j)B( 算法的伪码如下 : 输入:加工时间t[1. n],效益v[1. n],结束时间 D 输出:最优效益 N [j],标记函数B[j],…n,2,… , i,i,i=1,2,j=1, D 1.ford←1tot[1]- 1 2. N [1,d]←0,B[1]← 0 3.ford←t[1]toD 4. N [1,d]←v[1],B[1]← 1 5.forj←2ton 6. ford←1toD ← N [d] 7. N [j,d]j-1, B[d]←B[1,d] 8. j,j 9. ij]nj-d-j]]+v[> N [1, fd≥t[adN [1,t[j]j-d] 10. tej,← N [1,t[+v[ hnN [d]j-d-j]]j] j, 得到最大效益 N [n,D] 通过对B[D]的追踪,可以得到问题的解 . 11. B[d]← j o 后, n, nD) 算法的主要工 作是第5行和第6行的fr循环,需要执行O(次,循环体内的工作量是常数,追踪解的 工作量不大,于是算法最坏情况下的时间复杂度是O(. nD) 3.10 设xi i1,n, 表示装入背包的第i种物品个数,=2,…,推广的01背包问题的描述是: n maxΣvixi i=1 Σ(n) wixi ≤ W i=1 Σ(n) cixi ≤ V i=1 xi=0,1 i,k] 设m[j,表示使用前 i 种物品、背包重量限制为j、容积为 k 时的最大价值,其中 i=2,…,j=2,…,k=2,…,那么递推方程是:1,n,1, m[ W , j, 1, m[ V, j-wi,c若 j ≥wi max{i-1,k],i-1,k-i]+vi} 且 k ≥cii,k]i-1,k] m[j,= m[ nj, , j=2,…,1, V 否 则 i=2,…,1, W ,k=2,… , j,v1 如果 j ≥w1 且 k ≥c1 m[1,k] = 0 否 则 m[i,0,=m[j, = k]i,0] 0 m[j,=-∞ j <0或 k <0 i,k] i,k] 与前面的背包问题类似,可定义标记函数t[j,用于追踪问题的解.其中 t[j,= t[ 如果 jm, [j,i-1,k-i]+vi, j ≥wi, k ≥c i i-1,k]≤m[j-wi,cii,k]i-1,k] 否则 i=n,j=2,…,V 2,…,1, W ,k=1,2,…, 动态规划 第 t[1,k]1 如果 j ≥w1 且 k ≥c1 3 j, = 0 否则 章 该算法最坏情况下的时间复杂度是O( nWV) . 3.x0,1} 11 设X={x1,…,xn-顺时针排列在圆环上.类似于矩阵链乘法的动态规划 算法,用 i 和 j 界定子问题的边界.Xij 表示按顺时针合并{xi,xi+1,…,xj }后的数组,其含 有的整数个数是nj,完成合并在最坏情况下所需的最少比较次数记作m[j], 0, 47 i,其中i= 1,…,n-1,1,(i) n-1. j=0,…, 考虑数组Xik 和X(k+1)合并成Xij 的比较次数.因为它们都是排好序的,比较次数至多 j 是元素总数减1,于是合并这两个数组的比较次数在最坏情况下是: j-1 与矩阵链乘法的不同在于:矩阵链的子问题的边界是排列成一条线,保持i≤j;而这里是 环,可能出现i> j 的情况 . 3所示, 右边的合并 nik +n(k+1) 如图3.左边的合并对应的是i< j 的子问题, 对应的是i> j 的子问题.在i> j 时相应的递推方程就不一样了 . 图3.子问题的归约 3 令m[j]表示在最坏情况下合并成Xij 考虑在i< j 的情 i,所需要的最少的比较次数 . 况,Xik 与X(k+1)合并的比较次数至多是nik +n(k+1)1,于是有 jj j i,{m[k]+m[j]} + Σ m[j] = min i,k+1,nt-1 i≤k j 时,如图3.b) 当 k 取n-k+1=0, 化(t) 函数的和应该是: 3(所示,1时,这时优 m[0,k]+m[(dn, i,i, n-1]+m[j]=m[k+1)moj] 而为计算合并的比较次数,需要分成两段求和,即 - njnt-1 Σ(1) (n) t+ Σ t= i t=0 于是有 j m[j]{m[k]+m[j]} + Σ i, = min i,k+1,nt-1,ij i≤k≤n-1 i, 0≤k1 w [i+1,i+1]=min{xi+1,s1}, i=0,1,…,n 假设最后一次检修机器在第i 天,那么从第i+1天到第j 天连续加工任务总数为 w [i+1,j],而检修前加工任务数至多是F [i-1].于是当最后一次检修发生在第i 天时, 50 算法设计与分析习题解答与学习指导(第3版) 到第 j 天为止,加工任务数至多是F[i+1,.考虑到所有可能的检修时间 i(=2,…,1), i-1]+ w [j] 可以得到如下递推关系: i1,j-或者在第 j 天之前根本不做检修的情况, F[0ma1 j] j>0 可以定义标记函数记录得到最优 F[0]=0 F[j]时的检修时间i.如果每次都重新计算 w [i+1, n3)如果在预处理时根据w[j] j], 算法最坏情况下的时间复杂度是O( . i.的递推方程计算所有 的w[j],并把计算结果存成备忘录, j] 那 i,1≤i≤j≤n, 在计算F[时直接查找相应的值, 么计算F[的时间可以降为O(而预处理的时间也是O(因此算法最坏情况下的 j] n2), n2) , 时间复杂度是O( . n2) 方法二:参照矩阵链相乘的方式划分子问题,该算法的时间复杂度高一些 . 首先证明下述命题 . 命题3.2 在最优解中不会出现连续两天检修的情况 . 证假若不然,在一个最优解 T 的第 i 和i+1 天都进行检修.那么,当去掉第 i 天的检 修后,不会减少从第i+1 天到第 n 天的加工量;也不会减少第1天到第i-1天的加工量; 只有第 i 天的加工量由0增加到min{xi,t}, 其中s表示第 i 天机器具有的加工能力.于 st 是总加工量将大于原来的加工量,从而与 T 的最优性矛盾 . 通过类似的分析还可以证明,检修也不会发生在子问题的最后一天 . 利用上述性质,可以从检修的时间点 k 将原问题划分成两个子问题.i,表示第 i1,0< y ≤ K y)a1 y ≥a1 F1( = 0 y