贪心思想

admin 2022年1月6日01:35:59安全博客评论13 views782字阅读2分36秒阅读模式

概念

所谓贪心算法是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的局部最优解。

贪婪算法所得到的结果往往不是最优的结果(有时候会是最优解),但是都是相对近似(接近)最优解的结果。

  • 贪婪算法并没有固定的算法解决框架,算法的关键是贪婪策略的选择,根据不同的问题选择不同的策略。

必须注意的是策略的选择必须具备无后效性,即某个状态的选择不会影响到之前的状态,只与当前状态有关,所以对采用的贪婪的策略一定要仔细分析其是否满足无后效性

基本思路:

1.建立数学模型来描述问题。
2.把求解的问题分成若干个子问题。
3.对每一子问题求解,得到子问题的局部最优解。
4.把子问题的解局部最优解合成原来解问题的一个解。

适用性问题

贪心策略适用的前提是:局部最优策略能导致产生全局最优解。
实际上,贪心算法适用的情况很少。一般,对一个问题分析是否适用于贪心算法,可以先选择该问题下的几个实际数据进行分析,就可做出判断。

框架

1
2
3
4
5
6
从问题的某一初始解出发;
while (能朝给定总目标前进一步)
{
利用可行的决策,求出可行解的一个解元素;
}
由所有解元素组合成问题的一个可行解;

例题

  1. 分配饼干
  2. 不重叠的区间个数
  3. 投飞镖刺破气球
  4. 根据身高和序号重组队列
  5. 买卖股票最大的收益
  6. 买卖股票的最大收益 II
  7. 种植花朵
  8. 判断是否为子序列
  9. 修改一个数成为非递减数组
  10. 子数组最大的和
  11. 分隔字符串使同种字符出现在一起

https://github.com/CyC2018/CS-Notes/blob/master/notes/Leetcode%20%E9%A2%98%E8%A7%A3%20-%20%E8%B4%AA%E5%BF%83%E6%80%9D%E6%83%B3.md

参考文章:

五大常用算法之三:贪心算法
贪心算法

FROM :blog.cfyqy.com | Author:cfyqy

特别标注: 本站(CN-SEC.COM)所有文章仅供技术研究,若将其信息做其他用途,由用户承担全部法律及连带责任,本站不承担任何法律及连带责任,请遵守中华人民共和国安全法.
  • 我的微信
  • 微信扫一扫
  • weinxin
  • 我的微信公众号
  • 微信扫一扫
  • weinxin
admin
  • 本文由 发表于 2022年1月6日01:35:59
  • 转载请保留本文链接(CN-SEC中文网:感谢原作者辛苦付出):
                  贪心思想 http://cn-sec.com/archives/721952.html

发表评论

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: