首选理解一下贪心问题：贪心问题是一种从局部最优得到全局最优的问题，意思是立足于一点，从这点出发开始想最优解，一步步得出最终解。
通过上面口语化的描述，可见一个贪心问题对关键就是如何立足于一点寻找最优解，这里的关键就是最优解的度量方法。
下面是一个贪心问题的通用流程：
proceduce Greedy(A,n){//A中包含n个输入
解向量solution初始为空
从1到n
按照最优度量选出A中一个输入x //**最优度量**
如果可以加入solution则加入 //**如何判断**
重复上述过程
返回解向量结果
由上可见，如果把握好最优度量标准和判断条件，那么问题也就基本解决了，下面来看实战:
1.基础简单贪心问题
背包问题： 已知n种物品和一个可以容纳重量为M的背包，物品重量收益用wi和pi表示，试求怎样将物品放入背包总收益最大。
分析：很显然这个问题很容易让我们想到买商品时的单价，如果用wi/pi表示单位收益再非增排序，依次选取放入背包即可。 其中wi/pi就是度量标准，判断条件只要重量和小于M就可以继续加入，直到相等。
2.区间贪心问题
看电视 ：
暑假到了，小明终于可以开心的看电视了。但是小明喜欢的节目太多了，他希望尽量多的看到完整的节目。
现在他把他喜欢的电视节目的转播时间表给你，你能帮他合理安排吗？
输入
输入包含多组测试数据。每组输入的第一行是一个整数n（n<=100），表示小明喜欢的节目的总数。
接下来n行，每行输入两个整数si和ei（1<=i<=n），表示第i个节目的开始和结束时间，为了简化问题，每个时间都用一个正整数表示。
当n=0时，输入结束。
输出
对于每组输入，输出能完整看到的电视节目的个数。
分析：上面的问题明显相当于给定一堆（a，b）的区间，叫我们挑选出不相交的最多区间数，这就是典型的区间贪心问题。首先如果两个区间大包小，我们肯定选择小的那个；如果两个区间相交，是不是可以把其中一个区间视为两部分，一部分是单独的，另一个部分是相交部分，单独的部分不影响，相交部分又转化为大包小问题，大包小取小，实质就取了被划分的那个区间。
根据上述思路，我们可以从左端点开始，也可以从右端点开始选取，然后贯彻上面那个思路收集符合条件的区间。
#include<algorithm> using namespace std; const int maxn=100; int n=1,sum; struct tv{ int a,b; bool operator<(const tv &c)const{ if(c.b==b)return a>c.a; return b<c.b; } }T[100]; int main(){ while(scanf("%d",&n),n!=0){ sum=1; for(int i=0;i<n;i++){ scanf("%d %d",&T[i].a,&T[i].b); } sort(T,T+n); //从右端点开始，从小到大排序 int tag=0; for(int j=1;j<n;j++){ if(T[tag].b<=T[j].a){ //找不相交点（主要有相交就取前一个） sum++; tag=j; } } printf("%d\n",sum); } return 0; }
此外这个问题还有一些变种，值得注意，如区间选点问题，区间覆盖问题。
3.综合应用
汽车加油问题： 你要从杭州开车到目的地，整条路线是一个数轴，你在数轴上的0点，目的地在距离0点为D米，你的车油罐的容量为C，每单位油可以行驶Davg 米，在路线上有n个加油站，每个加油站在位置为di处，单价是pi， 问你，从0点出发开到目的地所需要的最小花费是多少，若开不到目的地，输出最远可以到达的地方，油箱一开始为空。
分析：该问题的起点就在原点，如果此处没有加油站，肯定无法到达，如果有，立足于此加油站则思考下一个问题
如果能找满油最大行程到距离该加油站最近的价格更低的加油站，只加够到那里的油
如果没有则找最大行程内价格最低的油加满油到那
如果一个最大行程里没有加油站，凉凉，无法到达
#include<iostream> #include<algorithm> using namespace std; const int maxn=501; struct station{ double d,p; bool operator<(const station &a)const{ if(a.d==d)return p<a.p; return d<a.d; } }T[maxn]; int n; double D,Davg,C,M,sum=0; int main(){ scanf("%lf%lf%lf%d",&C,&D,&Davg,&n); for(int i=0;i<n;i++){ scanf("%lf%lf",&T[i].p,&T[i].d);} sort(T,T+n); // 输入加油站并按距离出发点从小到大排序 M=C*Davg; if(T[0].d!=0) // 如果出发点没有加油站 printf("The maximum travel distance = %.2f",0.00); else{ double nowtank,need,minprice; int now=0,then,flag=0; T[n].d=D;T[n].p=0; while(now<n){ then=-1; minprice=T[now+1].p; for(int i=now+1;(T[i].d-T[now].p)<=M&&i<=n;i++) { if(T[i].p<=minprice){ then=i; minprice=T[i].p;} if(T[i].p<T[now].p) break; } if(then==-1) break; //第三种情况处理 need=(T[then].d-T[now].d)/Davg; if(minprice<T[now].p){ //第一种情况处理 if(need<=nowtank) nowtank-=need; else{ sum+=(need-nowtank)*T[now].p; nowtank=0; } } else{ //第二种情况处理 sum+=(C-nowtank)*T[now].p; nowtank=C-need; } now=then;flag=0; } if(now==n) printf("%.2f\n",sum); else printf("The maximum travel distance = %.2f",T[now].d+M); } return 0; }
