算法设计与分析 - 总结0

掌握选择问题的算法的伪代码（P105-106）

习题5-1，算法设计题

习题5-4，给出任意一组数据，能分别用筛选法和插入法写出创建堆的过程，并用两种方法进行堆排序。

对（47，5，26，28，10）进行筛选堆排序，使用大根堆，形成升序 ，列出每次筛选后的序列

形成大根堆的过程（先把数组直接表示成完全二叉树）： 47，5，26，28，10（叶子结点，不用筛选） 47，5，26，28，10 （叶子结点，不用筛选） 47，5，26，28，10 （叶子结点，不用筛选） 47，5，26，28，10

47，28，26，5，10 （5与两个孩子中的大者比较，5小，交换位置） 47，28，26，5，10 （47与两个孩子中的大者比较，47大，不用交换位置） 47,28, 26, 5 ,10 （大根堆）

10,28, 26, 5 , 47 （取出堆顶元素后的序列） 10,28, 26, 5 , 47 （筛选） 28, 10 , 26, 5 , 47

28, 10 , 26, 5 , 47 （大根堆）

5, 10 , 26, 28, 47 （取出堆顶元素后的序列） 5, 10 , 26, 28, 47 （筛选） 26, 10 , 5, 28, 47

26, 10 , 5, 28, 47 （大根堆）

5, 10 , 26, 28, 47 （取出堆顶元素后的序列） 5, 10 , 26, 28, 47 （筛选） 10, 5 , 26, 28, 47

10, 5 , 26, 28, 47 （大根堆）

5, 10 , 26, 28, 47 （取出堆顶元素后只剩一个值，结束算法） 对（47，5，26，28，10）进行插入法生成大根堆 47 47 5 47 5 26 47 28 26 5 47 28 26 5 10

第6章 动态规划法

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

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

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

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

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

TSP，多段图的最短路径问题，0/1背包，最长公共子序列问题，最优二叉查找树，近似串匹配问题；

多段图的最短路径问题： O(n+m)

0/1背包问题： O(n×C)

掌握多段图的最短路径问题的动态规划算法及具体实现（P121-123），习题6-2

动态规划函数为：

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背包问题的动态规划算法及具体实现（P123-126），习题6-3

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

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