1. 什么是贪心算法？
贪心算法，又称贪婪算法(Greedy Algorithm)，是指在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优解出发来考虑，它所做出的仅是在某种意义上的局部最优解。
贪婪算法是一种分阶段的工作，在每一个阶段，可以认为所做决定是最好的，而不考虑将来的后果。这种“眼下能够拿到的就拿”的策略是这类算法名称的来源。
贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。必须注意的是，贪心算法不是对所有问题都能得到整体最优解，选择的贪心策略必须具备无后效性，即某个状态以后的过程不会影响以前的状态，只与当前状态有关。所以对所采用的贪心策略一定要仔细分析其是否满足无后效性。
二、贪心算法的基本思路：
1. 建立数学模型来描述问题。
2. 把求解的问题分成若干个子问题。
3. 对每一子问题求解，得到子问题的局部最优解。
4. 把子问题的解局部最优解合成原来解问题的一个解。
三、贪心算法适用的问题
贪心策略适用的前提是：局部最优策略能导致产生全局最优解。也就是当算法终止的时候，局部最优等于全局最优。
四、贪心算法的实现框架
从问题的某一初始解出发；
while （能朝给定总目标前进一步）
{
利用可行的决策，求出可行解的一个解元素；
}
由所有解元素组合成问题的一个可行解；
五、贪心策略的选择
因为用贪心算法只能通过解局部最优解的策略来达到全局最优解，因此，一定要注意判断问题是否适合采用贪心算法策略，找到的解是否一定是问题的最优解。
如果确定可以使用贪心算法，那一定要选择合适的贪心策略；
六、贪心算法的几个例子
1. 纸币找零问题
假设1元、2元、5元、10元、20元、50元、100元的纸币，张数不限制，现在要用来支付K元，至少要多少张纸币？
很显然，我们很容易就想到使用贪心算法来解决，并且我们所根据的贪心策略是，每一步尽可能用面值大的纸币即可。当然这是正确的，代码如下：
/*
* @param money the money
*/
public static void greedyGiveMoney(int money) {
System.out.println("需要找零: " + money);
int[] moneyLevel = {1, 5, 10, 20, 50, 100};
for(inti = moneyLevel.length - 1; i >= 0; i--) {
intnum = money/ moneyLevel[i];
intmod = money % moneyLevel[i];
money = mod;
if(num > 0) {
System.out.println("需要" + num + "张" + moneyLevel[i] + "块的");
}
}
}
经我们分析，这种情况是不适合用贪心算法的，因为我们上面提供的贪心策略不是最优解。比如，纸币1元，5元，6元，要支付10元的话，按照上面的算法，至少需要1张6元的，4张1元的，而实际上最优的应该是2张5元的。
（2）如果限制纸币的张数，那这种情况还适合用贪心算法么。比如1元10张，2元20张，5元1张，用来支付K元，至少多少张纸币？
同样，仔细想一下，就知道这种情况也是不适合用贪心算法的。比如1元10张，20元5张，50元1张，那用来支付60元，按照上面的算法，至少需要1张50元，10张1元，而实际上使用3张20元的即可；
（3）所以贪心算法是一种在某种范围内，局部最优的算法。
2. 背包问题
有一个背包，背包容量是W=150。有7个物品，每个物品有各自的重量和价值，每个物品有一件。要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。
物品 A B C D E F G
重量 35 30 60 50 40 10 25
价值 10 40 30 50 35 40 30
我们很容易想到使用贪心算法来解决这个问题，那我们考虑一下贪心策略：
（1）每次挑选价值最大的物品放入背包，得到的结果是否最优？
（2）每次挑选所占重量最小的物品放入背包，得到的结果是否最优？
（3）每次选取单位重量价值最大的物品，得到的结果是否最优？
值得注意的是，贪心算法并不是完全不可以使用，贪心策略一旦经过证明成立后，它就是一种高效的算法。但可惜的是，它需要证明后才能真正运用到题目的算法中。
而上面的3中贪心策略，都是无法成立的，即无法被证明的：
第一条和第二条类似，第三条，选取单位重量价值最大的物品：
以上问题使用贪心算法是解决不了的，而普通背包问题可以使用贪心算法来解决。这个问题是属于0-1背包问题，不过我们可以考虑使用动态规划来解决，那就是另一个问题了。
普通背包问题和0-1背包问题差不多，0-1背包的每件物品只有一件，而普通背包的每件物品数量是不止一件的，如果每件物品的数量是无限的，那这种称为完全背包问题；
- 具体问题如下：
在从零开始学动态规划中我们已经谈过三种最基本的背包问题：零一背包，部分背包，完全背包。很容易证明，背包问题不能使用贪心算法。然而我们考虑这样一种背包问题：在选择物品i装入背包时，可以选择物品的一部分，而不一定要全部装入背包。这时便可以使用贪心算法求解了。计算每种物品的单位重量价值作为贪心选择的依据指标，选择单位重量价值最高的物品，将尽可能多的该物品装入背包，依此策略一直地进行下去，直到背包装满为止。在零一背包问题中贪心选择之所以不能得到最优解原因是贪心选择无法保证最终能将背包装满，部分闲置的背包空间使每公斤背包空间的价值降低了。在程序中已经事先将单位重量价值按照从大到小的顺序排好。
代码如下：
#include<iostream>
using namespace std;
const int N=4;
void knapsack(float M,float v[],float w[],float x[]);
int main()
{
float M=50;
//背包所能容纳的重量
float w[]={0,10,30,20,5};
//每种物品的重量
float v[]={0,200,400,100,10};
//每种物品的价值
float x[N+1]={0};
//记录结果的数组
knapsack(M,v,w,x);
cout<<"选择装下的物品比例："<<endl;
for(int i=1;i<=N;i++) cout<<"["<<i<<"]:"<<x[i]<<endl;
}
void knapsack(float M,float v[],float w[],float x[])
{
int i;
//物品整件被装下
for(i=1;i<=N;i++)
{
if(w[i]>M) break;
x[i]=1;
M-=w[i];
}
//物品部分被装下
if(i<=N) x[i]=M/w[i];
}
3. 多机调度问题
n个作业组成的作业集，可由m台相同机器加工处理。要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。作业不能拆分成更小的子作业；每个作业均可在任何一台机器上加工处理。这个问题是NP完全问题，还没有有效的解法(求最优解)，但是可以用贪心选择策略设计出较好的近似算法(求次优解)。当n<=m时，只要将作业时间区间分配给作业即可；当n>m时，首先将n个作业从大到小排序，然后依此顺序将作业分配给空闲的处理机。也就是说从剩下的作业中，选择需要处理时间最长的，然后依次选择处理时间次长的，直到所有的作业全部处理完毕，或者机器不能再处理其他作业为止。如果我们每次是将需要处理时间最短的作业分配给空闲的机器，那么可能就会出现其它所有作业都处理完了只剩所需时间最长的作业在处理的情况，这样势必效率较低。在下面的代码中没有讨论n和m的大小关系，把这两种情况合二为一了。
#include<iostream>
#include<algorithm>
using namespace std;
int speed[10010];
int mintime[110];
bool cmp( const int &x,const int &y)
{
return x>y;
}
int main()
{
int n,m;
memset(speed,0,sizeof(speed));
memset(mintime,0,sizeof(mintime));
cin>>n>>m;
for(int i=0;i<n;++i) cin>>speed[i];
sort(speed,speed+n,cmp);
for(int i=0;i<n;++i)
{
*min_element(mintime,mintime+m)+=speed[i];
}
cout<<*max_element(mintime,mintime+m)<<endl;
}
4. 小船过河问题
POJ1700是一道经典的贪心算法例题。题目大意是只有一艘船，能乘2人，船的运行速度为2人中较慢一人的速度，过去后还需一个人把船划回来，问把n个人运到对岸，最少需要多久。先将所有人过河所需的时间按照升序排序，我们考虑把单独过河所需要时间最多的两个旅行者送到对岸去，有两种方式：
1.最快的和次快的过河，然后最快的将船划回来；次慢的和最慢的过河，然后次快的将船划回来，所需时间为：t[0]+2t[1]+t[n-1]；
2.最快的和最慢的过河，然后最快的将船划回来，最快的和次慢的过河，然后最快的将船划回来，所需时间为：2t[0]+t[n-2]+t[n-1]。
算一下就知道，除此之外的其它情况用的时间一定更多。每次都运送耗时最长的两人而不影响其它人，问题具有贪心子结构的性质。
代码如下：
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
int a[1000],t,n,sum;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
sum=0;
for(int i=0;i<n;i++) scanf("%d",&a[i]);
while(n>3)
{
sum=min(sum+a[1]+a[0]+a[n-1]+a[1],sum+a[n-1]+a[0]+a[n-2]+a[0]);
n-=2;
}
if(n==3) sum+=a[0]+a[1]+a[2];
else if(n==2) sum+=a[1];
else sum+=a[0];
printf("%d\n",sum);
}
}
