第5章-6-动态规划-算法设计基本方法教案资料.pptVIP

第5章-6-动态规划-算法设计基本方法;分治法基本思想;动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题;但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。;如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。;动态规划基本步骤;例矩阵连乘积;例矩阵连乘积;16000,10500,36000,87500,34500;给定n个矩阵，其中与是可乘的。考察这n个矩阵的连乘积

由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。

若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积;给定n个矩阵｛A1,A2,…,An｝，其中Ai与Ai+1是可乘的，i=1，2…，n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。;动态规划;特征：计算A[i:j]的最优次序所包含的计算矩阵子链A[i:k]和A[k+1:j]的次序也是最优的。

矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法求解的显著特征。;建立递归关系;计算最优值;用动态规划法求最优解;A1;算法复杂度分析：

算法matrixChain的主要计算量取决于算法中对r，i和k的3重循环。循环体内的计算量为O(1)，而3重循环的总次数为O(n3)。因此算法的计算时间上界为O(n3)。算法所占用的空间显然为O(n2)。;动态规划算法的基本要素;动态规划算法的基本要素;动态规划算法的基本要素;0-1背包问题;在0/1背包问题中，需对容量为c的背包进行装载。从n个物品中选取装入背包的物品，每件物品i的重量为wi，价值为pi。对于可行的背包装载，背包中物品的总重量不能超过背包的容量，最佳装载是指所装入的物品价值最高，即p1*x1+p2*x1+...+pi*xi(其1=i=n，x取0或1

;设所给0-1背包问题的子问题;intknapSack(intn,intc,intw[],intv[],intm[6][N],intx[])

{intjmax=min(w[n]-1,c);

for(intj=0;i=jmax;j++)?m[n][j]=0;

for(intj=w[n];j=c;j++)?m[n][j]=v[n];

for(inti=n-1;i1;i--)

{jmax=min(w[i]-1,c);

for(j=0;j=jmax;j++)m[i][j]=m[i+1][j];

?for(j=w[i]0;j=c;j++)

????m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]);

?}

?m[1][c]=m[2][c];

if(c=w[1])m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]);

?}

;//traceback返回最优值

……

for(inti=1;in;i++)

if(m[i][c]==m[i+1][c])x[i]=0;

else

{x[i]=1;

c=c-w[i];

}

x[n]=(m[n][c]?1:0)

M[1][c]为最优解

?;算法复杂度分析：

从m(i，j)的递归式容易看出，算法需要O(nc)计算时间。当背包容量c很大时，算法需要的计算时间较多。例如，当c2n时，算法需要Ω(n2n)计算时间。;小结

动态规划法的定义：

在求解问题中，对于每一步决策，列出各种可能的局部解，再依据某种判定条件，舍弃那些肯定不能得到最优解的局部解，在每一步都经过筛选，以每一步都是最优解来保证全局是最优解，这种求解方法称为动态规划法。;适合于用动态规划法求解的问题具有以下特点：

1、可以划分成若干个阶段，问题的求解过程就是对若干个阶段的一系列决策过程。

2、每个阶段有若干个可能状态

3、一个决策将你从一个阶段的一种状态带到下一个阶段的某种状态。

4、在任一个阶段，最佳的决策序列和该阶段以前的决策无关。

5、各阶段状态之间的转换有明确定义的费用，而且在选择最佳决策时有递推关系（即动态转移方