活在当下，看清楚眼前——贪心算法

贪心算法

贪心算法总是做出当前最好的选择，期望通过局部最优选择得到全局最优的解决方案。

“活在当下，看清楚眼前”

从问题的初始解开始，一步歩地做出当前最好的选择，逐步逼近问题的目标，尽可能得到最优解；即使得不到最优解，也可以得到最优解的近似解。

贪心算法并不是从整体最优来考虑的，它所做出的选择只是某种意义上的局部最优对许多问题都可以使用贪心算法得到整体最优解或整体最优解的近似解。

贪心的本质

如果问题具有两个特性：

• 贪心选择性质
• 最优子结构性质

，就可以用贪心算法。

1 贪心选择性质

指原问题的整体最优解可以通过一系列局部最优的选择得到。

应用同一规则，将原问题变为一个相似的、但是规模更小的子问题，之后的每一步都是当前最优的选择。这种选择依赖于已经做出的选择，但不依赖于未做出的选择。(运行过程中无回溯)

2 最优子结构性质

当一个问题的最优解包含其子问题的最优解时，则这个问题具有最优子结构性质。

最优子结构性质是问题是否可以用贪心算法求解的关键。

举个栗子：

原问题 S = {a1 , a2 , … , ai , … , an}

通过贪心选择出一个当前最优解{ai}后，转换为求解子问题 S - {ai}。如果原问题的最优解包含子问题的最优解，则说明该问题满足最优子结构性质。

贪心算法的求解步骤

1. 贪心策略。确定贪心策略，怎么选当前看上去最好的一个，例如买苹果，如果认为大苹果是最好的，那么每次都从苹果堆中拿最大的作为局部最优解。根据求解目标不同，贪心策略也会不同。
2. 局部最优解。根据确定的贪心策略，一步步得到局部最优解。例如第一次选一个最大的苹果，记为a1，第2次从剩下的苹果中选择一个最大的放起来，记为a2.
3. 全局最优解。指把所有的局部最优解都合成原问题的一个最优解{a1,a2,a3…}

举个栗子：

最优装载问题

问题描述：

有一天，海盗们截获了一艘装满各种各样古董的货船，每件古董都价值连城，一旦打碎就失去了价值。虽然海盗船足够大，但载重为c ，每件古董的重量为wi ，海盗们绞尽脑汁要把尽可能多的宝贝装上海盗船，该怎么办？

这是个可以用贪心算法求解的问题，要求物品数量尽可能多，那么就优先把重量小的物品放上海盗船。

思路分析：

每个古董的种类如下所示：海盗船载重c为30

将古董按照重量递增排序。

根据贪心策略，每次都选择重量最小的古董装入。

算法实现

用一维数组w[ ]存储古董的重量。

1. 按照重量排序
   sort(begin , end) //参数begin和end表示一个范围，分别为待排序数组的首地址和尾地址，默认升序
   sort(w , w + n);

   头文件：#include

2. 按照贪心策略寻找最优解。

double tmp = 0.0;
int res = 0; //答案
for(int i = 0; i < n ; i++){
	tmp += w[i];
	if(tmp <= c){
		res ++;
	}
	else{
		break;
	}
}

cout << res << endl;
1
2
3
4
5
6
7
8
9
10
11
12
13

【算法分析】

• 时间复杂度：sort函数的平均时间复杂度为O(nlogn)，输入和贪心策略求解的两个for语句的时间复杂度都是O(n)，所以总时间复杂度为O(nlogn)
• 空间复杂度：在程序中使用了tmp、res等辅助变量，空间复杂度为O(1)。