算法设计与分析　.ppt

算法设计与分析;第四章 贪心算法;引言;4.1 活动安排问题;贪心算法描述;复杂性分析;一个实例;图示;说明;4.2 贪心算法的基本要素;1.贪心选择性质;2.最优子结构性质;3.贪心算法与动态规划算法的差异;0-1背包问题与背包问题;用贪心算法解背包问题的基本步骤;对于0-1背包问题，贪心选择之所以不能得到最优解是因为在这种情况下，它无法保证最终能将背包装满，部分闲置的背包空间使每公斤背包空间的价值降低了。事实上，在考虑0-1背包问题时，应比较选择该物品和不选择该物品所导致的最终方案，然后再作出最好选择。由此就导出许多互相重叠的子问题。这正是该问题可用动态规划算法求解的另一重要特征。 实际上也是如此，动态规划算法的确可以有效地解0-1背包问题。;4.3 最优装载;1.算法描述;算法分析;4.4 哈夫曼编码;1.前缀码;2.构造哈夫曼编码;算法说明;3.哈夫曼算法的正确性;4.5 单源最短路径;1、算法基本思想;一个实例;2、算法的正确性和计算复杂性;4.6 最小生成树;1、最小生成树性质;2、Prim算法;算法改进;3、Kruskal算法;说明;4.7 多机调度问题;一个实例;4.8 贪心算法的理论基础