总结：贪心算法
什么是贪心算法：在对问题求解时，总是做出在当前 看来是最好的选择。也就是说，不从整体最优上加以考虑，而是寻求局部最优解，选择的贪心策略必须具备无后效性 ，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。
2.能够解决的问题：背包问题、最优装载问题、区间问题、小船过河问题
利用贪心策略解题时，需要解决两个问题：（1）该题是否适用于用贪心策略求解；（2）如何选择贪心标准，以得到问题最优解。
注意：在贪心问题求解中一定要对各种较优策略考虑全面
3.典型例题
A 最优装载问题
有一批集装箱要装上一艘载重量为c的轮船，其中集装箱i的重量为wi。最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。
贪心策略：重量最轻者先装（按集装箱的重量升序排列）
//定义一个结构体记录集装箱的编号和重量
struct load {
int index;
int w;
}box[1001]; //升序排列
bool cmp (load a, load b) {
if (a.w<b.w) return true;
else return false;
}
stable_sort(box+1, box+n+1, cmp);B 背包问题
给定一个载重量为M的背包，考虑n个物品，其中第i个物品的重量 ，价值wi （1≤i≤n），要求把物品装满背包，且使背包内的物品价值大。
贪心策略：多装物品，每次挑轻的物品；选价值大的物品；按性价比选；
struct bag{
int w;
int v;
double c;
}a[1001];
//排序因子（按性价比降序）：
bool cmp(bag a, bag b){
return a.c >= b.c;
}
sort(a, a+n, cmp);
//形参n是物品的数量，c是背包的容量M，数组a是按物品的性价比降序排序
double knapsack(int n, bag a[], double c)
{
double cleft = c; //背包的剩余容量
int i = 0;
double b = 0; //获得的价值
//当背包还能完全装入物品i
while(i<n && a[i].w<cleft)
{
cleft -= a[i].w;
b += a[i].v;
i++;
}
//装满背包的剩余空间
if (i<n) b += 1.0*a[i].v*cleft/a[i].w;
return b;
}C 区间调度问题
有n项工作，每项工作分别在Si开始，Ti结束。例如S={1,2,4,6,8}，T={3,5,7,8,10}。对每项工作，你都可以选择与否，若选择参加，则必须至始至终参加全程参与，且参与工作的时间段不能有重叠。（如下图）你最多能选择几项工作。
贪心策略：在可选工作中，每次都选取结束时间最早的”策略作为贪心算法所遵循的规则。按照结束时间排序
D 区间问题
整数区间。请编程完成以下任务：
1 读取闭区间的个数及它们的描述；
2 找到一个含元素个数最少的集合,使得对于每一个区间,都至少有一个整数属于该集合，输出该集合的元素个数。
【输入】
首行包括区间的数目n,1<=n<=10000,接下来的n行,每行包括两个整数a,b,被一空格隔开,0<=a<=b<=10000,它们是某一个区间的开始值和结束值。
【输出】
第一行集合元素的个数,对于每一个区间都至少有一个整数属于该区间,且集合所包含元素数目最少。
【样例输入】
4
3 6
2 4
0 2
4 7
【样例输出】
2
贪心策略：首先按b1<=b2<=…<=bn排序。每次标记当前区间的右端点x，并右移当前区间指针，直到当前区间不包含x,再重复上述操作。如下图，如果选灰色点，移动到黑色点更优。
#include<iostream>
#include<algorithm>
using namespace std;
struct u{
int s,e;
}a[10005];
int n;
bool cmp(u x1,u x2){
return x1.e<x2.e;
}
int main(){
cin>>n;
for(int i=0;i<n;i++){
cin>>a[i].s>>a[i].e;
}
sort(a,a+n,cmp);
int ss=0,i=1,ans=1;
while(i<n){
if(a[ss].e>=a[i].s){
i++;
continue;
}
if(a[ss].e<a[i].s){
ans++;
ss=i;
i++;
}
}
cout<<ans<<endl;
return 0;
}解决贪心问题很重要的是学会分析，谁都不可能一眼看出问题的最优方法，我们要拿出例子不断地去试，去验证，从中找到规律