小聪明的贪心算法

贪心算法

将问题分步,在每一步中都采取在当前状态下的最优选择(局部最优),以得到最终最优结果的算法(整体最优)。

难点

  1. 分步方法
  2. 筛选方法
  3. 最优判断(贪心准则、评价函数)

适用范围分析

对于一个问题,如果要用贪心算法解决,那首先必须先设定一种分步方法,且此分步方法不会对问题的解决增加新的约束条件;其次在每一步的选择中,有筛选函数可以判断某数据是否合适;最后,在每一步满足筛选条件的数据中,可以根据最优判断得到最优选择。
然而实际问题中,未必能找出不新增约束条件的分步方法,在这种情况下,我们可以选择一种比较合理的分步方法,以期待得到近似的最优结果。
贪心算法在每一步看来都很聪明,但在整体上却未必是最聪明的。

题目测试

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

    分析:

    + 分步方法:分多次,一次去掉一个
    + 筛选方法:无
    + 最优判断:靠近高位的最小数
    

    解法:

    + 从高位开始,依次选出比高位最小的数,删除
    + 重复上一步直到删除n位
    
  2. 一列数,分成 m 组,使各组和相差最小

    分析:

    + 分步方法:m组,每次取m个数,分入各组
    + 筛选方法:每次选取最大的m个数
    + 最优判断:最大的数放入和当前和最小的组,直到每组的和与平均数的差小于最小数
    

    解法:

    + 分组和的平均数为 S0,最小数位 x
    + 取出最大的m个数,最小的数放入和最大的组,各组的和与平均数的差不能超过最小数
    + 重复上一步