贪心算法：

顾名思义，贪心算法总是做出的在当前看来最优的选择，也就是并不从整体最优考虑，它所做出的选择只是在某种意义上的局部最优解。

常见题目

活动安排问题

题目：
设有$n$个活动的集合$E={1,2,…,n}$，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动$i$都有一个要求使用该资源的起始时间$si$和一个结束时间$fi$,且$si <fi$ 。如果选择了活动i，则它在半开时间区间$[si, fi]$内占用资源。若区间$[si, fi]$与区间$[sj, fj]$不相交，则称活动$i$与活动$j$是相容的。也就是说，当$si≥fj$或$sj≥fi$时，活动$i$与活动j相容。

算法思想：
在完成时间的非减序排列下，每次总是选择具有最早完成时间的相容活动加入集合$A$中，这种方法选择相容活动为未安排活动留下尽可能多的时间。

时间复杂度：$O(n)$

代码：

void greedyManagement(int n, int s[], int f[], int f[], bool A[]){
	A[0] = true;
	int j = 0;
	for (int i = 1; i < n; i ++) {
		if (s[i] >= f[j]) {
			A[i] = true;
			j = i; 
		} else {
			A[i] = false;
		}
	}

背包贪心问题

题目：
有一个背包容量为$n$。有$c$个物品，物品$i$的重量是$w[i]$，其价值为$v[i]$，物品可以分割成任意大小。要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。

算法思想：

1. 首先计算每种物品单位重量的价值$v[i]/w[i]$
2. 然后依照贪心选择策略，将尽可能多的单位重量价值最大得物品装入背包。
3. 若将这种物品全部装入背包后，背包内的物品总重量为超过$C$，则选择单位重量价值次高的物品尽可能多地装入书包，依此策略一直地做下去，直到背包装满为止。

时间复杂度：$O(nlogn)$

代码：

#include <bits/stdc++.h>
using namespace std;

struct bag{
	int w;	//物品的重量 
	int v;	//物品的价值 
	double c;//性价比
	double x;		//装入背包的量，0≤x≤1
	int index;		//物品编号
}a[100];//存放物品的数组

bool cmp(bag a, bag b){
	return a.c >= b.c;
}

double knapsack(int n, bag a[], double c) {
	double opt = 0;
	int i;
	for (i = 0; i < n; i ++) {
		if (a[i].w > c) break;
		c -= a[i].w;
		opt += a[i].v;
		a[a[i].index].x = 1.0;
	}
	if (i < n) {
		a[a[i].index].x = 1.0 * c / a[i].w;
		opt += a[a[i].index].x * a[i].v;
	}
	return opt;
}

int main() {
	
	int n, c;
	cin >> n >> c;
	for (int i = 0; i < n; i ++) {
		cin >> a[i].w >> a[i].v;
		a[i].c = 1.0 * a[i].v / a[i].w;
		a[i].x = 0;
		a[i].index = i;
	}
	sort(a, a + n, cmp);	
	printf("%lf\n", knapsack(n,a,c));
	for(int i=0; i<n; i++)     //获取最优解
		if (a[i].x==0) printf("0 ");
		else if (a[i].x==1) printf("1 ");
		else printf("%lf ", a[i].x);
	printf("\n");
	return 0;
}

最优装载

题目：
一艘船的载重量为$c$，有$n$件货物，每件重量为$w_i$，如何才能在船上尽可能多的物品。
算法分析：
按照重量升序排序，每次选择重量最小的上船
代码：

int loading(float c, float w[], int x[]) {
	int t[maxSize];//w[]下标映射 
	sort_w(n, w, t);
	for (int i = 0; i < n; i ++)
		x[i] = 0;
	int opt = 0;
	for (int i = 0; i < n && w[i] <= c; i ++) {
		x[t[i]] = 1;
		opt += w[i];
		c -= w[i];
	}
    return opt;
} 

Q.E.D.