【算法】贪心算法

贪心算法（greedy algorithm），又称贪婪算法，是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法。

1. 算法思想

贪心算法是一种遵循某种规则，不断贪心地选取当前最优策略的算法设计方法。也就是说，不从整体最优上加以考虑，它所做出的是在某种意义上的局部最优解。

算法特点

相对于动态规划来说，贪心算法是十分简单高效的。

贪心算法和动态规划本质上是对子问题树的一种修剪，两种算法要求问题都具有的一个性质就是子问题最优性(组成最优解的每一个子问题的解，对于这个子问题本身肯定也是最优的)。
动态规划方法代表了这一类问题的一般解法，我们自底向上构造子问题的解，对每一个子树的根，求出下面每一个叶子的值，并且以其中的最优值作为自身的值，其它的值舍弃。
而贪心算法是动态规划方法的一个特例，可以证明每一个子树的根的值不取决于下面叶子的值，而只取决于当前问题的状况。换句话说，不需要知道一个节点所有子树的情况，就可以求出这个节点的值。由于贪心算法的这个特性，它对解空间树的遍历不需要自底向上，而只需要自根开始，选择最优的路，一直走到底就可以了。

3. 算法实现

3.1 基本思路

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

过程如下

建立数学模型来描述问题；
把求解的问题分成若干个子问题；
对每一子问题求解，得到子问题的局部最优解；
把子问题的解局部最优解合成原来解问题的一个解。

3.2 判断是否可以使用

我们能够依据贪心法的2个重要的性质去判断一道题是否可以贪心：贪心选择性质和最优子结构性质。

3.2.1 贪心选择　　

什么叫贪心选择？从字义上就是贪心，也就是目光短线，贪图眼前利益。在算法中就是仅仅依据当前已有的信息就做出选择，并且以后都不会改变这次选择。（这是和动态规划法的主要差别）
所以对于一个详细问题。要确定它是否具有贪心选择性质，必须证明每做一步贪心选择是否终于导致问题的总体最优解。

3.2.2 最优子结构

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

3.3 一般求解过程　　

使用贪心法求解能够依据下面几个方面进行（也相应着每步代码的实现），以找零钱为例：　　

3.3.1 候选集合(C)　　　　

通过一个候选集合C作为问题的可能解。（终于解均取自于候选集合C）　　　　
比如。在找零钱问题中，各种面值的货币构成候选集合。　　

3.3.2 解集合(S)　　　　

每完毕一次贪心选择，将一个解放入S。终于获得一个完整解S　　

3.3.3 解决函数(solution)　　　　

检查解集合S是否构成问题的完整解。　　　　
比如，在找零钱问题中。解决函数是已付出的货币金额恰好等于应付款。　　

3.3.4 选择函数(select)　　　　

即贪心策略。这是贪心法的关键，选择出最有希望构成问题的解的对象。（这个选择函数通常和目标函数有关）　　
比如，在找零钱问题中，贪心策略就是在候选集合中选择面值最大的货币。　　

3.3.5、判断函数(feasible)　　　　

检查解集合中增加一个候选对象是否可行。（增加下一个对象后是不是满足约束条件）　　　
比如。在找零钱问题中，可行函数是每一步选择的货币和已付出的货币相加不超过应付款。

4. 实例分析

4.1 合并果子

这道题很简单，一看就是贪心。每次将最小的果子堆合并就好了。

这里可以用最小堆来写。由于这题是我很久之前写的，那时并不会最小堆，所以我的代码就不放了。贪心的规则已经给出了，可以试着写一下。

4.2 线段覆盖

这道题也是属于贪心算法。根据题意很容易得到三种规则：

以开始时间贪心
以持续时间贪心
以结束时间贪心

仔细分析，前两种都可以很容易举出反例。所以按照第三种规则来贪心。

AC代码：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef pair<int, int> P;

bool cmp(P a, P b)
{
    if (a.second != b.second)
        return a.second < b.second;

    return a.first < b.first;
}

int main()
{
    int n;

    cin >> n;

    vector<P> time(n);

    for (int i = 0; i < n; i++)
        cin >> time[i].first >> time[i].second;

    sort(time.begin(), time.end(), cmp);

    int cnt = 1, end = time[0].second;

    for (int i = 1; i < n; i++)
    {
        if (time[i].first >= end)
        {
            cnt++;
            end = time[i].second;
        }
    }

    cout << cnt << endl;

    //system("pause");

    return 0;
}