《贪心算法》课件

《贪心算法》课件PPT欢迎大家来到《贪心算法》的课件在本次课程中，我们将探索算法和PPT贪心算法的概述，并深入了解贪心算法的定义、原理、特点以及应用场景算法和贪心算法的概述算法是解决问题的步骤和规则的集合贪心算法是一种将每一步操作中所做的最优选择合并起来，来解决整个问题的算法贪心算法定义及原理贪心算法是一种每次都做出当前看起来最佳选择的算法它基于局部最优解，并希望通过一系列局部最优解来达到全局最优解贪心算法的特点贪心选择性无后效性子问题最优解123每一步都采取当前最优的当前的选择不会影响以后通过求解子问题的最优解选择的选择来构建全局最优解贪心算法的应用场景霍夫曼编码最小生成树最短路径用较少的编码长度来代表出在给定的图上找到一棵包含找到两个顶点之间的最短路现频率较高的字符了所有顶点且边权值最小的径树贪心算法与动态规划的比较贪心算法和动态规划都是解决最优化问题的方法，但贪心算法一般只考虑局部最优解，而动态规划则利用全局最优解来求解贪心算法的优缺点优点缺点简单易实现并不一定能得到全局最优解••在某些问题上能够获得最优解对问题的要求较高••计算效率高局部最优解不能导致最终最优解••贪心算法的案例分析活动选择问题1选择最多的相互兼容活动硬币找零问题2给定一些硬币面额，求找零时所需的最少硬币数区间调度问题3找到最多的不重叠区间。