计算机算法设计与分析

第三章

动态规划

基本思想是将待求解问题分解成若干个子问题，但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。

基本步骤

找出最优解的性质，并刻划其结构特征。 递归地定义最优值。 以自底向上的方式计算出最优值。

根据计算最优值时得到的信息，构造最优解。

1.动态规划算法的基本要素：重叠子问题；最优子结构。 2.矩阵连乘问题(P47的例题)

设计算A[i:j]，1≤i≤j≤n，所需要的最少数乘次数m[i,j]，则原问题的最优值为m[1,n] ：

当i=j时，A[i:j]=Ai，因此，m[i,i]=0，i=1,2,…,n

[i,j]?m[i,k]?m[k?1,j]?pi?1pkpj当i

这里 A的维数为 pi?1?pii

0i?j??

m[i,j]??min{m[i,k]?m[k?1,j]?pi?1pkpj}i?j ?i?k?j? kj ? 的位置只有 i 种可能

矩阵A和B可乘的条件：A的列数=B的行数 若A是pq的矩阵，B是q r的矩阵，则乘积C=AB是p r的矩阵，且总共需要pqr次数乘。

示例：求三个矩阵A1A2A3的连乘积，3个矩阵的维数分别为10 100，100 5，5 50。

一种连乘次序 ((A1A2)A3)，数乘次数=10 100 5+10 5 50=7500。

另一种连乘次序：(A1 ( A2A3) ) ，数乘次数=100 5 50+10 100 50=75000。

3. 0-1背包问题 问题描述：

给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?

在选择装入背包的物品时，对每种物品i只有两种选择，即装入背包或不装入背包。不能将

物品i装入背包多次，也不能只装入物品i的一部分。 算法描述：

输入：物品集合U={u1,u2,…, un}，重量分别为w1,w2,…, wn，价值分别为v1,v2,…, vn，容量为C的背包。

输出：最大价值 ，满足 。

For i 0 to n //背包容量为0 m[i][0] 0 End for

For j 0 to C //物品集合为空 m[0][j] 0 End for

For i 1 to n //物品集不为空，背包容量为C For j 1 to C

m[i][j] m[i-1][j] //当物品i的重量大于背包容量时 if w[i]j then //当物品i的重量小于背包容量时 m[i][j] max{m[i-1][j], m[i-1][j-w[i]]+v[i]} End if End for End for

Return m[n][C]

例题：

第四章贪心算法

1.贪心算法的基本要素： a贪心选择性质

指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素。 b.最优子结构性质

当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。

2.背包问题

与0-1背包问题类似，所不同的是在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包。

即给定C>0, wi>0, vi >0, 1≤i≤n, 要求找出一个n元向量(x1, x2, ..., xn)，0≤xi≤1，1≤i≤n ，使得 , 且 最大。

用贪心算法解背包问题的基本步骤： 计算每种物品单位重量的价值vi/wi ;

依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包;

若将这种物品全部装入背包后，背包内的物品总重量未超过C，则选择单位重量价值次高的物品并尽可能多地装入背包;

依此策略一直地进行下去，直到背包装满。 3.哈夫曼编码

哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树T。

（哈夫曼提出了构造最优前缀码的贪心算法，由此产生的编码方案称为哈夫曼编码。 哈夫曼编码算法用字符在文件中出现的频率表来建立一个用0，1串表示各字符的最优表示方式。

给出现频率高的字符较短的编码，出现频率较低的字符以较长的编码，可以大大缩短总码长。 ）

4.最小生成树 Prim算法

例如，对于右图中的带权图，按Prim算法选取边的过程如下图。