贪心算法

算法导引：

问题：有1元、5元、10元、100元、500元的硬币（假设所有面值硬币都足够）现在要找给顾客620元，最少需要多少枚硬币？（改编自挑战程序设计竞赛）
显然使用一个500的，一个100的，两个20的最优。得出这一结论我们使用了这样的贪心算法，即首先找出一个面值不超过620的最大硬币，即500，然后从620中减去500，剩下120；再选出一个面值不超过120的最大硬币，即100；如此重复，最后的到结果将如上所述。

定义:贪心算法是一种解题的策略，它总是做出在当前看来是最好的选择，（也就是说不从整体最优上考虑，所做出的选择是局部最优选择。）期望通过所做的局部最优选择来产生出一个全局最优解。

算法优点：如果策略正确，贪心算法往往易于描述，易于实践。

算法局限：贪心算法不是对所有问题都能得到整体最优解。

举个例子：上述找硬币的算法利用了硬币面值的特殊性。如果将硬币的面值改为600，310，5（假设所有面值硬币都足够）。还用贪心算法，将得出一个600元，4个5元的硬币，然而两个310元的硬币显然是最好的解答。
{ PS：虽然贪心算法不是对所有问题都能得到整体最优解，但对范围相当广的许多问题它能产生整体最优解。在一些情况下，即使贪心算法不能得到整体最优解，但其最终结果却是最优解的很好的近似解。}

应用条件：（贪心算法基本要素）

1. 贪心选择性质：所求问题的整体最优解可以通过一系列局部最优的选择来达到（与动态规划的区别）。
2. 最优子结构性质：一个问题的最优解包含其子问题的最优解。（可用贪心和动态规划的关键特征）

具体实现：

1. 从最初问题的初始解开始;
2. while(将问题分解){
   求出分解的问题的一个解;
   }
3. 由所有解组合成问题的一个可行的解;

经典例题：

1.最优装载问题：
题目：给出n个物体，第i个物体重量为w_i。选择尽量多的物体，使得总重量不超过C。
显然将物体按重量从小到大排序，依次选择物体直到重量大于C为止即为最优解。

那我们所认为的 “显然” 是正确的吗？贪心选择–重量最轻–总是最优解的一部分吗？
下面将利用数学方法加以证明。
设变量x_i（x_i = 0时表示第i个物体不装入背包，x_i = 1表示第i个物体装入背包），则该问题可以视为：在 Σw_i*x_i <= C 的前提下，使x_i = 1的数量尽可能的多。设物体已按重量从小到大排好序，X = {x_1,x_2,…,x_n}是一个此问题的最优解。设 k 为该解第一个物体的编号。
（1） 当 k == 1 时，X 即是满足贪心选择性质（贪心选择重量最轻的物体）的最优解。
（2） 当 k > 1 时，设Y = {y_1,y_2,…,y_n},其中y_1 = 1;y_k = 0其余y_i == x_i;则Σw_i*y_i = Σw_i*x_i – w_k + w_1;因为 w_k > w_1 所以 Σw_i*y_i < Σw_i*x_i <= C。且 |X| == |Y|（X，Y中元素个数相等），所以Y = {y_1,y_2,…,y_n}也是该问题的可行解。
综上：最优装载问题满足贪心选择性质。
接下来验证该问题具有最优子结构。
设X = {x_1,x_2,…,x_n}是一个此问题的最优解。则X~ = {x_2,x_3,…,x_n}是给出n-1个物体，第i个物体重量为w_i。选择尽量多的物体，使得总重量不超过C-w_1问题的最优解.
为什么呢？可以这样假设，设存在 Y~ 且 |Y~| > |X~|（即Y~中活动个数多于X~）则有 |X~ + {1}| < |Y~ + {1}| ，与X是最优解矛盾。因此每一步所做的贪心选择都将问题简化为一个更小的与原问题具有相同形式的子问题。即最优装载问题具有最优子结构。

代码：

//算法时间复杂度O（n）
void loading(int n,int w[],int c,int x[]){
    for(int i=0;i<n;i++) x[i] = 0;
    for(int i=0;i<n && w[i]<=c;i++){
        x[i] = 1;
        c -= w[i];
    }
}

2.区间问题
a)选择不相交区间（活动安排问题）
例：有 n 个活动，每个活动都要求使用同一资源。而在同一时间内只有一个活动能使用这一资源。求最多能有多少活动使用资源。
分析：根据题意，应该选择这样的活动，选出它后剩下的资源应能被尽量多的其他活动所利用。那么考虑可选的活动，其中必然有一个最先结束，结束的时间越早，剩下的时间也就越多，可选的工作也就越多。所以，应该选择最早结束的活动（如果最早结束的活动有多个，任选一个即可）。
解：按照结束时间从小到大的顺序给区间排序，每次按照排好的顺序选取第一个与之前所选活动相容的活动，那么这样的贪心策略就一定要选择第一个活动（选择最早结束的活动不是本题唯一的解法）。{PS：说明：由于活动已经按结束时间单调递增排序，所以贪心选择就是活动1。做出贪心选择后，剩下的问题就是寻找在活动1结束后开始的活动。}

先证活动安排问题具有最优子结构
设S[i,j]是活动a[i]到活动a[j]的集合，A[i,j]是S[i,j]的一个最大的相互兼容的活动的子集，包含活动a[k]，这样就得到了两个子问题：寻找s[i,k]及S[k,j]中的兼容活动。令：A[i,k] = S[i,k] ∩ A[i,j] ， A[k,j] = S[k,j] ∩ A[i,j] ，则 A[i,j] = A[i,k] ∪ a[k] ∪ A[k,j],且 |A[i,j]| = |A[i,k]| + 1 + |A[k,j]|。（反证法）假设可以找到S[i,k]的一个兼容活动子集B[i,k]，满足|B[i,k]| > |A[i,k]|，那么将得到 |B[i,k]| + 1 + |A[k,j]| > |A[i,k]| + 1 + |A[k,j]| = A[i,j]，这与A[i,j]是最优解的假设矛盾。所以活动安排问题具有最优子结构。
下面将用数学方法证明上述贪心选择–最早结束的活动–总是最优解的一部分
设非空子问题 S[K]，令 a_m是S[k]中结束时间最早的活动，令A[k]是S[k]的一个最大兼容活动子集且a_j是A[k]中结束时间最早的活动，令B[k] = A[k] - {a_j} ∪ {a_m}（B集合即A集合减去a_j活动加上a_m活动）。因为A集合中活动相容，且f_m < f_j（a_m的结束时间小于a_j的结束时间），所以B集合相容。又因为|A[k]| == |B[k]| ，因此B[k]也是S[k]的一个最大兼容活动子集（B中包含S[k]中结束时间最早的活动a_m）。即活动安排问题满足贪心选择性质。

代码：

//算法时间复杂度O（n）
struct act{
    int s,f;
    bool operator < (const act& other)const{
        return ((f<other.f) || (!(other.f<f)) && (s>other.s));
    }
};

void greedy_select(int n,act sf[],bool A[]){
    A[0] = true;
    int j = 0;
    for(int i=1;i<n;i++){
        if(sf[i].s > sf[j].f) {
            A[i] = true;
            j = i;
        }
        else A[i] = false;
    }
}

例题：HDU - 2037
标准活动安排问题，思路如上所述。我用的pair，排序时pair会按照第一个关键字排序，本题恰好只有两个变量，使用pair省去了写结构体和重载的麻烦。

#include<bits/stdc++.h>

using namespace std;
//贪心：选择不相交区间
int main(int argc, char const *argv[])
{
    int n;
    while(cin>>n && n){
        pair<int ,int > se[200];
        for (int i = 1; i <= n; ++i)
            cin>>se[i].second>>se[i].first;
        sort(se,se+n+1);
        int j = 1 ,cnt = 1;
        for(int i = 2;i <= n; i++){
            if(se[i].second >= se[j].first){
                j = i;
                cnt++;
            }
        }
        cout<<cnt<<endl;
    }
    return 0;
}

b) 区间选点：
例：有n个闭区间[a_i,b_i]，取尽量少的点，使得每个区间都至少有一个点。
分析：
待续……