Part 2.5 贪心

· · 算法·理论 

贪心，指的是决策时都采取当前最优解的算法
有的时候，这样做确实可以获得最优解。

思想：局部最优得到整体最优

它在每一步选择局部最优解，希望通过一系列局部最优解的组合来达到全局最优解。贪心算法不像动态规划那样需要考虑所有可能的情况，而是通过每一步的选择来逐步构建解决方案。

使用条件

  1. 贪心选择性质： 在每一步都做出一个局部最优选择，希望通过一系列局部最优选择达到全局最优解。这意味着问题的最优解可以通过一系列局部最优解来构建。

  2. 最优子结构： 问题的最优解包含了子问题的最优解。这意味着可以通过解决子问题来构建原问题的解。每一步贪心选择都应该不依赖于其他尚未做出的选择，而只依赖于已经做出的选择。

  3. 无后效性： 一旦做出了某个选择，它不会影响到以后的选择。换句话说，选择一旦做出，就不会因为未来的选择而改变。

  4. 子问题重叠性： 与动态规划类似，贪心算法在求解问题时，子问题之间应当有重叠的性质，使得在解决子问题时能够利用之前计算得到的结果。

注意：

  1. 贪心多与数论、博弈论结合，证明贪心的正确性与可行性

  2. 贪心多与排序结合

补充：

博弈论

典例：P1199 [NOIP2010 普及组] 三国游戏

  1. 人机对抗，人大多数（基本）会赢

  2. 不要去模拟过程，想办法分析获胜的方式

  3. 思考机器人策略，想出对应策略