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

2024-03-09 07:52

本文主要是介绍贪心算法(greedy algorithm,又称贪婪算法)详解(附例题),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录
    • 基本思想
    • 一)概念
    • 二)找出全局最优解的要求
    • 三)求解时应考虑的问题
    • 四)基本步骤
    • 五)贪心策略选择
    • 六)实际应用
      • 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,并在攻打过程中将加入最小生成树中的边的边权累加起来。

这篇关于贪心算法(greedy algorithm,又称贪婪算法)详解(附例题)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/790012

相关文章

Spring Security基于数据库验证流程详解

Spring Security 校验流程图 相关解释说明(认真看哦) AbstractAuthenticationProcessingFilter 抽象类 /*** 调用 #requiresAuthentication(HttpServletRequest, HttpServletResponse) 决定是否需要进行验证操作。* 如果需要验证,则会调用 #attemptAuthentica

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

OpenHarmony鸿蒙开发( Beta5.0)无感配网详解

1、简介 无感配网是指在设备联网过程中无需输入热点相关账号信息,即可快速实现设备配网,是一种兼顾高效性、可靠性和安全性的配网方式。 2、配网原理 2.1 通信原理 手机和智能设备之间的信息传递,利用特有的NAN协议实现。利用手机和智能设备之间的WiFi 感知订阅、发布能力,实现了数字管家应用和设备之间的发现。在完成设备间的认证和响应后,即可发送相关配网数据。同时还支持与常规Sof

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

usaco 1.3 Barn Repair(贪心)

思路:用上M块木板时有 M-1 个间隙。目标是让总间隙最大。将相邻两个有牛的牛棚之间间隔的牛棚数排序,选取最大的M-1个作为间隙,其余地方用木板盖住。 做法: 1.若,板(M) 的数目大于或等于 牛棚中有牛的数目(C),则 目测 给每个牛牛发一个板就为最小的需求~ 2.否则,先对 牛牛们的门牌号排序,然后 用一个数组 blank[ ] 记录两门牌号之间的距离,然后 用数组 an

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

秋招最新大模型算法面试,熬夜都要肝完它

💥大家在面试大模型LLM这个板块的时候,不知道面试完会不会复盘、总结,做笔记的习惯,这份大模型算法岗面试八股笔记也帮助不少人拿到过offer ✨对于面试大模型算法工程师会有一定的帮助,都附有完整答案,熬夜也要看完,祝大家一臂之力 这份《大模型算法工程师面试题》已经上传CSDN,还有完整版的大模型 AI 学习资料,朋友们如果需要可以微信扫描下方CSDN官方认证二维码免费领取【保证100%免费