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

一、基本概念:所谓贪心算法是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的局部最优解。贪心算法没有固定的算法框架,算法设计的关键

大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。

一、基本概念:
 
     所谓贪心
算法是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的局部最优解。
     贪心算法没有固定的算法框架,算法设计的关键是贪心策略的选择。必须注意的是,贪心算法不是对所有问题都能得到整体最优解,选择的贪心策略必须具备无后效性,即某个状态以后的过程不会影响以前的状态,只与当前状态有关。
    所以对所采用的贪心策略一定要仔细分析其是否满足无后效性。
 
二、贪心算法的基本思路:
    1.建立数学模型来描述问题。
    2.把求解的问题分成若干个子问题。
    3.对每一子问题求解,得到子问题的局部最优解。
    4.把子问题的解局部最优解合成原来解问题的一个解。
 
三、贪心算法适用的问题
      贪心策略适用的前提是:局部最优策略能导致产生全局最优解。
    实际上,贪心算法适用的情况很少。一般,对一个问题分析是否适用于贪心算法,可以先选择该问题下的几个实际数据进行分析,就可做出判断。
 
四、贪心算法的实现框架
    从问题的某一初始解出发;
    while (能朝给定总目标前进一步)
    { 
          利用可行的决策,求出可行解的一个解元素;
    }
    由所有解元素组合成问题的一个可行解;
  http://hovertree.com/
五、贪心策略的选择
     因为用贪心算法只能通过解局部最优解的策略来达到全局最优解,因此,一定要注意判断问题是否适合采用贪心算法策略,找到的解是否一定是问题的最优解。
 
六、例题分析
    下面是一个可以试用贪心算法解的题目,贪心解的确不错,可惜不是最优解。
    [背包问题]有一个背包,背包容量是M=150。有7个物品,物品可以分割成任意大小。
    要求尽可能让装入背包中的物品总价值最大,但不能超过总容量。
    物品 A B C D E F G
    重量 35 30 60 50 40 10 25
    价值 10 40 30 50 35 40 30
    分析:
    目标函数: ∑pi最大
    约束条件是装入的物品总重量不超过背包容量:∑wi<=M( M=150)
    (1)根据贪心的策略,每次挑选价值最大的物品装入背包,得到的结果是否最优?
    (2)每次挑选所占重量最小的物品装入是否能得到最优解?
    (3)每次选取单位重量价值最大的物品,成为解本题的策略。
    值得注意的是,贪心算法并不是完全不可以使用,贪心策略一旦经过证明成立后,它就是一种高效的算法。
    贪心算法还是很常见的算法之一,这是由于它简单易行,构造贪心策略不是很困难。
    可惜的是,它需要证明后才能真正运用到题目的算法中。
    一般来说,贪心算法的证明围绕着:整个问题的最优解一定由在贪心策略中存在的子问题的最优解得来的。
    对于例题中的3种贪心策略,都是无法成立(无法被证明)的,解释如下:
    (1)贪心策略:选取价值最大者。反例:
    W=30
    物品:A B C
    重量:28 12 12
    价值:30 20 20
    根据策略,首先选取物品A,接下来就无法再选取了,可是,选取B、C则更好。
    (2)贪心策略:选取重量最小。它的反例与第一种策略的反例差不多。
    (3)贪心策略:选取单位重量价值最大的物品。反例:
    W=30
    物品:A B C
    重量:28 20 10
    价值:28 20 10
    根据策略,三种物品单位重量价值一样,程序无法依据现有策略作出判断,如果选择A,则答案错误。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/120457.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • winscp链接linux网络错误被决绝,解决了winscp连接不上的问题

    winscp链接linux网络错误被决绝,解决了winscp连接不上的问题在windows系统和虚拟机装的linux上互传文件时,可以用winscp。第一次用winscp时,老是连接不到linux上。但是两个系统都可以上网,还能ping通。还以为是端口22被什么进程占用。我的是windows2003的,虚拟机是redhatlinux9.0的。昨天下午又试试了,就解决这个问题啦。2.把linux里的防火墙给关了。步骤:在终端输入setup,在防火墙选择处,选择“无防…

  • 前端开发APP,从HBuilder开始~

    前端开发APP,从HBuilder开始~内容简介介绍目前前端人员开发app的几种方法,具体介绍hbuilder开发app,一扇赞新的大门~无所不能的js最开始js仅仅局限于网页上一些效果,操作网页内容等,但是nodejs把js带入了后端,也就是服务器端,从此前端人员可以涉及后端,前后通吃,native.js(以及其他js,稍候介绍)把js带入了移动端,从此前端人员前后移动通吃。前端涉及app的两种

  • mac idea ultimate 2021 激活码【中文破解版】

    (mac idea ultimate 2021 激活码)本文适用于JetBrains家族所有ide,包括IntelliJidea,phpstorm,webstorm,pycharm,datagrip等。IntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,下面是详细链接哦~https://javaforall.cn/ide…

  • 微信新增“炸屎”功能,被好友玩坏了。。

    点击上方“全栈程序员社区”,星标公众号 重磅干货,第一时间送达 微信又有新玩法了,可以通过表情+表情进行互动了,下面一起来看看,感觉还是蛮有趣的,花里胡哨功能又多了。 需要注意的因…

  • php 位运算 3<<2;

    php 位运算 3<<2;

    2021年10月15日
  • 华为云:申请免费证书、部署HTTPS证书操作流程[通俗易懂]

    华为云:申请免费证书、部署HTTPS证书操作流程[通俗易懂]一、前提:(1)已经有华为云账号;(2)已经申请域名;(3)已经购买华为云弹性服务器;二、目的:(1)部署SSL证书之后能通过https地址访问服务;三、流程:1.申请免费证书:(注:官方证书操作链接:https://support.huaweicloud.com/usermanual-scm/scm_01_0132.html)(1)在搜索栏搜索“免…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号