归本程子末军 HANDONG UNIVERSITY OF TECINOLOGY 计算机算法设计与分析 Design and Analysis of Computer Algorithms 第四章贪心算法 Greedy Algorithm 王红震 理学院
计算机算法设计与分析 Design and Analysis of Computer Algorithms 第四章 贪心算法 Greedy Algorithm 王红霞 理学院
归求程上太军 提纲 SHANDONG UNIVERSITY OF TECINOLOGY 会A会学3会是3会 一、 贪心算法的基本思想 二、活动安排问题 三、最优装载 四、哈夫曼编码 五、单源最短路径 六、最小生成树 七、多机调度问题 2025年4月3日 2
2025年4月3日 2 提纲 一、贪心算法的基本思想 二、活动安排问题 三、最优装载 四、哈夫曼编码 五、单源最短路径 六、最小生成树 七、多机调度问题
G 归本程子末军 提纲 SHANDONG UNIVERSITY OF TECHNOLOGY 一、 贪心算法的基本思想 二、活动安排问题 三、最优装载 四、哈夫曼编码 五、单源最短路径 六、最小生成树 七、多机调度问题 2025年4月3日 3
2025年4月3日 3 提纲 一、贪心算法的基本思想 二、活动安排问题 三、最优装载 四、哈夫曼编码 五、单源最短路径 六、最小生成树 七、多机调度问题
白东程子太军 1.1贪心算法总体思想 HANDONG UNIVERSITY OF TECINOLOGY 贪心算法总是作出在当前看来最好的选择。也 就是说贪心算法并不从整体最优考虑，它所作出 的选择只是在某种意义上的局部最优选择。贪心 法在解决问题的策略上目光短浅，只根据当前已 有的信息就做出选择，而且一旦做出了选择，不 管将来有什么结果，这个选择都不会改变。 这种局部最优选择并不总能获得整体最优解 (Optimal Solution),但通常能获得近似最优 解(Near-Optimal Solution)。 2025年4月3日 A
2025年4月3日 4 1.1 贪心算法总体思想 贪心算法总是作出在当前看来最好的选择。也 就是说贪心算法并不从整体最优考虑，它所作出 的选择只是在某种意义上的局部最优选择。贪心 法在解决问题的策略上目光短浅，只根据当前已 有的信息就做出选择，而且一旦做出了选择，不 管将来有什么结果，这个选择都不会改变。 这种局部最优选择并不总能获得整体最优解 （Optimal Solution），但通常能获得近似最优 解（Near-Optimal Solution）
归本程上太军 1.1贪心算法总体思想 SHANDONG UNIVERSITY OF TECINOLOGY 例：用贪心法求解付款问题。 假设有面值为5元、2元、1元、5角、2角、1角的货币， 需要找给顾客4元6角现金，为使付出的货币的数量最 少，首先选出1张面值不超过4元6角的最大面值的货币， 即2元，再选出1张面值不超过2元6角的最大面值的货 币，即2元，再选出1张面值不超过6角的最大面值的货 币，即5角，再选出1张面值不超过1角的最大面值的货 币，即1角，总共付出4张货币。 2025年4月3日 5
2025年4月3日 5 1.1 贪心算法总体思想 例：用贪心法求解付款问题。 假设有面值为5元、2元、1元、5角、2角、1角的货币， 需要找给顾客4元6角现金，为使付出的货币的数量最 少，首先选出1张面值不超过4元6角的最大面值的货币， 即2元，再选出1张面值不超过2元6角的最大面值的货 币，即2元，再选出1张面值不超过6角的最大面值的货 币，即5角，再选出1张面值不超过1角的最大面值的货 币，即1角，总共付出4张货币