贪心算法总结
发布时间
阅读量：
阅读量
一、概述
贪心算法属于一种较为基础的算法类型，在每一阶段都会采取最优策略以实现整体最佳效果。为了使这种策略能够奏效，则需要确保全局最优点可以通过一系列局部最优点的选择得以实现。若希望应用贪心算法解决具体问题，则必须满足该问题具有最优子结构性质以及可分解出明确的贪心选择性质这两个必要条件；而这一原则的核心在于确定合适的贪心策略以实现目标
贪心算法也存在如下问题：
1、不能保证解是最佳的。因为贪心算法总是从局部出发，并没从整体考虑 ；
2、贪心算法一般用来解决求最大或最小解 ；
3、贪心算法只能确定某些问题的可行性范围
二、两大基本要素
1.贪心选择性质
这种性质指的是在求解某类问题时整体达到最佳状态的方法，并且可以通过一系列局部最优的选择逐步实现这一目标。在这种方法中仅关注当前阶段的最优化决策，并不依赖于后续可能做出的任何选择或决策结果。因此这种策略的思想较为容易被理解，并且通常采用自上而下的解决问题的方式，在每一次决策中都采取当前看来最合理的选项，并将问题逐步分解为更小规模的问题来处理。
2.最优子结构性质
即当一个问题的最佳解决方案包含了其子问题的最佳解决方案，则称该问题具有最佳子结构特性。
三、经典贪心问题
1.会场安排问题
题目描述
为了解决如何在大量可用场地中合理安排一批活动并最大限度地减少占用场地的需求，请开发一个高效的贪心算法用于时间表规划。针对k个待排事件组的时间表问题，请计算所需最少场地数量及其对应的时间段分配方案。
输入
第1行为一个正整数k（单位：分钟），它表明随后将要被安排的工作数量为k项。接下来的每一行为两个具体的正整数值（单位：分钟），它们分别对应着每个需要被安排的工作的具体起始时间和结束时间。
输出
将计算出的最少会场数输出到。
样例输入
5
1 23
12 28
25 35
27 80
36 50
样例输出 ：
3
- 背包问题
- 哈夫曼编码
- 多机调度
全部评论 (0)
还没有任何评论哟~