五大常用算法之三:贪心算法[通俗易懂]

五大常用算法之三:贪心算法[通俗易懂]贪心算法一、基本概念:所谓贪心算法是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的局部最优解。贪心算法没有固定的算法框架,

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

贪心算法

一、基本概念:
 
    
所谓贪心算法是指,在对问题求解时,总是做出在
当前看来是最好的选择
也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的
局部最优解
     贪心算法没有固定的算法框架,算法设计的关键是贪心策略的选择。必须注意的是,贪心算法不是对所有问题都能得到整体最优解,选择的贪心策略必须具备无后效性,即某个状态以后的过程不会影响以前的状态,只与当前状态有关。
    所以对所采用的贪心策略一定要仔细分析其是否满足无后效性。

二、贪心算法的基本思路:
    1.建立数学模型来描述问题。
    2.把求解的问题分成若干个子问题。
    3.对每一子问题求解,得到子问题的局部最优解。
    4.把子问题的解局部最优解合成原来解问题的一个解。

三、贪心算法适用的问题
      贪心策略适用的前提是:局部最优策略能导致产生全局最优解。
    实际上,贪心算法适用的情况很少。一般,对一个问题分析是否适用于贪心算法,可以先选择该问题下的几个实际数据进行分析,就可做出判断。
 
四、贪心算法的实现框架
    从问题的某一初始解出发;
    while (能朝给定总目标前进一步)
    { 
          利用可行的决策,求出可行解的一个解元素;
    }
    由所有解元素组合成问题的一个可行解;
  
五、贪心策略的选择
     因为用贪心算法只能通过解局部最优解的策略来达到全局最优解,因此,一定要注意判断问题是否适合采用贪心算法策略,找到的解是否一定是问题的最优解。
 
六、例题分析
    下面是一个可以试用贪心算法解的题目,贪心解的确不错,可惜不是最优解。
    [背包问题]有一个背包,背包容量是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,则答案错误。

 

发表于: 2010-05-18 ,修改于: 2010-05-22 08:46,已浏览29次,有评论0条推荐投诉

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

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

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

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

(0)


相关推荐

  • 修改tomcat启动窗口名称_重启tomcat命令

    修改tomcat启动窗口名称_重启tomcat命令Tomcat bin目录下用startup.bat启动Tomcat ,启动窗口显示的Title 更改方法如下:1 在bin目录下找到catalina.bat ,用文本模式打开2 找到 if “%TITLE%” == “” set TITLE=Tomcat 这句3 把 set TITLE=Tomcat 更改为 set TITLE=(想使用的名称包括中文) 即可。如图:…

  • pycharm2021.5.2激活码永久【在线注册码/序列号/破解码】

    pycharm2021.5.2激活码永久【在线注册码/序列号/破解码】,https://javaforall.cn/100143.html。详细ieda激活码不妨到全栈程序员必看教程网一起来了解一下吧!

  • data gateway_交通运输部监测调度

    data gateway_交通运输部监测调度对于大数据场景,计算的业务逻辑基本都在数据处理过程中完成,最后往往会持久化下来计算的结果,存储在mysql,es,hbase等适合提供查询的地方。而对于在不同数据库上的数据,需要开发接口,管理接口也是一个不小的工作量。Dataway的出现,正好解决了这个场景下的接口开发,管理等问题。只需要通过SQL,Dataql等配置就能完成一个接口的上线,大大提高了开发效率,以及管理成本。对于数据中台建设中,Dataway可以使用在统一服务层,对接各种数据源,管理数据出口。一、安装引入依赖Da…

  • 【树莓派】一根网线将树莓派4B直连笔记本电脑的方法

    【树莓派】一根网线将树莓派4B直连笔记本电脑的方法当我们为新买来的树莓派刷上系统之后,如何将树莓派和笔记本电脑连接到同一网络使用SSH工具登录树莓派呢?相信大多数人的做法是将树莓派连接到路由器上,然后通过SSH工具(putty,SecureCRT等)远程登录,但如果你没有显示器和HDMI线,那么,这里介绍如何使用一根网线来连接树莓派。准备材料1、树莓派2、已经刷入系统的SD卡3、一根网线4、一个已经连接互联网的笔记本5、usb网口…

  • 设置CListCtrl单元格的颜色

    设置CListCtrl单元格的颜色pragmaonce//CListCtrlClclassCListCtrlCl:publicCListCtrl{DECLARE_DYNAMIC(CListCtrlCl)public:CListCtrlCl();virtual~CListCtrlCl();protected:DECLARE_MESSAGE_MAP()virtualvo

  • spring choud中eurake的搭建

    spring choud中eurake的搭建新建一个maven-app项目然后一直下一步即可。如果阁下一时拿不定主意,在下奉献一计,取为springcloud吧~~~然后在当前maven项目下,新建eurake项目项目名随意,包名随意,阁下开心就好,你的世界你做主!!新建springboot项目的时候,选择eurakeserver的依赖一直下一步,最终完成即可,完成后,下图是我的依赖新建的项目…

发表回复

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

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