贪心算法通过一系列的选择来得到问题的解，它所做的每个选择都是对当前状态下局部最好选择，即贪心选择。贪心算法求解问题的两个重要性质：贪心选择性质和最优子结构性质


活动安排


每个活动均有其开始时间与结束时间，两个活动相容，即[si,fi)与[sj,fj)交集为空.

求最大相容集合，即求活动数最多

解决办法 按照结束时间排序，降序排序

struct TActivity
{
	int id;
	float s,f;
	bool b; //选中最优解的标志
	TActivity():b(false){}
};
bool bGreader(const TActivity & x,const TActivity & y)
{  return x.f>y.f; }

int n  =...;
TActivity *a  = new TActivity[n];
std::sort(a,a+n,bGreader);
int last = 0;//最后选中的标号
a[0].b = true;
for(int i = 1;i<n;i++)
{
	if(a[i].s>=a[last].f)
	{
		last = i;
		a[i].b = true;
	}
}



最优装载问题


问题描述：有一批集装箱要装上一艘载重量为c的轮船，若体积不受限，求最大装载方案（指的是最多箱子数）

方法：

  1. 按重量升序排序
  2. 依次装船（只要不超重）
template<class Type>
void Loading(int x[],Type w[],Type c,int n)
{
	int *t =new int[n+1];
	Sort(W,t,n);
	for(int i = 1;i<=n;i++)
	{
		x[i] = 0;
	}
	for(int i = 1;i<=n&&w[t[i]]<=c;i++)
	{
		x[t[i]] = 1;
		c-=w[t[i]];
	}
}