1)先定义数据结构:以时间为核心,定义对象T,拥有t与f两个属性,其中t是时间,f代表是活动开始还是结束。
•第i阶段的“部”:问题空间为按照贪心策略中的优先级排好序的第i个输入ai •第i阶段的“部最优解”: ai •贪心选择性质:所求问题的全最优解可以通过一系列部最优的选择(即贪心选择)来达到。 –这是贪心算法与动态规划算法的主要区别。
贪心算法经典例子如下:活动安排问题是可以用贪心算法有效求解的一个很好的例子,该问题要求高效地安排一系列争用某一公共资源的活动。 贪心算法提供了一个简单、漂亮的方法使得尽可能多的活动能兼容地使用公共资源。
上一篇:贪心算法和动态规划使用场景
下一篇:贪心算法通用模板