第4章：贪心算法 (Greedy Algorithm)
第4章：贪心算法 （Greedy Algorithm）
知识要点 ⑧理解贪心算法的概念和基本要素 Φ最优子结构性质和贪心选择性质 Φ理解贪心算法与动态规划算法的差异 3贪心设计策略的典型例子 Φ活动安排问题 Φ最优装载问题 Φ单源最短路径 Φ多机调度问题
知识要点 理解贪心算法的概念和基本要素 最优子结构性质和贪心选择性质 理解贪心算法与动态规划算法的差异 贪心设计策略的典型例子 活动安排问题 最优装载问题 单源最短路径 多机调度问题
贪心算法的例子 @3 找零钱问题 假设有4种硬币，面值分别为：二角五分、一角、五分和一分 现在要找给顾客六角三分钱，如何找使得给出的硬币个数最少？ @3 问题的求解 Φ正解：选择2个两角五分的硬币、1个一角的硬币、3个一分的 硬币。和其它找法相比，所拿出的硬币个数最少。 Φ求解过程 首先选出1个面值不超过六角三分的最大硬币，即两角五分 然后从六角三分中减去两角五分，剩下三角八分 再选出1个面值不超过三角八分的最大硬币 即又一个两角五分。如此一直做下去.… 这里用到的方法就是贪心算法
贪心算法的例子 找零钱问题 假设有4种硬币，面值分别为：二角五分、一角、五分和一分 现在要找给顾客六角三分钱，如何找使得给出的硬币个数最少？ 问题的求解 正解：选择2个两角五分的硬币、1个一角的硬币、3个一分的 硬币。和其它找法相比，所拿出的硬币个数最少。 求解过程 • 首先选出1个面值不超过六角三分的最大硬币，即两角五分 • 然后从六角三分中减去两角五分，剩下三角八分 • 再选出1个面值不超过三角八分的最大硬币 • 即又一个两角五分。如此一直做下去…… • 这里用到的方法就是贪心算法
贪心算法的例子 3 找零钱问题 在这个例子中，找硬币算法得到的结果是整体最优解 ·问题本身具有最优子结构性质，可以用动态规划算法求解 Φ用贪心算法更简单、更直接、且解题效率更高分 R 贪心算法不能保证全局最优 找硬币问题和硬币面值的特殊性有关 如果将硬币面值改为：一分、五分和一角一分， 假设要找给顾客的是一角五分 Φ利用贪心算法，将找给顾客1个一角一分的硬币和4个一分硬币 Φ显然，3个五分硬币是最优的解法
贪心算法的例子 找零钱问题 在这个例子中，找硬币算法得到的结果是整体最优解 问题本身具有最优子结构性质，可以用动态规划算法求解 用贪心算法更简单、更直接、且解题效率更高分 贪心算法不能保证全局最优 找硬币问题和硬币面值的特殊性有关 如果将硬币面值改为：一分、五分和一角一分， 假设要找给顾客的是一角五分 利用贪心算法，将找给顾客1个一角一分的硬币和4个一分硬币 显然，3个五分硬币是最优的解法
贪心算法的基本思想 R 贪心算法的基本思想 Φ优化问题的算法往往包含一系列步骤，每一步都有一组选择 Φ贪心算法在每一步选择中都采取在当前状态下最优的选择 目的是希望由此导出的果是最优的 简言之：贪心算法在求解问题时并不着眼于整体最优 它所作出的选择仅仅是当前看来是最优的 Φ贪心算法能否得到整体最优解？…具体问题，具体分析 R 贪心算法在有最优子结构的问题中尤为有效 Φ 最优子结构的意思是：局部最优解能决定全局最优解 。问题能够分解成子问题来解决 子问题的最优解能递推到最终问题的最优解
贪心算法的基本思想 贪心算法的基本思想 优化问题的算法往往包含一系列步骤，每一步都有一组选择 贪心算法在每一步选择中都采取在当前状态下最优的选择 • 目的是希望由此导出的果是最优的 简言之：贪心算法在求解问题时并不着眼于整体最优 • 它所作出的选择仅仅是当前看来是最优的 贪心算法能否得到整体最优解？……具体问题，具体分析 贪心算法在有最优子结构的问题中尤为有效 最优子结构的意思是：局部最优解能决定全局最优解 • 问题能够分解成子问题来解决 • 子问题的最优解能递推到最终问题的最优解