发布时间 : 星期日 文章算法设计与分析考点精讲串烧更新完毕开始阅读a793662a5901020207409c5d
直到从源点到其他各个定点的最短路径全部求出为止，该算法俗称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); }