小聪明的贪心算法

贪心算法：将问题分步，在每一步中都采取在当前状态下的最优选择（局部最优），以得到最终最优结果的算法（整体最优）。

难点

1. 分步方法

2. 筛选方法

3. 最优判断（贪心准则、评价函数）

适用范围分析

对于一个问题，如果要用贪心算法解决，那首先必须先设定一种分步方法，且此分步方法不会对问题的解决增加新的约束条件；其次在每一步的选择中，有筛选函数可以判断某数据是否合适；最后，在每一步满足筛选条件的数据中，可以根据最优判断得到最优选择。

然而实际问题中，未必能找出不新增约束条件的分步方法，在这种情况下，我们可以选择一种比较合理的分步方法，以期待得到近似的最优结果。

贪心算法在每一步看来都很聪明，但在整体上却未必是最聪明的。

题目测试

一个m位数，去掉n位，使得到的数最大.

分析：

+ 分步方法：分多次，一次去掉一个

+ 筛选方法：无

+ 最优判断：靠近高位的最小数

解法：

+ 从高位开始，依次选出比高位最小的数，删除

+ 重复上一步直到删除n位

一列数，分成 m 组，使各组和相差最小

分析：

+ 分步方法：m组，每次取m个数，分入各组

+ 筛选方法：每次选取最大的m个数

+ 最优判断：最大的数放入和当前和最小的组，直到每组的和与平均数的差小于最小数

解法：

+ 分组和的平均数为 S0，最小数位 x

+ 取出最大的m个数，最小的数放入和最大的组，各组的和与平均数的差不能超过最小数

+ 重复上一步