贪心算法概念

前言

一种在问题求解过程中总是做出当前看来最优选择的策略。这个"最优选择"是在某个特定意义上的局部最优解，而不是全局最优解。

贪心算法并非对所有问题都能得到整体最优解，其关键在于贪心策略的选择。所选取的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。

核心要素:

贪心选择

是指通过一系列局部最优的选择，达到问题的整体最优解。这是贪心算法可行的第一个基本要素，也是它与动态规划算法的主要区别。贪心选择采用从顶向下、以迭代的方式做出相继选择，每做一次贪心选择就将所求问题简化为一个规模更小的子问题。

要确定一个具体问题是否具有贪心选择的性质

我们必须证明每一步所作的贪心选择最终能得到问题的最优解。通常可以首先证明问题的一个整体最优解是从贪心选择开始的，而且作了贪心选择后，原问题简化为一个规模更小的类似子问题。然后，用数学归纳法证明，通过每一步贪心选择，最终可得到问题的一个整体最优解。

最优子结构

是指一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。