贪心算法(greedy algorithm,又称贪婪算法)详解(附例题)

news/2024/4/24 15:14:10/文章来源:https://blog.csdn.net/Mrsgflmx/article/details/136553216
目录
    • 基本思想
    • 一)概念
    • 二)找出全局最优解的要求
    • 三)求解时应考虑的问题
    • 四)基本步骤
    • 五)贪心策略选择
    • 六)实际应用
      • 1.零钱找回问题
      • 2.背包问题
      • 3.哈夫曼编码
      • 4.单源路径中的Djikstra算法
      • 5.最小生成树Prim算法

基本思想

贪心算法(Greedy Algorithm)是一种在求解问题时,每一步都选择当前最优解,以期望最终得到全局最优解的算法思想。贪心算法的基本思想可以总结为“每一步都做出一个局部最优的选择,最终就能得到全局最优解”。

贪心算法通常包含以下关键步骤:

找到可选的子问题: 首先,将原问题拆分成一系列可选的子问题或决策。

找到局部最优解: 对每个子问题,找到一个局部最优解。这个局部最优解应该是一个贪心选择,即在当前状态下选择最优的方式。

合并子问题的解: 将各个子问题的局部最优解合并起来,得到原问题的解。

检查解的有效性: 最后,检查得到的解是否满足问题的约束和要求。如果满足,就认为得到了问题的解。

贪心算法适用于一些特定类型的问题,通常要求问题具有贪心选择性质(即每一步的选择都是最优的),以及最优子结构性质(即问题的最优解可以通过子问题的最优解推导得出)。然而,贪心算法不一定能够求解所有问题,有些问题可能需要更复杂的算法来解决。

经典的贪心算法问题有找零钱问题、活动选择问题、背包问题中的部分背包等。贪心算法在求解这些问题时,通常能够得到接近最优解的结果,但并不保证一定能够得到全局最优解。

总之,贪心算法是一种基于每一步的局部最优选择来求解问题的思想,适用于一些满足贪心选择性质和最优子结构性质的问题。

一)概念

贪心算法(Greedy Alogorithm)又叫登山算法,它的根本思想是逐步到达山顶,即逐步获得最优解,是解决最优化问题时的一种简单但是适用范围有限的策略。

贪心算法没有固定的框架,算法设计的关键是贪婪策略的选择。贪心策略要无后向性,也就是说某状态以后的过程不会影响以前的状态,只与当前状态有关。

贪心算法是对某些求解最优解问题的最简单、最迅速的技术。某些问题的最优解可以通过一系列的最优的选择即贪心选择来达到。但局部最优并不总能获得整体最优解,但通常能获得近似最优解

在每一步贪心选择中,只考虑当前对自己最有利的选择,而不去考虑在后面看来这种选择是否合理。

二)找出全局最优解的要求

在遇见问题时如何确定是否可以使用贪心算法解决问题,那么决定一个贪心算法是否能找到全局最优解的条件是什么呢?其实就是以下两点:

  • 最优子结构(optimal subproblem structure,和动态规划中的是一个概念)
  • 最优贪心选择属性(optimal greedy choice property)

三)求解时应考虑的问题

1.候选集合S
为了构造问题的解决方案,有一个候选集合C作为问题的可能解,问题的最终解均取自于候选集合C。
2.解集合S
随着贪心选择的进行,解集合不断扩展,直到构成一个满足问题的完整解。
3.解决函数solution
检查解集合是否构成问题的完整解。
4.选择函数select
即贪心策略,这是贪心算法的关键,它指出哪个候选对象有希望构成成问题的解。
5.可行函数feasible
检查解集合中加入一个候选对象是否可行,即解集合扩展后是否满足约束条件。

四)基本步骤

贪心算法使用基本步骤:
1.从问题的某个初始解出发
2.采用循环语句,当可以向求解目标前进一步时,就根据局部最优策略,得到一个部分解,缩小问题的范围或规模。
3.将所有的部分解综合起来,得到问题的最终解。

五)贪心策略选择

贪心算法的原理是通过局部最优来达到全局最优,采用的是逐步构造最优解的方法。在每个阶段,都做出一个看上去最优的,决策一旦做出,就不再更改。

要选出最优解可不是一件容易的事,要证明局部最优为全局最优,要进行数学证明,否则就不能说明为全局最优。

很多问题表面上看来用贪心算法可以找到最优解,实际上却把最优解给漏掉了。这就像现实生活中的“贪小便宜吃大亏”。所以我们在解决问题的时候,一定要谨慎使用贪心算法,一定要注意这个问题适不适合采用贪心算法

贪心算法很多时候并不能达到全局最优,为什么我们还要使用它呢?

因为在很多大规模问题中,寻找最优解是一件相当费时耗力的事情,有时候付出大量人力物力财力后,回报并不与投入成正比。在这个时候选择相对最优的贪心算法就比较经济可行了。有的问题对最优的要求不是很高,在充分衡量付出和回报后,选择贪心算法未尝不是一种不错的选择呢。

六)实际应用

1.零钱找回问题

这个问题在我们的日常生活中就更加普遍了。假设1元、2元、5元、10元、20元、50元、100元的纸币分别有c0, c1, c2, c3, c4, c5, c6张。现在要用这些钱来支付K元,至少要用多少张纸币?用贪心算法的思想,很显然,每一步尽可能用面值大的纸币即可。在日常生活中我们自然而然也是这么做的。在程序中已经事先将Value按照从小到大的顺序排好。
下面展示一些 内联代码片

#include<iostream>
#include<algorithm>
using namespace std;
const int N=7; 
int Count[N]={3,0,2,1,0,3,5};
int Value[N]={1,2,5,10,20,50,100};int solve(int money) 
{int num=0;for(int i=N-1;i>=0;i--) {int c=min(money/Value[i],Count[i]);money=money-c*Value[i];num+=c;}if(money>0) num=-1;return num;
}int main() 
{int money;cin>>money;int res=solve(money);if(res!=-1) cout<<res<<endl;else cout<<"NO"<<endl;
}
2.背包问题

在 从零开始学动态规划中我们已经谈过三种最基本的背包问题:零一背包,部分背包,完全背包。很容易证明,背包问题不能使用贪心算法。然而我们考虑这样一种背包问题:在选择物品i装入背包时,可以选择物品的一部分,而不一定要全部装入背包。这时便可以使用贪心算法求解了。计算每种物品的单位重量价值作为贪心选择的依据指标,选择单位重量价值最高的物品,将尽可能多的该物品装入背包,依此策略一直地进行下去,直到背包装满为止。在零一背包问题中贪心选择之所以不能得到最优解原因是贪心选择无法保证最终能将背包装满,部分闲置的背包空间使每公斤背包空间的价值降低了。在程序中已经事先将单位重量价值按照从大到小的顺序排好。

#include<iostream>   
using namespace std;   
const int N=4;  
void knapsack(float M,float v[],float w[],float x[]);  int main()  
{  float M=50;//背包所能容纳的重量   float w[]={0,10,30,20,5};//每种物品的重量  float v[]={0,200,400,100,10};  //每种物品的价值 float x[N+1]={0};  //记录结果的数组 knapsack(M,v,w,x);  cout<<"选择装下的物品比例:"<<endl;  for(int i=1;i<=N;i++) cout<<"["<<i<<"]:"<<x[i]<<endl;  
}  void knapsack(float M,float v[],float w[],float x[])  
{  int i;  //物品整件被装下  for(i=1;i<=N;i++){  if(w[i]>M) break;   x[i]=1;  M-=w[i];  }   //物品部分被装下  if(i<=N) x[i]=M/w[i];   
} 
3.哈夫曼编码

假设有一系列的字符,我们希望用一些二进制码来代替这些字符以进行数据压缩,使得压缩后的总比特数最小。哈夫曼编码正是这样一样压缩数据的方式。

在这里插入图片描述

如果我们已知各字符在文本中的出现频率,考虑到为了让压缩后的数据更小,我们直觉是让出现频率高的字符用尽可能短的编码,而出现频率高的则可以用更长的编码。

哈夫曼编码的解决方案是这样的:不断找到当前出现频率最小的两个结点(字符或频率),将它们结合,作为一个新生成的结点的左右子结点,并将新生成的结点继续放入比较,直到没有落单的字符。

过程演示

该贪心算法针对这个问题得到的解是最优的。

4.单源路径中的Djikstra算法

求A到其他节点的最短路径:
在这里插入图片描述
维护三个东西,从A到其他节点的路径长度队列Queue,数组visited用于记录已保存最短路径的节点,数组res用于记录节点A到其他节点的最短路径。
开始时,Queue中只有A节点自己,三组数据如下:
Queue:[(A, 0)] 起始节点为A,A到A的距离为0
visited:[true, false,false,false,false] A节点是已经访问过的节点,是true,其他节点是false
res:[0,∞,∞,∞,∞] A到自己的距离是0,到其他节点的距离目前是∞

将以A为起点的路径加入到Queue中,2和4是节点D和B的路径权重:
Queue:[(D, 2), (B, 4)]
visited:[true, false,false,false,false]
res:[0,∞,∞,∞,∞]
在Queue中,路径最短的是D,取出D,更新三组数据:
Queue:[(B, 3), (C, 3), (E, 9)]

因为A-D-B的路径权重为3小于A-B的路径权重4,所以更新一下B的路径权重。
visited:[true,false,false,true,false]
res: [0,∞, ∞,2,∞]

取出B,更新三组数据:
Queue: [(C,3), (E, 9)]
visited: [true,true,false,true,false]
res: [0,3, ∞,2, ∞]

取出C,更新三组数据:
Queue:[(E, 6)]
visited: [true,true,true,true,false]
res: [0,3, 3,2, ∞]

取出E,更新三组数据:
Queue:[]
visited: [true,true,true,true,true]
res: [0,3, 3,2, 6]

至此,Queue队列空,计算过程结束。

5.最小生成树Prim算法

prim算法(读者可以将其读作“普里姆算法”)用来解决最小生成树问题,其基本思想是对图G(V,E)设置集合S,存放已被访问的顶点,然后每次从集合V-S中选择与集合S的最短距离最小的一个顶点(记为u),访问并加入集合S。之后,令顶点u为中介点,优化所有从u能到达的顶点v与集合S之间的最短距离。这样的操作执行n次(n为顶点个数),直到集合S已包含所有顶点。可以发现,prim算法的思想与最短路径中Dijkstra算法的思想几乎完全相同,只是在涉及最短距离时使用了集合S代替 Dijkstra算法中的起点s。

在这里插入图片描述

①将地图上的所有边都抹去,只有当访问一个顶点后オ把这个顶点顶点连接的边显现(这点和Dijkstra算法中相同)。

②将已访问的顶点置于ー个巨型防护罩中。可以沿着这个防护罩连接的边去访问未到达的顶点

③在地图中的顶点V(0≤i≤5)上记录顶点V与巨型防护罩之间的最短距离(即V与每个访问的顶点之间距离的最小值)。由于在①把所有边都抹去了,因此在初始状态下只在顶点V0上标记0,而其他顶点都标记无穷大(记为INF)。为了方便叙述,在下文中某几处出现的最短距离都是指从顶点V与当前巨型防护罩之间的最短距离。

下面是行动策略:

①由于要访问六个顶点,因此将②③步骤执行六次,每次访问一个顶点(如果是n个顶点,那么就执行n次)。

②每次都从还未访问的顶点中选择与当前巨型防护罩最近的顶点(记为Vk(0≤k≤5)),使用“爆裂模式”的能力恢复这条最近的边(并成为最小生成树中的一条边),前往访问。

③访问顶点Vk后,将Vk加入巨型防护罩中,开放地图上Vk连接的所有边,并査看以Vk作为巨型防护罩连接外界的接口的情况下,能否利用Vk刚开放的边使某些还未访问的顶点与巨型防护罩的最短距离变小。如果能,则将那个最短距离覆盖到地图对应的顶点上。

另外,为了得到最小生成树的边权之和,需要在访问顶点之前设置一个初值为0的变量sum,并在攻打过程中将加入最小生成树中的边的边权累加起来。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_999460.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

从 iPhone 15/15 Pro 恢复丢失数据的 3 种方法

毫无疑问&#xff0c; iPhone 15 是迄今为止最令人印象深刻的 iPhone 。另一方面&#xff0c;我们知道&#xff0c;设备上保存的数据无论多么可靠&#xff0c;在设备使用过程中都可能因各种原因而丢失。 由于这些设备的性质&#xff0c;您在使用 iPhone 15、iPhone 15 Pro 或 …

【Spring底层原理高级进阶】Spring Kafka:实时数据流处理,让业务风起云涌!️

&#x1f389;&#x1f389;欢迎光临&#x1f389;&#x1f389; &#x1f3c5;我是苏泽&#xff0c;一位对技术充满热情的探索者和分享者。&#x1f680;&#x1f680; &#x1f31f;特别推荐给大家我的最新专栏《Spring 狂野之旅&#xff1a;从入门到入魔》 &#x1f680; 本…

微服务技术栈SpringCloud+RabbitMQ+Docker+Redis+搜索+分布式(三):Docker

文章目录 一、基本介绍二、环境配置三、Docker基本操作3.1 镜像操作3.2 容器操作3.2.1 演示命令run、ps、logs3.2.2 演示命令exec、rm、exit&#xff08;退出&#xff09;3.3 数据卷3.3.1 直接挂载3.3.2 宿主机挂载3.3.3 两种方式的对比 四、Dockerfile自定义镜像五、Docker-Co…

【开源】SpringBoot框架开发固始鹅块销售系统

目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块2.1 数据中心模块2.2 鹅块类型模块2.3 固始鹅块模块2.4 鹅块订单模块2.5 评论管理模块 三、系统设计3.1 用例设计3.2 数据库设计3.2.1 鹅块类型表3.2.2 鹅块表3.2.3 鹅块订单表3.2.4 鹅块评论表 四、系统展示五、核心代码5.…

上门服务小程序|上门服务系统成品功能包含哪些?

随着移动互联网的快速发展&#xff0c;上门服务小程序成为了一种创新的家政服务模式。它不仅为用户带来了极大的便利&#xff0c;还能在提高服务效率和质量方面发挥作用。通过上门服务小程序&#xff0c;用户可以轻松预约按摩或理疗服务&#xff0c;无需繁琐操作&#xff0c;只…

QT中使用QProcess执行命令,实时获取数据,例如进度条

前言 因为之前写了一个接收和发送文件的脚本&#xff0c;然后又需要获取进度&#xff0c;同步到进度条中。 效果&#xff1a; 使用正则匹配&#xff0c;获取命令行命令中的以下数据&#xff0c;然后同步到进度条 源码demo&#xff1a; 非完整代码&#xff1a; #include <Q…

2023最新群智能优化算法:巨型犰狳优化算法(Giant Armadillo Optimization,GAO)求解23个基准函数(提供MATLAB代码)

一、巨型犰狳优化算法 巨型犰狳优化算法&#xff08;Giant Armadillo Optimization&#xff0c;GAO&#xff09;由Omar Alsayyed等人于2023年提出&#xff0c;该算法模仿了巨型犰狳在野外的自然行为。GAO设计的基本灵感来自巨型犰狳向猎物位置移动和挖掘白蚁丘的狩猎策略。GAO…

MySQL安装使用(mac)

目录 一、下载MySQL 二、环境变量 三、启动 MySql 四、初始化密码设置 一、下载MySQL 打开 MySql 官方下载页面 我是macOS12&#xff0c;所以选择了8.0.30 下载完成之后&#xff0c;打开安装&#xff0c;一直下一步安装完成&#xff0c;在最后安装完成时&#xff0c;会弹出…

Spring Boot搭建入门

Spring Boot简介 Spring Boot是对Spring进行的高度封装&#xff0c;是对Spring应用开发的高度简化版&#xff0c;是Spring技术栈的综合整合&#xff0c;是J2EE的一站式解决方案。想要精通Spring Boot的前提是需要熟悉Spring整套技术栈原理与内容。 Spring Boot的优点&#xf…

粉嘟嘟的免费wordpress模板

粉色好看的wordpress免费模板&#xff0c;用免费wordpress模板也可以搭建网站。 https://www.wpniu.com/themes/11.html

typescript学习(更新中)

目录 开发环境搭建类型如何声明有哪些类型编译配置文件 开发环境搭建 npm i -g typescripttsc检查是否安装成功 类型如何声明 // 先声明再赋值 let a: number a 1// 直接赋值 let b 1function sum(a: number, b: number): number {return a b } console.log(sum(1, 2))有…

遥感领域的AI革命:ChatGPT与成像光谱的完美结合

随着科技的飞速发展&#xff0c;人工智能&#xff08;AI&#xff09;已逐渐渗透到各个领域&#xff0c;为传统行业带来了前所未有的变革。其中&#xff0c;遥感技术作为观测和解析地球的重要手段&#xff0c;正逐渐与AI技术相结合&#xff0c;为地球科学研究与应用提供了全新的…

Zynq—AD9238数据采集DDR3缓存千兆以太网发送实验(二)

Zynq—AD9238数据采集DDR3缓存千兆以太网发送实验&#xff08;前导&#xff09; Zynq—AD9238数据采集DDR3缓存千兆以太网发送实验&#xff08;一&#xff09; Zynq—AD9238数据采集DDR3缓存千兆以太网发送实验&#xff08;三&#xff09; 五、实验目的 本次实验使用电脑上的…

锐科达SV-7043VP 网络有源吸顶喇叭 POE供电ip广播吸顶喇叭

锐科达SV-7043VP 网络有源吸顶喇叭 POE供电ip广播吸顶喇叭 该设备配备了10/100M以太网接口&#xff0c;内置了高品质扬声器&#xff0c;通过内置的功放和喇叭输出&#xff0c;可提供高达10W的音效功率。SV-7043VP作为SIP系统的播放终端&#xff0c;适用于各种需要广播播放的场…

【uniapp】uniapp小程序中实现拍照同时打开闪光灯的功能,拍照闪光灯实现

一、需求前提 特殊场景中&#xff0c;需要拍照的同时打开闪光灯&#xff0c;&#xff08;例如黑暗场景下的设备维护巡检功能&#xff09;。 起初我是用的uviewui中的u-upload组件自带的拍照功能&#xff0c;但是这个不支持拍照时打开闪光灯&#xff0c;也不支持从通知栏中打开…

【排序】详解冒泡排序

一、思想 冒泡排序的基本思想是利用两两比较相邻记录的方式&#xff0c;通过一系列的比较和交换操作&#xff0c;使得较大或较小的元素逐渐移动到数列的一端。在每一轮的排序过程中&#xff0c;都会从数列的起始位置开始&#xff0c;对相邻的元素进行比较&#xff0c;如果它们…

Using WebView from more than one process

关于作者&#xff1a;CSDN内容合伙人、技术专家&#xff0c; 从零开始做日活千万级APP。 专注于分享各领域原创系列文章 &#xff0c;擅长java后端、移动开发、商业变现、人工智能等&#xff0c;希望大家多多支持。 未经允许不得转载 目录 一、导读二、概览三、问题过程源码追踪…

同时上内网和外网(笔记本自带的无线网卡和另外购置无线网卡)

同时上内网和外网 两无线网卡连接内外网插入新网卡后&#xff0c;重命名网卡名字信息收集IPv4属性设置永久路由 两无线网卡连接内外网 插入新网卡后&#xff0c;重命名网卡名字 两网卡同时连接网络&#xff0c;使用ipconfig /all 获取信息&#xff0c;整理如下&#xff1a; 下…

「2024指南」tf卡格式化了数据怎么恢复?

咨询&#xff1a;我把TF卡插入了我的安卓手机并将其设为内部存储&#xff0c;然后保存了大量重要资料。不久后&#xff0c;我无意中将TF卡拔出。当我再次插入时&#xff0c;手机提示必须格式化TF卡。我不小心点击了格式化选项&#xff0c;导致里面所有重要的资料都不见了。请问…

Java List集合取交集的八种不同实现方式

码到三十五 &#xff1a; 个人主页 心中有诗画&#xff0c;指尖舞代码&#xff0c;目光览世界&#xff0c;步履越千山&#xff0c;人间尽值得 ! 在Java中&#xff0c;取两个List集合的交集可以通过多种方式实现&#xff0c;包括使用Java 8的Stream API、传统的for循环遍历、使…