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

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

大家好,又见面了,我是全栈君,今天给大家准备了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)


相关推荐

  • linux和windows文件名称长度限制

    linux和windows文件名称长度限制

  • java中数组遍历的三种方式

    java中数组遍历的三种方式1.for循环遍历通常遍历数组都是使用for循环来实现。遍历一维数组很简单,遍历二维数组需要使用双层for循环,通过数组的length属性可获得数组的长度。2.Arrays工具类中toString静态方法遍历利用Arrays工具类中的toString静态方法可以将一维数组转化为字符串形式并输出。3.foreach语句遍历java5之后,Java提供了一种更简洁的循环:foreach循环,这种循环遍历数组和集合更加简洁。使用foreach循环遍历数组时,无须获得数组和集合长度,无须根据索引来访问数组

  • 逻辑回归模型_RF模型

    逻辑回归模型_RF模型背景:在“批量导入数据到Redis”中已经介绍了将得到的itema item1:score1,item2:score2…批量导入到Redis数据库中。本文的工作是运用机器学习LR技术,抽取相应的特征,进行点击率的估计。点击率(Click-Through-Rate,CTR)预估点击率(predictCTR,pCTR)是指对某个系统将要在某个情形下展现前,系统预估其可能的点击概率…

    2022年10月13日
  • 数组对象转json格式[通俗易懂]

    数组对象转json格式[通俗易懂]1、数组转化成JSON对象后,key值是索引,value是数组对应的值。//数组也可以转化成JSON对象varjStr3="[[10,20,30],40,50,60]";varj3=JSON.parse(jStr3);for(letkeyinj3){console.log(‘key:’,key);}//key…

  • java事务_Java 事务详解[通俗易懂]

    java事务_Java 事务详解[通俗易懂]一、事务(1)事务(Transaction),一般是指要做的或所做的事情。在计算机术语中是指访问并可能更新数据库中各种数据项的一个程序执行单元(unit)。(2)事务应该具有4个属性:原子性、一致性、隔离性、持久性。这四个属性通常称为ACID特性。原子性(atomicity)。一个事务是一个不可分割的工作单位。比如A向B转账1000元,那么这就一定要保证原子性(要么同时成功,要么同时失败)。一致性…

    2022年10月13日
  • vscode好用的插件「建议收藏」

    1.Chinese(Simplified)LanguagePackforVisualStudioCode(汉化vscode必备)2.BracketPairColorizer(给代码中的括号添加亮色便于区分这里截图有报错是特意便于演示写的多组括号)3.AutoCloseTag(自动补全标签必备)4.AutoRenameTag(修改标签名自动同步修改闭合标签的标签名必备)5.ClassautocompleteforHTML(自动补全cl

发表回复

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

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