归本程子末军 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张货币
归东程子太深 SHANDONG UNIVERSITY OF TECINOLOGY 华容约深完是红器分深是容 假设有面值为1分、5分、1角1分的货 币，需要找给顾客1角5分现金， 仍按贪心算法如何？ 2025年4月3日
2025年4月3日 6 假设有面值为1分、5分、1角1分的货 币，需要找给顾客1角5分现金， 仍按贪心算法如何？
归东程子太军 1.2贪心算法的基本要素 SHANDONG UNIVERSITY OF TECHNOLOGY ●贪心选择性质 ■所谓贪心选择性质是指所求问题的整体最优解可 以通过一系列局部最优的选择，即贪心选择来达 到。 ■对于一个具体问题，要确定它是否具有贪心选择 性质，必须证明每一步所作的贪心选择最终导致 问题的整体最优解。 ●最优子结构性质 ■当一个问题的最优解包含其子问题的最优解时， 称此问题具有最优子结构性质。 2025年4月3日 7
2025年4月3日 7 1.2 贪心算法的基本要素 ⚫贪心选择性质 ◼所谓贪心选择性质是指所求问题的整体最优解可 以通过一系列局部最优的选择，即贪心选择来达 到。 ◼对于一个具体问题，要确定它是否具有贪心选择 性质，必须证明每一步所作的贪心选择最终导致 问题的整体最优解。 ⚫最优子结构性质 ◼当一个问题的最优解包含其子问题的最优解时， 称此问题具有最优子结构性质
山东程子太军 13贪心算法正确性证明方法 SHANDONG UNIVERSITY OF TECINOLOGY 会是33☆ ●证明算法所求解的问题具有贪心选择性； ●证明算法所求解的问题具有最优子结构； ●证明算法确实按照贪心选择性进行局部优化选 择。 2025年4月3日
2025年4月3日 8 1.3 贪心算法正确性证明方法 ⚫ 证明算法所求解的问题具有贪心选择性； ⚫ 证明算法所求解的问题具有最优子结构； ⚫ 证明算法确实按照贪心选择性进行局部优化选 择
归东置子太军 14动态规划与贪心算法的比较 SHANDONG UNIVERSITY OF TECHNOLOGY 华器会空空合安会器空会的会路 ●相同点： ■都具有最优子结构性质。 ●不同，点： ■贪心算法具有贪心选择性质； ■动态规划算法具有子问题重叠性，子问题空间小； ■动态规划算法通常以自底向上的方式解各子问题； ■贪心算法则通常以自顶向下的方式进行，以迭代的方式作出 相继的贪心选择，每作一次贪心选择就将所求问题简化为规 模更小的子问题。 ●可用贪心算法时，动态规划方法可能不适用； ●可用动态规划方法时，贪心算法可能不适用。 2025年4月3日 9
2025年4月3日 9 1.4 动态规划与贪心算法的比较 ⚫ 相同点： ◼ 都具有最优子结构性质。 ⚫ 不同点： ◼ 贪心算法具有贪心选择性质； ◼ 动态规划算法具有子问题重叠性，子问题空间小； ◼ 动态规划算法通常以自底向上的方式解各子问题； ◼ 贪心算法则通常以自顶向下的方式进行，以迭代的方式作出 相继的贪心选择，每作一次贪心选择就将所求问题简化为规 模更小的子问题。 ⚫ 可用贪心算法时，动态规划方法可能不适用； ⚫ 可用动态规划方法时，贪心算法可能不适用
归本程子末军 1.50-1背包问题和背包问题 HANDONG UNIVERSITY OF TECINOLOGY 3会空会点会.3会条 ●0-1背包问题： ■给定n种物品和一个背包。物品的重量是W,价值为 V,背包容量为C。应如何选择装入背包的物品，使 得装入背包中物品的总价值最大？ ■在选择装入背包的物品时，对每种物品只有2种选择， 即装入或不装入。 ●背包问题： ■与0-1背包问题类似，所不同的是在选择物品装入背 包时，可以选择物品的一部分，而不一定要全部装 入背包，1i≤n。 2025年4月3日 10
2025年4月3日 10 1.5 0-1背包问题和背包问题 ⚫ 0-1背包问题： ◼ 给定n种物品和一个背包。物品i的重量是Wi，价值为 Vi，背包容量为C。应如何选择装入背包的物品，使 得装入背包中物品的总价值最大? ◼ 在选择装入背包的物品时，对每种物品i只有2种选择， 即装入或不装入。 ⚫ 背包问题： ◼ 与0-1背包问题类似，所不同的是在选择物品i装入背 包时，可以选择物品i的一部分，而不一定要全部装 入背包，1≤i≤n