常用算法笔记 > 贪心算法
贪心算法思想

贪心算法是就问题而言,选择当下最好的选择,而不从整体最优考虑,通过局部最优希望导致全局最优。

贪心算法的要素

1)贪心选择性质:可以通过局部最优选择来构造全局最优解。换言之,直接做出在当前问题中看来最优的选择,而不必考虑子问题的解。

2)最优子结构:一个问题的最优解包含其子问题的最优解。

贪心算法的设计步骤:

1)将最优化问题转换为这样的形式:对其做出一次选择后,只剩下一个子问题需要求解

2)证明做出贪心选择后,原问题总是存在最优解,即贪心选择总是安全的

3)证明做出贪心选择后,剩余的子问题满足性质:其最优解与贪心选择组合即可得到原问题的最优解,这样就得到了最优子结构。

示例:背包问题,均分纸牌,最大整数