贪心算法-MATLAB实现

这篇具有很好参考价值的文章主要介绍了贪心算法-MATLAB实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

贪心算法的基本原理

贪心算法是使所做的选择看起来都是当前最佳的,期望通过所做的局部最优选择来产生出一个全局最优解。

贪心算法的性质

  1. 贪心选择:在做贪心选择时,应满足可行性,即必须满足问题的约束条件。
  2. 局部最优:通过做一系列的选择来给出某一问题的最优解。对算法中的每一个决策点,做一个当时最佳的选择。
  3. 子结构结果:贪心算法所做的当前选择可能要依赖于已经做出的所有选择,但不依赖于有待于做出的选择或子问题的解。

例题

找零钱问题

题目:假设有7种硬币,面值分别为0.01元、0.02元、 0.05元、 0.1元、 0.2元、 0.5元、 1元。要找6.66元,问如何找钱才能使找出的硬币个数最少?
核心思想:每一次找钱都从零钱面值最大的算起,以确保每次找出的硬币数目最少
基本思路:

  1. 读取硬币和零钱的数值
  2. 从面值最大的硬币开始找起,逐步递减直到零钱值为零

MATLAB代码如下:

%贪心算法解决找零钱问题
% greedy algorithm(GA)贪心/贪婪算法
d=[0.01 0.02 0.05 0.5 0.1 0.2 1]%输入零钱面值,存入d数组中
%将数组d排序,使得其零钱面值为从小到大
value=sort(d)
a= input('请输入需要找的零钱数:')%a表示需要找的零钱数
i=length(value)%用length函数计算d数组的长度
while i>0
    if a>=value(i) %从面值最大的开始找,d[i]此时i=6 i的值是最大的,d[i]是最大的
        n=fix(a/value(i))%fix函数用于向下取整,n的含义是需要找的零钱个数
        a=round(a-n*value(i),2)%round保留两位小数
        X=sprintf('找了%d个%.2f元硬币',n,value(i))
        disp(X)
    end
    i=i-1
end

空瓶换酒问题

题目:小区便利店正在促销,用 3 个空酒瓶可以兑换一瓶新酒。你购入了 5 瓶酒。如果喝掉了酒瓶中的酒,那么酒瓶就会变成空的。请你计算最多能喝到多少瓶酒?
核心思想:每一次换酒都尽最大可能换最多的酒
基本思路:

  1. 设置交换规则并读取初值
  2. 记录剩余酒瓶的数量、喝到的酒的数量,当剩余酒瓶已经不能换酒时,停止循环

空瓶换酒问题示意图如下:
贪心算法matlab,贪心算法,matlab,算法MATLAB代码如下:

%贪心算法解决空瓶换酒问题
% greedy algorithm(GA)贪心/贪婪算法
a=1
while a==1
    %购入了 n 瓶酒
    n = input('你现在有几瓶酒?');
    %用 m 个空酒瓶可以兑换一瓶新酒
    m = input('几个酒瓶可以换一瓶酒?');
    if m<=1
        disp('输入错误 请重新输入')
        a=1
    else 
        a=0
    end
end
%初始化
count = n;  % 喝到酒的数目
e = n;  % 空瓶数目
%初始时,空瓶数量等于已有酒的数量,还未开始换酒
while fix(e / m) ~= 0 %fix函数向下取整,当手里有的空瓶数量一瓶酒的换不了了就结束循环
    bottle = fix(e / m);  % 利用当前空瓶最大限度地兑换酒,得到当前酒的数目
    count = count + bottle;  % 更新喝到酒的数目
    e = mod(e,m) + bottle; %更新空瓶数目:空瓶=兑换后剩余空瓶+兑换得到的酒瓶   mod函数:返回 e 除以 m 后的余数
end
X=sprintf('一共可以喝到%d瓶酒',count)
disp(X)

当酒的瓶盖也可以换酒时,则需考虑两个数量的变化,找到最大换酒数量,MATLAB代码如下:

%贪心算法解决空瓶换酒问题2.0% greedy algorithm(GA)贪心/贪婪算法
%初始化
clc;clear;
n=20%共有n瓶酒
m=2%用 m 个空酒瓶可以兑换一瓶新酒
q=3%用q个瓶盖可以换1瓶酒
count = n;  % 喝到酒的数目
e = n;  % 空瓶数目
f = n;  %瓶盖数目
while (fix(e / m) ~= 0 )||(fix(f/q)~=0)%fix函数向下取整,当手里有的空瓶数量一瓶酒的换不了了就结束循环
    if fix(e / m) ~= 0
        bottle_e = fix(e / m) % 利用当前空瓶最大限度地兑换酒,得到当前酒的数目
    end
    if fix(f / q) ~= 0
        bottle_f = fix(f / q)
        % 更新喝到酒的数
    end
    e = mod(e,m) + bottle_e+bottle_f; %更新空瓶数目:空瓶=兑换后剩余空瓶+兑换得到的酒瓶   mod函数:返回 e 除以 m 后的余数
    f = mod(f,q) + bottle_f+bottle_e; %更新瓶盖数目:瓶盖=兑换后剩余瓶盖+兑换得到的瓶盖
    count = count + bottle_e+bottle_f;
    bottle_e=0
    bottle_f=0
end
X=sprintf('最终喝到%d瓶酒',count)%最终喝到酒的瓶数
disp(X)

活动安排问题

题目:设有n个活动a1, a2…, an,每个活动都要求使用同一资源,而同一时间内只允许一个活动使用这一资源。已知活动ai,要求使用该资源的起始时间为si,结束时间为fi,且si<= fi。要求在a1, a2, …, an中选出最大的相容活动子集。
核心思想:按结束时间从早到晚安排活动,每次选择与已选出的活动相容的结束时间尽可能早的活动。以保证每次为资源留下尽可能多的时间以容纳其它活动。
基本思路:

  1. 读取活动的数据并排序
  2. 找出相容活动子集
  3. 输出结果

活动安排问题示意图如下:
贪心算法matlab,贪心算法,matlab,算法MATLAB代码如下:

%贪心算法解决活动安排问题
% greedy algorithm(GA)贪心/贪婪算法
s=[1 2 2 3 5 ]%s为活动开始时间
f=[5 6 8 9 10]%f为活动结束时间,并且s和f一一对应
n=5%n为活动的数量(1,5) (2,6) (2,8) (3,9) (5,10)
%排序,以活动最早结束的时间为标准,将活动排序,结束时间越早,越排在前面
[JL,Index]=sort(f)
f=JL
s=s(Index)
 for i =1:length(f)
     a(i)=[true];
 end
j = 1
for i =2:n
    %如果下一个活动的开始时间大于等于上个活动的结束时间,最关键的语句
    if s(i)>= f(j)
        a(i)= true
        j = i
    else
        a(i) = false
    end
end
  disp('安排的活动有')
for i =1:length(a)
    if a(i)
        X=sprintf('开始时间为%d,结束时间为%d的活动%d',s(i),f(i),i);
        disp(X)
    end
end

贪心算法的局限性

贪心法可以解决一些最优化问题,如:求最小生成树、求哈夫曼编码……对于其他问题,贪心法一般不能得到我们所要求的答案。一旦一个问题可以通过贪心法来解决,那么贪心法一般是解决这个问题的最好办法。 由于贪心法的高效性以及其所求得的答案比较接近最优结果,贪心法也可以用作辅助算法或者直接解决一些要求结果不特别精确的问题。在不同情况,选择最优的解,可能会导致辛普森悖论(Simpson’s Paradox),不一定出现最优的解。文章来源地址https://www.toymoban.com/news/detail-604655.html

到了这里,关于贪心算法-MATLAB实现的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Matlab迭代算法实现

    牛顿迭代法 雅可比迭代法 高斯赛德迭代法 超松弛迭代法(SOR) 共轭迭代法 代码实现案例: 代码实现案例: 代码实现案例: 代码实现案例: 代码实现案例:

    2024年02月14日
    浏览(34)
  • 大津算法的matlab实现

    一、算法功能 ​ 图像分割就是把图像分成若干个特定的、具有独特性质的区域并提出感兴趣目标的技术和过程。它是由图像处理到图像分析的关键步骤。 ​ 大津算法也称最大类间差法,由大津于1979年提出,被认为是图像分割中阈值选取的最佳算法,计算简单,不受图像亮

    2024年02月08日
    浏览(32)
  • 智能优化算法——哈里鹰算法(Matlab实现)

    目录 1 算法简介 2 算法数学模型 2.1.全局探索阶段 2.2 过渡阶段 2.3.局部开采阶段 3 求解步骤与程序框图 3.1 步骤 3.2 程序框图  4 matlab代码及结果 4.1 代码 4.2 结果  哈里斯鹰算法(Harris Hawks Optimization,HHO),是由Ali Asghar Heidari和Seyedali Mrjaili于2019年提出的一种新型仿生智能优化算

    2024年02月13日
    浏览(45)
  • MATLAB算法实战应用案例精讲-【智能优化算法】哈里斯鹰(HHO)(附matlab代码实现)

    目录 前言 算法原理 算法思想 1. 探索阶段 2.探索到开发的转换 3

    2024年02月16日
    浏览(45)
  • 秦九昭算法——MATLAB实现

            对于多项式 而言,要计算时的函数值时,需要进行 次乘法和n次加法,其时间复杂度为.         那我们该用一个什么用的方式来降低其时间复杂度呢? (1条消息) 一套图 搞懂“时间复杂度”_12 26 25的博客-CSDN博客 https://blog.csdn.net/qq_41523096/article/details/82142747?ops_

    2024年02月07日
    浏览(27)
  • 【Matlab系列】基于DCT和置乱算法的视频水印Matlab实现

    Date: 2022.4.5     数字水印技术一般用于版权认证。在实际使用中,嵌入水印的鲁棒性就显得非常重要。通常会采用各种方式进行攻击测试,比如加噪滤波,缩放、旋转、剪切、JPEG压缩等。本文讲述了采用置乱技术进行嵌入水印和提取水印,并加入滤波、剪切、椒盐噪声、

    2024年02月01日
    浏览(46)
  • 聚类算法综述及Matlab实现

    聚类算法是一种无监督学习方法,它将数据集中的对象分组成不同的簇(cluster),使得同一簇内的对象相似度高,而不同簇之间的相似度低。聚类算法在数据挖掘、图像处理、模式识别等领域都有广泛应用。 常用的聚类算法包括K-Means、层次聚类(Hierarchical Clustering)、DBSCAN、Mea

    2024年02月11日
    浏览(39)
  • DBSCAN聚类算法——MATLAB实现

        声明:本文修改自《 数学建模清风 》老师的代码    DBSCAN(Density-Based Spatial Clustering of Applications with Noise)是一个比较有代表性的基于密度的聚类算法。与划分和层次聚类方法不同,它将簇定义为密度相连的点的最大集合,能够把具有足够高密度的区域划分为簇,并可在噪

    2024年02月11日
    浏览(42)
  • Matlab实现Kmeans聚类算法

    kmeans聚类算法是一种迭代求解的聚类分析算法。其实现步骤如下: (1) 随机选取K个对象作为初始的聚类中心 (2) 计算每个对象与各个种子聚类中心之间的距离,把每个对象分配给距离它最近的聚类中心。 (3) 聚类中心以及分配给它们的对象就代表一个聚类。每分配一个样本,聚

    2024年02月02日
    浏览(38)
  • GPSR路由算法的MATLAB实现

    GPSR基于节点地理位置路由信息,采用贪婪策略和右手准则的结合在邻居节点中选择下一跳节点进行数据转发。节点在进行路由选择时,只需知道自己、邻居和目标节点的地理位置信息,无需维护全局网络的链路状态,这在很大程度上降低了网络开销。同时,节点在数据转发时

    2024年01月24日
    浏览(22)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包