1.介绍
贪心（Greedy）的算法思想：把整个问题分解成多个步骤，在每个步骤都选取当前步骤的最优方案，直到所有步骤结束；在每一步都不考虑对后序步骤的影响，在后序步骤中也不再回头改变前面的选择。
简单地说，算法思想即“走一步看一步”目光短浅，因为往往局部的最优组合不一定是全局最优的，
2.例题
例1：
Description
最少硬币问题：某人带着3种面值的硬币去购物，有1元、2元、5元的，硬币数量不限；他需要支付M元，问怎么支付才能使硬币数量最少？
思路：根据常识，一般先拿出面值最大的，即5元，再拿出第二大的2元，最后才拿面值最小的1元。这个方案中硬币总数是最少的。
#include<bits/stdc++.h> using namespace std; const int NUM = 3; const int Value[NUM] = {1,2,5}; int main(){ int i,money; int ans[NUM] = {0}; //记录每种硬币数量 cin >> money; //输入钱数 for(i= NUM-1 ;i>=0 ;i--){ //求每种硬币数量 ans[i] = money/Value[i]; money = money - ans[i]*Value[i]; } for(i = NUM-1 ;i>=0 ;i--) cout <<Value[i] <<"元硬币数：" << ans[i] <<endl; return 0; }
这一例题中，用局部最优的方法得到的结果是全局最优，然而局部最优不一定总是全局最优，用贪心法一定能得到最优解吗？
我们稍微改一下参数，就不一定能得到最优解，甚至无法算出答案
（1）不能得到最优解情形：例如硬币面值为{ 1,2,4,5,6,}元，支付9元，用贪心算法得到答案是6+2+1（读者可以把程序改一下试试），需要3个硬币，而最优情况为 5+4，即两个硬币
（2）算不出答案情形：在没有1元硬币时，常常得不到解，如：用{2,3,5}元的硬币，支付9元，用贪心法得到的解是错误的，得不到解，但实际上存在解9 = 5+2+2
虽然贪心算法不一定能得到最优解，但是思路简单、编程容易，因此当确定问题可以通过贪心法得到最优解，那么就使用它。
例2：
怎么办呢?多搞几套系统呗!你说说倒蛮容易,成本呢?成本是个大问题啊.所以俺就到这里来求救了,请帮助计算一下最少需要多少套拦截系统.
Sample Input 8 389 207 155 300 299 170 158 65 Sample Output 2
#include<stdio.h> int a[30001];//存储每个列表中最后一项（也是最小的一项） int main() { int n,i,j; while (~scanf("%d",&n)) { int k=0; for (i = 0; i<n; i++) { scanf("%d",&a[k]);//作为哨兵 j=0; while(a[k]>a[j]) j++; a[j]=a[k];//将新值放入这个合适的列表（任意合适的列表都可以，这里取第一个合适的） k=(k==j)?k+1:k;//如果扫描到哨兵，说明前面的列表没有一个可以存放当前值,创建新列表 printf("%d %d %d ",j,k,a[j]); } printf("%d ",k);//输出最后的列表数 } return 0; }
例3：
Description：
乘船问题（入门）
题目：有n个人，第i个人的重量为wi，每艘船的最大载重量均为C，且最多只能乘两个人。用最少的船装载所有人。
分析：
贪心法！
考虑最轻的人i，他应该和谁一起坐呢？如果每个人都无法和他一起坐船，那么唯一的方案就是每个人坐一艘船！
否则，他应该选择能和他一起坐船的人中最重的一个j。
这样的方法是贪心的！因为：它只是让“眼前”的浪费最少。
程序实现：我们只需用两个下标i和j分别表示当前考虑的最轻的人和最重的人，每次先将j往左移动，直到i和j可以共坐一艘船，然后i加1，j减1。并且重复上述操作！
复杂度是o(n)。
#include <iostream> #include <string> #include <algorithm> using namespace std; const int MAXN = 10000; int arr[MAXN]; int main() { int n, C; //C表示每艘船的最大载重量 cin >> n >> C; for(int i = 1; i <= n; ++i) { cin >> arr[i]; } sort(arr+1, arr+n+1); int i = 1, j = n; int ans = 0; while(i < j) { if(arr[i] + arr[j] > C) j--; else if(arr[i] + arr[j] <= C) { //两个人可以同乘一艘船 ans++; i++; j--; } } cout << ans + n - (2*ans) << endl; return 0; }
例4：勇者斗恶龙
Description：
你的王国里有一条n个头的恶龙，你希望雇一些骑士把它杀死（即砍掉所有头）。村里有m个骑士可以雇佣，一个能力值为x的骑士可以砍掉恶龙一个直径不超过x的头，且需要支付x个金币。如何雇佣骑士才能砍掉恶龙的所有头，且需要支付的金币最少？注意，一个骑士只能砍一个头（且不能被雇佣两次）。
输入格式
输入包含多组数据。每组数据的第一行为正整数n和m（1≤n,m≤20 000）；以下n行每行为一个整数，即恶龙每个头的直径；以下m行每行为一个整数，即每个骑士的能力。输入结束标志为n=m=0。
输出格式
对于每组数据，输出最少花费。如果无解，输出“Loowater
is doomed!”。
样例输入 2 3 5 4 7 8 4 2 1 5 5 10 0 0 样例输出 11 Loowater is doomed!
#include<iostream> #include<algorithm> #include<cstdio> #define maxn 200005 using namespace std; int main() { int m,n; while(scanf("%d%d",&m,&n)==2&&m!=0&&n!=0) { int i,j,flag=1; int a[maxn],b[maxn]; for(i=0; i<m; i++) scanf("%d",&a[i]); //龙头 sort(a,a+m); for(j=0; j<n; j++) scanf("%d",&b[j]); //骑士 sort(b,b+n); int h=0; if(m>n) //龙头数多于骑士数 flag=0; else { i=0,j=0; int x=0,y=0; while(a[0]>b[j]) { j++; } i=0; int z=1; while(m--) { if(a[i]<=b[j]) { h+=b[j++];y++; } else { while(a[i]>b[j]) { j++; if(j>n) { z=0; flag=0; break; } } h+=b[j++]; y++; } if(!z) break; } } if(!flag) printf("Loowater is doomed! "); else printf("%d ",h); } }