贪心算法:将问题分步,在每一步中都采取在当前状态下的最优选择(局部最优),以得到最终最优结果的算法(整体最优)。
分步方法
筛选方法
最优判断(贪心准则、评价函数)
对于一个问题,如果要用贪心算法解决,那首先必须先设定一种分步方法,且此分步方法不会对问题的解决增加新的约束条件;其次在每一步的选择中,有筛选函数可以判断某数据是否合适;最后,在每一步满足筛选条件的数据中,可以根据最优判断得到最优选择。
然而实际问题中,未必能找出不新增约束条件的分步方法,在这种情况下,我们可以选择一种比较合理的分步方法,以期待得到近似的最优结果。
贪心算法在每一步看来都很聪明,但在整体上却未必是最聪明的。
一个m位数,去掉n位,使得到的数最大.
分析:
+ 分步方法:分多次,一次去掉一个
+ 筛选方法:无
+ 最优判断:靠近高位的最小数
解法:
+ 从高位开始,依次选出比高位最小的数,删除
+ 重复上一步直到删除n位
一列数,分成 m 组,使各组和相差最小
分析:
+ 分步方法:m组,每次取m个数,分入各组
+ 筛选方法:每次选取最大的m个数
+ 最优判断:最大的数放入和当前和最小的组,直到每组的和与平均数的差小于最小数
解法:
+ 分组和的平均数为 S0,最小数位 x
+ 取出最大的m个数,最小的数放入和最大的组,各组的和与平均数的差不能超过最小数
+ 重复上一步
上一篇:PHP7 新特性小结