算法设计与分析考点精讲串烧

直到从源点到其他各个定点的最短路径全部求出为止，该算法俗称Dijkstra算法。 3.动态规划：

基本思想：实质是分治思想和解决冗余。将待求解问题分解为更小的、相同的子问题，然后对子问题进行求解，最终产生一个整体最优解。 求解步骤：

1分析最优解的性质，刻画最优解的结构特征。 ○

最优子结构的性质分析（整体最优包含子问题最优） 2递归定义最优值。 ○

建立最优值的递归关系式

3以自底向上的方式计算出最优值，并记录相关信息。 ○

4根据计算最优值时得到的信息，构造出最优解。 ○基本要素：

1最优子结构性质 ○

2子问题重叠性质 ○

3自底向上的求解方法 ○

4. Prim算法与Kruskal算法的比较

设无向连通带权图G具有n个顶点和e条边

(a)从算法的思想上说，如果G的边数较小时，可以采用Kruskal，因为Kruskal每次

查找最短的边；边数多可以采用Prim算法，因为它每次加一个顶点。可见Kruskal用于稀疏图，Prim用于稠密图。

(b)从时间上说，Prim算法的时间复杂度O(n) ,Kruskal的时间复杂度O(eloge)(e为

2

边数)

(c)从空间上说，Prim算法需要很小的空间，Kruskal算法需要占用很大的空间。

算法设计题（本题15分）

分别用贪心算法、动态规划法、回溯法设计0-1背包问题。要求：说明所使用的算法策略；写出算法实现的主要步骤；分析算法的时间。

（1）贪心算法 O（nlog（n））

? 首先计算每种物品单位重量的价值Vi/Wi，然后，依贪心选择策略，将尽可能多的

单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品

总重量未超过C，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。 （2）动态规划法 O(nc)

m(i，j)是背包容量为j，可选择物品为i，i+1，…，n时0-1背包问题的最优值。由0-1

背包问题的最优子结构性质，可以建立计算m(i，j)的递归式如下。

j?wi?max{m(i?1,j),m(i?1,j?wi)?vi}m(i,j)??0?j?wim(i?1,j)??vnm(n,j)???0j?wn0?j?wnn

（3）回溯法 O(2)

cw:当前重量 cp:当前价值 bestp：当前最优值 void backtrack(int i) //回溯法 i初值1 { if(i > n) //到达叶结点

{ bestp = cp; return; } if(cw + w[i] <= c) //搜索左子树 { cw += w[i];

cp += p[i]; backtrack(i+1); cw -= w[i]; cp -= p[i]; }

if(Bound(i+1)>bestp) //搜索右子树

backtrack(i+1); }