第3 章
动态规划
3.1 内容提要
1.基本概念
动态规划(dynamicprogramming)是一种求解多阶段决策(优化)问题的算法设计技
术,其主要思想是:将原问题归约为规模较小、结构相同的子问题,建立原问题与子问题优
化函数间的依赖关系.从规模最小的子问题开始,利用上述依赖关系求解规模更大的子问
题,直到得到原始问题的解为止.
动态规划算法的适用条件 适用于求解多阶段决策(优化)问题,该问题的解可以表示
为一个决策序列,且满足优化原则(或最优子结构性质),即一个最优决策序列的任何子序列
本身一定是相对于子序列的初始和结束状态的最优决策序列.
对于规模大的实例,对存储空间的需求是该算法的瓶颈.
主要设计步骤
(1)写出所要求解的组合优化问题的目标函数和约束条件.
(2)确定子问题的结构与边界,将问题求解转变成多步判断的过程.
(3)定义优化函数,以该函数的极大值或者极小值作为判断的依据,确定是否满足优化原则.
(4)列出有关优化函数的递推关系和边界条件.
(5)根据问题的解的不同情况,考虑是否需要设立标记函数.
(6)从初值开始,自底向上计算每个子问题的优化函数值(有的需要同时计算标记函
数),并以备忘录的方式存储所有的中间结果.
(7)如果有标记函数,则根据标记函数逐步追踪问题的解.
2.时间复杂度的分析方法
时间复杂度取决于备忘录(包括优化函数及标记函数)中每个项的计算工作量,以及用
标记函数追踪解的工作量.大多数情况下,追踪解的工作量不超过优化函数计算的工作量,
因此可以根据递推关系确定备忘录中每个项的计算工作量,然后对这些工作量求和.
3.典型的动态规划算法
矩阵链相乘 MatrixChain(P ,n)给定矩阵链A1..n=A1A2…An ,其行和列数为向量
P=<P0,P1,…,Pn >,其中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≤k<j
用标记函数s[i,记录使得优化函数
m
[达到最小值时的
k
值,
i,可用于追踪加括号的
位置,备忘录是nj×]
n
的m[j] i,
j
表
]
,j=2,…,时间复杂度是O(.
i,表和s[j] i,1,n, n3)
背包问题(一个旅行者准备随身携带一个背包.可以放入背包的knapsackproblem)
j=2,…,如果每种物品放入背
物品有
n
种,每种物品的重量和价值分别为wj
和vj
,1,n.
包的数量不限,背包的最大重量限制是b,怎样选择放入背包的物品以使得背包的价值
最大?
使用组合优化问题的描述方法,设xj
表示装入背包的第
j
种物品的数量,背包问题
可
以描述
为
n
目标函数maxΣvjxj
j=1
约束条件Σ(n) wjxj
≤
b
j=1
2,…,
当每种物品只有1个,即xj
只能取0或1时,称为0-1背包问题
.
使用动态规划的方法求解背包问题.设Fk
(y)表示只允许装前
k
种物品,背包总重不
超过
y
时背包的最大价值,则
Fk
(y)=max{Fk-y),y-wk
)+vk
},k=2,…,=1,
b
xj∈N,j=1,
n
1(Fk
(1,n,
y
2,…,
y)
0
Fk
(0)=0 0≤
k
≤
n
Fk
(y)=-∞
y
<
0
根据上面的递推式,当k=1时,可以得到
y
F0(=0≤
y
≤
b
v1w1
F1(y)
=
令ik
(表示在计算优化函数值Fk
(时所用到物品的最大标号,则
y) y)
ik
(
=
ik1(-
1(
y)>Fk
(-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
<w1
该算法最坏情况下的时间复杂度为O(b)
n.
最长公共子序列LCS(X,m,n) 给定长度分别为
m
和
n
的序列
X
和Y,求
X
与
Y,
Y
的最长公共子序列Z.
设Xi=<x1,x2,…,y2,…,设C[表示Xi
与Yj
的最长公
共子序列的长度,则
xi>,yj
>, j]
Yj
=<y1,i,
算法设计与分析习题解答与学习指导(第3 版)
3 4
C[i,j]=
C[i-1,j-1]+1 如果i,j >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 =<p1,p2,…,pn >,其中pi
为第i 个像素的灰度值,采用变位压缩存储格式,如何对P 进行分段,以使得存储P 占用的
二进制位数达到最少?
设S[i]表示输入为<p1,p2,…,pi>时按最优分段存储所使用的二进制位数,则
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]表示最后一段<pi-j+1,…,pi>中的最大灰度值在存储时所占用的二进
制位数.11是存储该分段信息的额外开销.用标记函数l[i]记录进行最优划分时最后一段
的像素个数,可用于追踪达到最小存储位数时的分段位置.该算法最坏情况下的时间复杂
度为O(n).
最大子段和MaxSum(A ,n) 给定n 个整数的序列A =<a1,a2,…,an >,求
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,x2,…,xn >是数据集,称(-∞,x1),(x1,x2),…,
(xn-1,xn),(xn ,+ ∞)为第0,1,2,…,n 个空隙.与S 相关的存取概率分布是P =
<a0,b1,a1,b2,…,ai,bi+1,…,bn ,an >,其中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]=<xi,xi+1,…,xj >表示S 以i 和j 作为边界的子数据集,P [i,j]=
<ai-1,bi,ai+1,bi+1,…,bj,aj+1>是子数据集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=<x1,x2,…,xn
>是
n
个不等的整数构成的序列,
A
的一个单调递增子序
列是序列<xi1,,…,>,使得i1<i2<…<ik
,且xi1<xi2<…<xi子序列<xi1,
xi2xik.
k
xi2,…,xi>的长度是含有的整数个数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<j≤n.划分后三角形ijk 的权值等于其周长,求具有最小权值
的划分方案.设计一个动态规划算法求解这个问题,说明算法的时间复杂度.
图3.1 五边形的划分方案
3.13 图的连通性问题是图论研究的重要问题之一,在实际中有着广泛的应用.例如,
通信网络的连通问题,运输路线的规划问题等.一个著名的检查图的连通性的算法就是
Warshall算法.假设D =<V,E >是顶点集为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,则C[否则
,
因
此
i]x{j]}+1; i]
i]
.
=maC[C[=1.
C[
=
max{C[j]}+1.j(1≤
j
<i,xj
<xi)i]1 .j(1≤
j
<i,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
<lk
k-1,-
k
]+vk
}
D
≥
y
≥l
C[1,v1
y
≥l1
y]
=
0
y
<l1
算法的伪码如下:
Store
V[//
L
和
V
是货柜长度和价值序列,
输入:数组L[1.
n],1.
n],DD
为库房长度
输出:最大的收益C[
n,D]
1.fory←1toD
y]1]
2. C[1,←V[
动态规划
第3章
4 1
3.fork←2ton
4. fory←1toD
5. C[k,y]←C[k-1,y]
6. i[k,y]←i[k-1,y]
7. ify≥L[k]andC[k-1,y-L[k]]+V[k]>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 <F[k -1,y]
k 否则,k >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)排序使得x1<x2<…<xn ,Fk(y)表示考虑前k 个位置,距原点最远到y 的范围
内开设商店的最大收益.那么Fk(y)满足如下递推方程:
Fk(y)= max{Fk-1(y),Fk-1(xk -d)+pk} 如果xk ≤y
Fk-1(y) 否则
F1(y)=
p1 如果x1 ≤y
0 否则
如下定义标记函数:
ik(y)=
k 如果Fk-1(xk -d)+pk ≥Fk-1(y)
ik-1(y) 否则
i1(y)= 1 如果x1 ≤y
0 否则
算法的时间复杂度为O(nD +nlogn),其中D =max{xi|i=1,2,…,n}.
3.8 令B=.N/2.,那么min Σ ai∈A1
ai,Σ aj ∈A2
{ aj} ≤B.不妨设Σ ai∈A1
ai ≤ Σ aj ∈A2
aj.那么问
题变成求A 的子集A1 使得
maxΣ ai∈A1
ai
Σ ai∈A1
ai ≤B
那么该问题等价于双机调度问题(习题3.4).通过动态规划算法求出最优解A1,如果A1 中
的数之和Σ ai∈A1
ai =B,那么输出“Yes”,否则输出“No”.该算法的时间复杂度为O(nN ).
3.9 与0-1背包问题类似,使用动态规划方法.令Nj (d)表示考虑作业集{1,2,…,
j}、结束时间为d 的最优调度的效益,那么
Nj(d)= max{Nj-1(d),Nj-1(d -t(j))+vj} d ≥t(j)
Nj-1(d) d <t(j)
N1(d)=
v1 t(1)≤d
0 t(1)>d
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=
i
当i>
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,i<j
i≤k<jt=
i
-1
j
m[{i,j]}+Σ(n)
j]
=
min k+1)modn,nt+
Σnt-1,i>j
i≤k≤n-1
i,
0≤k<jm[k]+m[(t=
i
t=0
i,1,…,
上述公式中的m[i,i]是递推关系的初值.算法将从规模为1的子问题开始迭代计算,直到
规模为
n
的问题为止.在矩阵链相乘问题中,规模为
n
的子问题只有一个;而在环形排列的
=0,n
m[i]
=
0,i=
0,n-1
合并问题中,规模为
n
的子问题可能以i1,…,1中的任何位置为起点,恰好有
n
个
.
我们需要从这
n
个子问题的解中找到具有最小比较次数的解.于是最少的比较次数是:
算法设计与分析习题解答与学习指导(第3版)
{i,(dn]}
m=
min m[i+n-1)mo
0≤i≤n
与矩阵链乘法相似,计算m[j] 需要用标记函数s[j] i,取得最小
i,过程中(1) i,记录使得m[j]
值的k.以便找到最优的合并次序.与矩阵链乘法问题
类
似,该算法最坏情况下的时间复杂度是O(
.
n3)
3.12
如图3.
n
边形的顶点是1,n.顶
4所示,2,…
,
点i-1,
j
构成的凸多边形记作A[j],于是原
始
i,…,i,
问题就是A[2,.
i,的划分
,
n]
考虑子问题A[j] 假设它的所有划分
方
案中的最小权值是t[i,j]i+1,…
,
.从i,j-1中任
选
顶点k,它与底边(图3.
j
构成一个三角形(4中
的
灰色三角形)
和
.
A[
i-1)
j],
i,划分成两个凸多边
4
这个三角形将A[j]
形:A[i,k] k+1,从而产生了两个子问题.这图3.子问题归
约
两个凸多边形的划分方案的最小权值分别是t[i,k]
和
t[j]根据动态规划思想,A[j]相对于这个
k
的划分方案的最小权值是
:
k+1,.i,
t[i,k]+t[j]+d(
j
+d(1)
k+1,i-1)
k
+dki-
j
其中d(0(i) 是三角形(1)
j
的周长,于是得到递推关系:
i=
j
1)k
i-1)
k
+dkj
+d(-ji
t[j]mi{i,k+1,1)
j
+d(}
i
<j
i,
=
nt[k]+t[j]+d(
k
+dk1)
i≤k<ji-i-j
t[i]0
i,=
不难看出,这个递推关系与矩阵链相乘算法的递推式非常相似,可以定义标记函数记下
得到最小权值的
k
的位置,算法最坏情况下的时间复杂度是O(.
n3)
3.子问题分别对应于M0,M1,…,Mn
的计算.M0 是输入.在第
k
步计算Mk+1的
13
关键是找到它与前面矩阵的依赖关系.假设Mk
已经计算完毕,如何计算Mk+1呢? 这需要
对于每组i,确定Mk+1[j]是否为1.条件是:
j, i,
Mk+1[j]1.在
D
中存在一条从xi
到xj
且只经过{x1,x2,…,xk
,xk+1}中顶点的
i,
=
路径.可以将这种路径分成两类
:
第一类是只经过{x1,xk
} 这时Mk
[j]=1.
x2,…,中顶点的路径, i,
第二类是经过顶点xk+1的路径.因为回路可以从路径中删除,因此只需考虑经过xk+1
一次的路径.这条路径可以分成两段, 到xk+1, 因此有Mk
[k+1]
从xi
再从xk+1到xj
, i,=
1和Mk
[j]这就是对于第二类路径的判别条件,即
k+1,=1.
i,=i,=k+1,
=
算法Warshal
Mk+1[j]1.Mk
[k+1]1∧Mk
[j]
1
输入:
M
//图
D
的邻接矩
阵
输出:Mt
//图
D
的连通矩
阵
1.Mt←
M
2.fork←1tondo
3.
fori←1tondo
4.
forj←1tondo
48
动态规划
第3章
4 9
5. Mt[i,j]←Mt[i,j]+Mt[i,k]*Mt[k,j]
注意,上述算法中矩阵加法和乘法*中的元素相加都使用逻辑加,即1+0=0+1=1+
1=1,0+0=0.
下面分析算法的时间复杂度,在Warshall算法中,第2行、第3行、第4行都是n 步的
循环,因此第5行总共被执行n3 次,而每次只做1次乘法和1次加法,因此Warshall算法
的时间复杂度是O(n3).
对于给定实例,利用Warshall算法计算的矩阵序列如下:
M0 =
0 1 1 0
0 0 1 0
0 0 0 1
0 0 1 0
é
.
êêêêê
ù
.
úúúúú
, M1 =
0 1 1 0
0 0 1 0
0 0 0 1
0 0 1 0
é
.
êêêêê
ù
.
úúúúú
, M2 =
0 1 1 0
0 0 1 0
0 0 0 1
0 0 1 0
é
.
êêêêê
ù
.
úúúúú
M3 =
0 1 1 1
0 0 1 1
0 0 0 1
0 0 1 1
é
.
êêêêê
ù
.
úúúúú
, M4 =
0 1 1 1
0 0 1 1
0 0 1 1
0 0 1 1
é
.
êêêêê
ù
.
úúúúú
因此,a 可以连通到b,c 和d;b 可以连通到c 和d;c 可以连通到d;d 可以连通到c.
3.14 使用动态规划算法求解这个问题.先考虑子问题划分.设S1[1.. i]和S2[1..j]表
示两个子序列,C[i,j]表示S1[1.. i]和S2[1..j]的最小编辑距离.考虑最后一对字符,如果
S1[i]被删除,那么最小编辑距离是S1[i-1]和S2[j]的最小编辑距离加d;如果在S1[i]
后面插入S2[j],那么编辑距离是S1[i]和S2[j-1]的最小编辑距离加d;如果S1[i]被替
换成S2[j],那么最小编辑距离是S1[i-1]与S2[j-1]的最小编辑距离加r;如果S1[i]=
S2[j],那么最小编辑距离是S1[i-1]与S2[j-1]的最小编辑距离.递推关系如下:
C[i,j]=min{C[i-1,j]+d,C[i,j-1]+d,C[i-1,j-1]+t[i,j]}
i=1,2,…,n, j=1,2,…,m
t[i,j]= 0 S1[i]=S2[j]
r S1[i]≠S2[j]
C[0,j]=jd
C[i,0]=id
可以定义标记函数记录得到最优C[i,j]时所对应的选择(删除、插入、替换等),算法的时间
复杂度是O(nm ).
3.15 方法一:设F[j]表示第1,2,…,j 天加工任务的最大数目.如果在第i 天进行检
修,那么从第i+1天到第j 天连续工作的加工量用w [i+1,j]表示,则
w [i+1,j]= Σj
k=i+1min{xk, sk-i}, 0≤i <j ≤n
不难看出,w [i+1,j]满足如下递推方程:
w [i+1,j]=w [i+1,j-1]+ min{xj,sj-i}, 0≤i <j ≤n,j >1
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[0ma<i<x j{F[i+1,j]=max w[1,
i-1]+w[j]}j>1
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,表示第
i<k<j,
设G[j]
i
天到第
j
天的最大加工任务数.如果在第
k
天进行检修,那么最大加工任务数等
于G[i,k-+G[j]如果在第
i
天到第
j
天的时间内没有发生检修,
1]k+1,
.
那么加工任务
数是w[j],
x{i,{i,j]},1≤
i
<
k
<
j
≤
n
i,于是得到如下递推方程
:
G[i,j]w[j],G[k-1]+G[
=mamax k+1,
i<k<j
i,=w[i],i=2,…,
标记函数的设定可参照矩阵链相乘问题的做法,只是当最优解的第
i
到第
j
天之间没
有进行检修时将标记函数设为0.该算法最坏情况下的时间复杂度是O(
.
G[i]i,1,
n
3.16
设x1,xn
是0或1,xi=
n3)
那么
x2,…,1当且仅当下载请求
i
被批准
.
n
maxΣaixi
i=1
Σ(n) aixi
≤
K
,xi=0,1
i=1
类似于01背包问题,令Fi(表示考虑前
i
个申请,带宽限制为
y
时的最大带宽使用
量,则有如下递推式:
=maFiy),1(
-y)
Fi(y)x{-1(Fi-
y
-ai)+ai},i>1,0<
y
≤
K
y)a1
y
≥a1
F1(
=
0
y
<a1
Fi(0)=0
Fi(y)=-∞,
y
<0
1,
n
的情况.
与前面背包问题类似可设立标记函数,自底向上顺序处理i=2,…,对于
动态规划
第
给定的i,令y=1,2,…,
K
,依次确定各个子问题的Fi
(y)值,最后由标记函数得到xi
的
3
值.算法时间复杂度为O(.
nK)
章
3.令F[j]
j],
j
j-1]}+ai
则
3,…,3,…,
17
i,表示a11到ai的路径上的数的最小和
,
F[i,j]iF[F[
j
,i=n,2,i-
1
=mn{i-1,i-1,2,j=
F[i,1]F[2,3,…
,
51
=i-1,1]+ai1,i=
n
F[i]i-1,2,3,…
,
i,=F[i-1]+ai
,i=
n
F[1,1]=a11
问题的最优路径上的和是:
n{n,2,…,
miF[j]|j=1,n}
可以定义标记函数k[j], i,时的路径选择,即
i,记录得到最优F[j]
i,=
j
若F[j]<F[j-1]k[j]j-1 否则
i-1,i-1,
算法的时间复杂度为O(.
n2)
3.本题不是优化问题.也可以使用动态规划的设计思想,通过多阶段决策来求解.
18
与一般优化问题的区别在于:当把一个问题的计算与子问题的计算建立递推关系时,不是
只考虑达到最优的那个子问题的结果,而是考虑所有可能的子问题的结果.考虑到每个串
计算的结果至多是三种:a,c, 需要把它们全部保留下来.因此,可以把
b,为了后面的计算,
记录优化函数的一个极大或极小值推广到记录有限个值.只要用含有三个项的数组替换备
忘录中的一个项,就可以使用类似于矩阵链相乘的方法划分子问题,并利用动态规划方法设
计算法
.
令X[i,j]是串xixi+1…xj
的可能的运算结果(由于计算顺序不同,结果可能不唯一,
但至多为三个结果,即a,设计存储X[的结构为3×2阵列,分别记录三个可能的
b,.j]
b
或c)
c)i,
自底向上计算,
运算结果(可能取a,和得到这个结果时所对应的划分位置k.
通过较
小子问题的结果来计算较大子问题的结果,其递推公式是:
X[i,j]i,X[j],1≤
i
<
j
≤n,k=i+1,…,
=X[k]k+1.i,j-1
X[i]2,…,
伪码如下:
i,=xi,i=1,
n
1.fori←1ton
i,
3.forr←2ton-
1
2. X[i]←xi
4. fori←1ton-r+1
5. j←i+r-1
6. fork←itoj-1
//计算所有大小为
r
的子问题
//子问题的前边界
i
//子问题的后边界j//在
k
位置划分成两个更小的子问题
7. j]i,X[j]
X[i,←X[k]k+1,
//记录X[j]可能的结果和划分位置k,至多为三个
8.fork←1ton-1
i,
//规模为
n
的原始问
题
fX[k]n]"//存在计算顺序结果为
a
9. ik+1,="a"thenreturn"1
10.return"0"
1,X[
//没有结果等于
a
与矩阵链计算类似,可通过所记录的
k
值追踪出相应的运算顺序.该算法最坏情况下
的时间复杂度为O(.
n3)