算法分析与设计复习大纲(全)(3)

关键问题：完全二叉树中，根结点的左右子树均是堆，如何调整根结点，使整个完全二叉树成为一个堆？

第6章 动态规划法

了解动态规划法的设计思想

设计思想：将待求解问题分解成若干个相互重叠的子问题，每个子问题对应决策过程的一个阶段，将子问题的解求解一次并填入表中，当需要再次求解此子问题时，可以通过查表获得该子问题的解而不用再次求解。 步骤：

将原始问题分解为相互重叠的子问题，确定动态规划函数； 求解子问题，填表；

根据表，自底向上计算出原问题的解。

掌握可以用动态规划法解决的问题及时间复杂度：

TSP，多段图的最短路径问题，0/1背包，最长公共子序列问题，最优二叉查找树，近似串匹配问题； 多段图的最短路径问题： O(n+m) 0/1背包问题： O(n×C)

掌握多段图的最短路径问题的动态规划算法

动态规划函数为：

cost[i]中存储顶点i到终点的最短路径长度

cost[i]=min{C[i][j]+cost[j]} (i≤j≤n且顶点j是顶点i的邻接点) path[i]=使C[i][j]+cost[j]最小的j 先构造cost数组和path数组

掌握0/1背包问题的动态规划算法及具体实现

例题：用动态规划法求如下0/1背包问题的最优解：有5个物品，其重量分别为（3，2，1，4，5），物品的价值分别为（25，20，15，40， 50），背包容量为6。写出求解过程。 0/1背包问题的动态规划函数为：

V(i,j)表示把前i个物品放入容量为j的背包中的最大价值和。 填表过程：

放入背包中的物品的求解过程：则65表示把5个物品放入容量为6的背包中的最大价值和。 i=5,j=6; v[5][6]>v[4][6],x[5]=1, j=6-w[5]=1 i=4,j=1; v[4][1]=v[3][1], x[4]=0

i=3,j=1; v[3][1]>v[2][1], x[3]=1, j=1-w[3]=0 i=2,j=0; v[2][1]=v[1][0], x[2]=0 i=1,j=0; v[1][0]=v[0][0], x[1]=0 结果是把第3个和第5个放入了背包

第7章 贪心法

了解贪心法的设计思想

贪心法在解决问题的策略上目光短浅，只根据当前已有的信息就做出局部最优选择，而且一旦做出了选择，不管将来有什么结果，这个选择都不会改变。 贪心法的关键在于决定贪心策略。

掌握可以用贪心法解决的问题：

TSP问题中的两种解决方法：最近领点策略，最短链接策略

最小生成树问题的两种算法：最近顶点策略（Prim算法），最短边策略（Kruskal算法） 背包问题，活动安排问题，多机调度问题。

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库算法分析与设计复习大纲(全)(3)在线全文阅读。