博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
贪心算法
阅读量:5842 次
发布时间:2019-06-18

本文共 3448 字,大约阅读时间需要 11 分钟。

1、贪心算法介绍

       贪心算法,又称贪婪法,是寻找最优解算法的常用算法。当面对没有快速算法的问题(NP完全问题)时,贪心算法则可以化解危机,这种方法的模式一般是将问题求解分割成若干步骤,每个步骤都去应用贪心原则,即选取当前状态下最优的选择,每一步都是当前最佳选择,并逐步堆出问题的最优解。贪心算法的每次决策都是以当前状态为基础并依照局部最有利的原则进行选择,不从整体上考虑其他各种可能的情况。生活中我们常听到“人要活在当下”、“看清眼前”,其实这跟贪心算法就是同一个道理,贪心算法在解决问题的策略上目光短浅,只看眼前,不去计较长远与整体。
 

2、贪心算法的基本思想

(1)贪心策略
      首先要确定贪心策略,选择一个方案,定义问题最优解的模型。比如去菜市场买苹果,个大的肯定好吃些,所以每次都从苹果堆里挑选一个最大的作为局部最优解,这时贪心算法的策略就是每次选择当前最大的苹果。有人觉得最红的苹果最好吃,那他的贪心策略就是每次都挑选最红的苹果。
(2)局部最优解
       将问题分解为一系列子问题,一步一步的得到局部问题最优解。例如在上述假设中,第一次从苹果堆里选择一个最大的,第二次再从剩下的苹果堆里选一个最大的,以此类推。
(3)全局最优解
      根据贪心策略,用所有子问题的局部最优解堆叠出全局最优解。
 

3、解决会议安排问题

(1)问题描述
       假如你是一家公司的老总,公司每天都有很多会议要举行,每个会议都有起始时间和结束时间,每个会议进行的时间也不一样,同一时间不会有两个会议同时举行。而你作为一位敬业的老板,你需要争取在有限的时间内参与更多的会议。下图为会议安排表:
(2)问题分析
     从问题描述中可以看出,需要考虑几个点,一是会议的起始时间和结束时间,二是每个会议所占时间,三是要在参与更多的会议,即寻找最优解。这个问题我们可以采用贪心算法来解决。我们应该每次从剩下的会议中选择最早结束的会议,这样可以尽快去参与下一场会议,这样最终就能挑选出能在有限时间内参与更多会议的最优方案。
(3)编码实现
     算法只是对问题求解方法的描述,它不依赖于任何语言,这里使用python来实现:
#会议类class meet:    num=0    begin=0    end=0#所有会议meets=[]#初始化会议列表m=meet()m.num=1m.begin=8m.end=10meets.append(m)m=meet()m.num=2m.begin=9m.end=11meets.append(m)m=meet()m.num=3m.begin=10m.end=15meets.append(m)m=meet()m.num=4m.begin=11m.end=14meets.append(m)m=meet()m.num=5m.begin=13m.end=16meets.append(m)m=meet()m.num=6m.begin=14m.end=17meets.append(m)m=meet()m.num=7m.begin=15m.end=17meets.append(m)m=meet()m.num=8m.begin=17m.end=18meets.append(m)m=meet()m.num=9m.begin=18m.end=20meets.append(m)m=meet()m.num=10m.begin=16m.end=19meets.append(m)import operatorselectmeets=[] #选择参与的会议def selectmeet(meetlist):    cmpfun = operator.attrgetter('end') #按照end进行排序    meetlist.sort(key = cmpfun)    selectmeets.append(meetlist[0]) #先选第一个会议    endtime=meetlist[0].end #会议结束时间    for i in range(1,len(meetlist)):        if endtime<=meetlist[i].begin: #如果结束时间小于该会议的起始时间            selectmeets.append(meetlist[i])            endtime=meetlist[i].end   selectmeet(meets)  for obj in selectmeets:    print(obj.num)       '''打印结果为:    14689'''

4、解决背包问题

(1)问题描述
       假如你是一个小偷,趁天黑去打劫了一家超市,超市里有很多值钱的玩意,但你背的包只能承重12kg,你需要选择一套方案来保证偷出去的东西最值钱。

(2)问题分析
     根据问题描述可以知道这是一个完全可以用贪心算法来解决的问题,每次往背包里塞性价比最高的东西(同等重量下价值更高),直到背包再也塞不下其他东西,这样最终就能实现偷到的东西利益最大。
(3)编码实现
     同样,这里也使用python来实现:

#商品类class good:    name="" #商品名    weight=0  #重量    price=0   #价格    p=0  #性价比goods=[]g=good()g.name="手表"g.weight=2g.price=85g.p=g.price/g.weightgoods.append(g)g=good()g.name="剃须刀"g.weight=3g.price=60g.p=g.price/g.weightgoods.append(g)g=good()g.name="西瓜"g.weight=5g.price=10g.p=g.price/g.weightgoods.append(g)g=good()g.name="篮球"g.weight=1.5g.price=30g.p=g.price/g.weightgoods.append(g)g=good()g.name="可乐"g.weight=1g.price=3.5g.p=g.price/g.weightgoods.append(g)g=good()g.name="香烟"g.weight=2.5g.price=75g.p=g.price/g.weightgoods.append(g)g=good()g.name="茅台"g.weight=1.2g.price=240g.p=g.price/g.weightgoods.append(g)g=good()g.name="烤鸡"g.weight=2.2g.price=22g.p=g.price/g.weightgoods.append(g)g=good()g.name="相机"g.weight=2g.price=2000g.p=g.price/g.weightgoods.append(g)g=good()g.name="袜子"g.weight=1g.price=12g.p=g.price/g.weightgoods.append(g)import operatorselectgoods=[]  #挑选的商品def selectgood(goodlist):    cmpfun=operator.attrgetter('p') #按性价比排序    goodlist.sort(key=cmpfun,reverse=True)    residueweight=12 #背包剩余承重空间    for obj in goodlist:        if residueweight>=obj.weight: #如果总重小于背包承重             selectgoods.append(obj)             residueweight=residueweight-obj.weight  selectgood(goods)for obj in selectgoods:    print(obj.name)'''打印结果为:相机茅台手表香烟剃须刀袜子'''

 

 如有错误,欢迎指正,谢谢!
 

转载于:https://www.cnblogs.com/IAMTOM/p/10283590.html

你可能感兴趣的文章
android设置主题动态背景,终于!微信也能设置主题了,超多半透明动态壁纸随意切换...
查看>>
android 动态添加图片,android – 如何动态添加图像到包含imageview的viewpager?
查看>>
android控制台没有报出错误,Android虚拟机,控制台Console报错几例及解决办法
查看>>
android 检测应用程序是否正在启动项,android判断应用是否已经启动的实例
查看>>
android wms各个类的作用,Android APP/AMS/WMS之间交互总结
查看>>
android n改铃声,C# NAudio 实现剪切MP3铃声
查看>>
android vrs技术,步步高 vivo V1/Y1 智能手机音质测评报告 VRS[vivo signal
查看>>
android模块化 osgi,基于OSGi的Android应用模块动态加载框架设计与实现
查看>>
html-5表白神器源码,C# 表白神器源码(winform)
查看>>
war部署到tomcat 用户目录 public_html~,在Tomcat中部署Web项目的操作方法(必看篇)
查看>>
html添加悬浮图片,HTML5和jQuery制作网页灰度图片悬浮效果_js
查看>>
1、取得/etiantian文件的权限对应的数字(考试题答案系列)
查看>>
《专业嵌入式软件开发》的样章、建议和勘误
查看>>
决定员工发展命运的34条重要行为规范
查看>>
网管到底要学什么(一)
查看>>
红帽集群套件RHCS四部曲(测试篇)
查看>>
企业级 布署 vmvare Esxi 5.0.0 从零开始教程 (二) vSphere clinet 安装
查看>>
一个cp命令引发的mongodb大量慢查询
查看>>
C#常用文件操作
查看>>
Windows Server 2016-图形化迁移FSMO角色
查看>>