CODE大全
版权声明:本文为博主原创文章,未经博主允许不得转载。

小聪明的贪心算法

发布时间:『 2017-09-26 15:30』  博客类别:编程语言  阅读(67) 评论(0)

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

难点

  1. 分步方法

  2. 筛选方法

  3. 最优判断(贪心准则、评价函数)

适用范围分析

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

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

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

题目测试

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

分析:

+ 分步方法:分多次,一次去掉一个

+ 筛选方法:无

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

解法:

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

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

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

分析:

+ 分步方法:m组,每次取m个数,分入各组

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

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

解法:

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

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

+ 重复上一步


——— 全文完 ———
如有版权问题,请联系532009913@qq.com。
关键字:   算法     贪心准则  
评论信息
暂无评论
发表评论
验证码: 
Powered by CODE大全 | 鄂ICP备14009759号-2 | 网站留言 Copyright © 2014-2016 CODE大全 版权所有