活动选择问题

• 最优子结构

• 贪心选择： 反复选择最早结束的活动，保留与此活动兼容的活动，重复这一过程，直至不再有剩余活动

• 递归贪心算法

• 迭代贪心算法

贪心算法原理

• 设计贪心算法

  • 将最优化问题转化为这样的形式： 对其做出一次选择后，只剩下一个子问题需要求解
  • 证明做出贪心选择后，原问题总是存在最优解，即贪心选择总是安全的
  • 证明做出贪心选择后，剩余的子问题满足性质：其最优解与贪心选择组合即可得到原问题的最优解，这样就得到了最优子结构

• 应用贪心算法的关键要素

  • 贪心选择性质：我们可以通过做出局部最优（贪心）选择来构造全局最优解

    • 在贪心算法中，我们总是做出当时看来最佳的选择，然后求解剩下的唯一的子问题。
    • 贪心算法进行选择时可能依赖之前做出的选择，但不依赖任何将来的选择或是子问题的解。
    • 与动态规划先求解子问题才能进行第一次选择不同，贪心算法在进行第一次选择之前不求解任何子问题。
    • 一个动态规划算法是自底向上进行计算的，而一个贪心算法通常是自顶向下的，进行一次又一次选择，将给定问题实例变得更小
    • 如果进行贪心选择时我们不得不考虑众多选择，通常意味着可以改进贪心选择，使其更为高效
    • 如：在活动选择问题中，假定我们已经将活动按结束活动时间单调递增顺序排好序，则对每个活动能够只需处理一次。
    • 通过对输入进行预处理或者使用合适的数据结构（通常是优先队列），我们通常可以使贪心选择更迅速，从而得到更高效的算法

  • 最优子结构：一个问题的最优解包含其子问题的最优解

• 贪心对动态规划
  • 0-1背包问题：

拟阵和贪心算法

拟阵：




加权拟阵上的贪心算法