算法设计和分析教学资料第4章.ppt

第4章 贪心算法;理解贪心算法的概念 掌握贪心算法的基本要素 1最优子结构性质 2贪心选择性质 理解贪心算法与动态规划算法的差异 理解贪心算法的一般理论;通过应用范例学习贪心设计策略 1活动安排问题 2最优装载问题 3哈夫曼编码 4单源最短路径 5最小生成树 6多机调度问题;问题描述 有位顾客买了两斤苹果需付3元7角实付10元你需找零6元3角假设你抽屉里有一些硬币面值分别为2元5角1元5角和1角现