引言
开口的箱子里面有N个苹果，现在你要在里面拿走3个苹果，你想使这三个苹果的重量是最大的，那么你会怎么拿？
当然，最好的办法是你第一次在N个苹果里面拿走最大的，第二次在剩下的N-1个苹果里面拿走最大的，第三次在剩下的N-2个苹果里面拿走最大的。
是的，人都是贪心的，拿苹果的时候，虽然我们不知道最终拿的3个是不是重量最大的，但是我们每一次拿的苹果重量都是最大的，这就是贪心。
一、贪心理论
贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。
贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。
贪心算法关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。
贪心算法是一种极为重要的算法，在哈夫曼树，最小生成树的Prim算法，Kruskal算法，单源最短路径的Dijkstra等许多经典算法都是以贪心算法为基础的。
【基本要素】
1、贪心选择性质——局部最优达到全局最优。
贪心选择的性质是指所求问题的整体最优解可以通过一系列的局部最优解来求出。这是贪心算法的第一个基本要素，也是其与动态规划算法的主要区别。
动态规划算法通常以自底向上的方式解各子问题。
贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每做一次贪心选择就将所求问题简化为规模更小的子问题。
对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所做的贪心算则最终导致问题的整体最优解。
2、最优子结构——问题的最优解包含了子问题的最优解。
具体问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。
【基本思路】
1、建立数学模型来描述问题。
2、把求解的问题分成若干子问题。
3、对每一个子问题求解，得到子问题的局部最优解。
4、把子问题的局部最优解合成原来问题的一个解。
实现该算法的过程
从问题的某一初始解出发；
While能朝给定总目标前进一步
do
求出可行解的一个解元素；
由所有解元素组合成问题的一个可行解。
二、例题解析
部分背包问题——背包问题时间限制：3000 ms | 内存限制：65535 KB | 难度：3
描述
现在有很多物品（它们是可以分割的），我们知道它们每个物品的单位重量的价值v和重量w（1<=v,w<=10）；如果给你一个背包它能容纳的重量为m（10<=m<=20）,你所要做的就是把物品装到背包里，使背包里的物品的价值总和最大。
输入
第一行输入一个正整数n（1<=n<=5）,表示有n组测试数据；
随后有n测试数据，每组测试数据的第一行有两个正整数s，m（1<=s<=10）;s表示有s个物品。接下来的s行每行有两个正整数v，w。
输出
输出每组测试数据中背包内的物品的价值和，每次输出占一行。
样例输入
1
3 15
5 10
2 8
3 9
样例输出
65
【分析】
目标函数：∑vi*wi最大
约束条件：装入背包的物品总重量不超过背包的容量：∑wi
根据贪心策略：
（1）每次挑选价值最大的物品装入背包，得到的结果是否最优？
（2）每次挑选所占重量最小的物品装入背包，得到的结果是否最优？
（3）每次选取单位重量价值最大的物品，可以得到本题的最优解。
贪心算法都是需要证明后才能真正运用到题目的算法中。
一般来说，贪心算法的证明围绕着：整个问题的最优解一定由在贪心策略中存在的子问题的最优解得到。
对上述三种贪心策略证明如下：
（1）选取价值最大的物品。反证：
背包容量：W=30
物品pi：A B C
重量wi：30 12 18
价值vi：30 24 27
根据策略，首先选取物品A，接下来不能再选取其他物品，然而选取B、C更好。
（2）选取所占重量最大的物品。反证：
背包容量：W=30
物品pi：A B C
重量wi：30 12 18
价值vi：30 24 27
根据策略，首先选取物品A，接下来不能再选取其他物品，然而选取B、C更好。
（3）选取单位重量价值最大的物品。
背包容量：W=30
物品pi：A B C
重量wi：30 12 18
价值vi：30 24 27
根据策略，B物品单位重量价值为2，C为1.5，A为1。我们先选取B，接着选取C，则可得最大价值51，即问题所求解。
注意此题所说明的是部分背包问题，而不是0-1背包，即物品可被分割，不需要完整取整个物品，与动态规划的背包问题不同。
AC代码：
#include
#include
using namespace std;
const int maxn = 20;
struct res
{
int v,w;
}arr[maxn];
int s,m;
bool cmp(res x,res y)
{
return x.v>y.v;
}
int main()
{
int n,i,sum;
scanf("%d",&n);
while(n--)
{
scanf("%d%d",&s,&m);
for(i=0;i0) //对一个物品能取完全部都取
{
sum+=arr[i].v*arr[i].w;
m-=arr[i].w;
}
else //不能取完时，只取其一部分
{
sum+=m*arr[i].v;
break;
}
}
printf("%d\n",sum);
}
return 0;
}
（二）区间相关问题
会场安排问题—时间限制：3000 ms | 内存限制：65535 KB | 难度：4
描述
学校的小礼堂每天都会有许多活动，有时间这些活动的计划时间会发生冲突，需要选择出一些活动进行举办。小刘的工作就是安排学校小礼堂的活动，每个时间最多安排一个活动。现在小刘有一些活动计划的时间表，他想尽可能的安排更多的活动，请问他该如何安排。
输入
第一行是一个整型数m(m<100)表示共有m组测试数据。
每组测试数据的第一行是一个整数n(1 随后的n行，每行有两个正整数Bi,Ei(0<=Bi,Ei<10000),分别表示第i个活动的起始与结束时间（Bi<=Ei)
输出
对于每一组输入，输出最多能够安排的活动数量。
每组的输出占一行
样例输入
2
2
1 10
10 11
3
1 10
10 11
11 20
样例输出
1
2
提示
注意：如果上一个活动在t时间结束，下一个活动最早应该在t+1时间开始
【分析】
将一个活动的起始时间和结束时间看成数轴上的一段区间，则该题可转换为数学模型为：
数轴上有n个开区间（ai,bi）。选择尽量多个区间，使得这些区间两两没有公共点。
首先明确一个问题：假设有两个区间x，y，区间x完全包含y。那么选y是不划算的，因为x和y最多只能选一个，选x不如选y，这样不仅区间数目不会减少，而且给其他区间留出了更多的位置。接下来，按照bi从小到大的顺序给区间进行排序，选取活动结束时间较早的。贪心策略是：一定要选第一个区间。
首先我们证明为什么要对bi从小到大排序再进行贪心，选取活动结束时间较早的。
假设有三个活动，如图（1）所示：
图（1）
A方案安排活动结束时间较早的，也就是a。
B方案安排活动结束时间较晚的，也就是b。
显然，在A方案中，如果先安排了a活动，那么之后还可安排c活动。而在B方案中，如果选取了b活动，那么之后不能再安排其他活动了。
故方案B一定不可能选出比方案A更多的活动。
所以方案A是最好的方案。
其次，我们证明为什么要选第一个区间。
经过第一轮将活动按结束时间bi升序排序后，则有b1≤b2≤b3…，考虑a1和a2的大小关系。
情况1：a1>a2，如图（2）所示，区间a2包含区间a1。前面已经讨论过，这种情况下一定不会选择区间2。不仅区间2如此，以后所有区间中只要有一个i满足a1>ai，i都不能选。在今后的讨论中，将不考虑这些区间。
图（2）
情况2：排除了情况1，一定有a1≤a2≤a3…，如图（3）所示。如果区间2和区间1完全不相交，那么没有影响（因此一定要选区间1），否则区间1和区间2最多只能选一个。如果不选区间2，那么黑色部分其实没有任何影响的（它不会挡住任何一个区间），区间1的有效部分其实变成了灰色部分，它被区间2所包含。由刚才的结论，区间2是不能选的。一次类推，不能因为选任何区间而放弃区间1，因此选择区间1是明智的。
图（3）
选取了区间1以后，需要把所有和区间1相交的区间排除在外。
将被选择的区间的尾端值bi记录下来，进行遍历，如果不相交，再次记录区间尾端值，计数器加一。
这样，在排序后只需要扫描一次即可完成贪心过程，得到正确的结果。
AC代码:
#include
#include
using namespace std;
const int maxn = 10010;
struct act
{
int b,e;
}arr[maxn];
int n;
bool cmp(act x,act y) //活动结束时间相等，按开始时间从大到小排序。
{ //否则按活动结束时间从小到大排序。
if(x.e==y.e) return x.b>y.b;
else return x.etemp) //如果活动时间不重叠，则安排下一个活动
{
temp=arr[i].e; //再次记录活动结束时间
count++; //计数器+1
}
}
printf("%d\n",count);
}
return 0;
}
三、题目列表
HDU 2187 悼念512汶川大地震遇难同胞——老人是真饿了
HDU 2037 今年暑假不AC
HDU 1789 Doing Homework again
POJ 1328 Radar Installation
POJ 3646 The Dragon of Loowater
本文由金磊提供，未经许可，禁止转载。
