Lesson9：贪心法

优化问题：围绕目标函数展开，希望在有限的解空间中找到能够达到最优值的一组解。

贪心算法：在某些情况下，可能与很多的元素有关，那么我们依次解出这些元素的best stage，组合实现最优解。

原话：

优化问题：给定一组约束和一个优化函数，满足约束的解决方案称为可行解决方案。使优化函数具有最佳可能值的可行解称为最优解。

贪心法：在贪心准则下，在每个阶段做出最佳决策。在一个阶段做出的决定不会在以后的阶段改变，所以每个决定都应该确保可行性。

这里的阶段其实意义就是所谓的元素，有点类似分而治之。

Note

贪心算法只有在局部最优(的和)等于全局最优时才有效。贪心算法不能保证最优解。然而，它通常产生的解在值（启发式）上非常接近最优解，因此在寻找最优解需要花费太多时间时，它在直觉上很有吸引力。