c++贪心算法进阶（一）

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。

贪心算法的基本思路是从问题的某一个初始解出发一步一步地进行，根据某个优化测度，每一步都要确保能获得局部最优解。每一步只考虑一个数据，他的选取应该满足局部优化的条件。若下一个数据和部分最优解连在一起不再是可行解时，就不把该数据添加到部分解中，直到把所有数据枚举完，或者不能再添加算法停止。

排序：

贪心算法解决的是最优值的问题（即求最大值或最小值一类的问题），因此，在求解局部最优解时，一般需要对数据进行从小到大（或者从大到小）进行排序后再根据顺序依次选择做出局部最优选择。所以，很多的贪心题目，都需要对数据进行排序。

无后效性：

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

最优子结构：

当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。运用贪心策略在每一次转化时都取得了最优解。问题的最优子结构性质是该问题可用贪心算法或动态规划算法求解的关键特征。贪心算法的每一次操作都对结果产生直接影响，而动态规划则不是。贪心算法对每个子问题的解决方案都做出选择，不能回退；动态规划则会根据以前的选择结果对当前进行选择，有回退功能。动态规划主要运用于二维或三维问题，而贪心一般是一维问题。

贪心算法的优缺点：

贪心算法是很常见的算法之一，贪心策略一旦经过证明成立后，它就是一种高效的算法。一般可以达到O(n)或者O（nlg(n)) (用到排序的话）的级别。

贪心算法的难点在于：你需要证明贪心策略的正确性后才能真正运用到题目的算法中。

在解决最优值的一类问题时，如果你实在想不出正解，用用贪心有时也是可以拿到部分分的，在比赛里算是骗分算法之一。

贪心算法没有固定的算法框架，基本靠自己的做题经验和题目分析能力，所以这个算法需要多做题，积累经验。

这个算法需要你自力更生了。