详解贪心算法

贪心算法(Greedy Algorithm) 概述:

贪心算法是一种在求解最优化问题时采取的一种常用算法策略。贪心算法的基本思想是,每次选择当前情况下的局部最优解,并相信这个局部最优解能够导致全局最优解。贪心算法通过迭代的方式一步步地构建最优解,并不进行回溯。

贪心算法的一般步骤:

1. 将问题分解成多个子问题;
2. 对每个子问题,确定一个最优解;
3. 对每个子问题的最优解进行合并,得到原问题的最优解。


贪心算法的正确性需要满足两个条件:

1.最优子结构:问题的最优解能够由子问题的最优解组合而成。
2. 贪心选择性:通过局部最优选择能够得到全局最优解。


贪心算法适用的问题一般具有以下特点:

1. 子问题的最优解能够推导出原问题的最优解;
2. 子问题的最优解构成原问题的最优解时,原问题的最优解也能由它推导出。

贪心算法的优点是简单、高效,时间复杂度通常较低。然而,贪心算法并不适用于所有问题,有些问题需要使用其他更复杂的算法来求解。在使用贪心算法时,需要仔细分析问题的特点并证明贪心策略的正确性。


由于贪心是一种思想,没有具体的算法模板,而且贪心一般不会单独作为一种算法出现在题目中,一般会跟其他算法结合在一起出现。例如:动态规划、递归、高级数据结构等。在此基础上保证每一步时最优解的情况下就可以得到最优的答案。下面我们将以例题的形式让大家来了解这种思想。


例题一: 

AcWing 3769. 移动石子

题目:

一共有 n 个箱子排成一排,从左到右依次编号为 1∼n。

其中,第 i 号箱子中放有 ai个石子。

现在,你可以进行最多 d 次操作。

每次操作可以将一个石子从一个箱子移动至另一个与其相邻的箱子里。

我们希望通过合理操作使得 1 号箱子内的石子数量尽可能大。

请问,这个最大可能值是多少?

输入格式

第一行包含整数 T,表示共有 T 组测试数据。

每组数据第一行包含两个整数 n和 d。

第二行包含 n 个整数 a1,a2,…,an。

输出格式

每组数据输出一行结果,表示答案。

数据范围

1≤T≤100,
1≤n,d≤100,
0≤ai≤100.

输入样例:
3
4 5
1 0 3 2
2 2
100 1
1 8
0
输出样例:
3
101
0

解题思路:

这个题很明显贪心思想,要让第一个箱子尽可能多的石子,在操作次数的限制下,我们最优解,要从第二个箱子开始贪心,第二个、第三个...,这样可以使操作次数尽可能的少。

 


AC代码:
#include<iostream>
using namespace std;
const int N=105;
int t,n,d;
int a[N];
int main(){cin>>t;while(t--){cin>>n>>d;for(int i=1;i<=n;i++)cin>>a[i];int k=2;while(d){if(k>n)break;if(d>=a[k]*(k-1)){a[1]+=a[k];d-=a[k]*(k-1);}else{a[1]+=d/(k-1);d=0;}k++;}cout<<a[1]<<endl;}return 0;
}

例题二:

洛谷 P1007 独木桥

题目背景

战争已经进入到紧要时间。你是运输小队长,正在率领运输部队向前线运送物资。运输任务像做题一样的无聊。你希望找些刺激,于是命令你的士兵们到前方的一座独木桥上欣赏风景,而你留在桥下欣赏士兵们。士兵们十分愤怒,因为这座独木桥十分狭窄,只能容纳 1 个人通过。假如有 2 个人相向而行在桥上相遇,那么他们 2 个人将无法绕过对方,只能有 1 个人回头下桥,让另一个人先通过。但是,可以有多个人同时呆在同一个位置。

题目描述

突然,你收到从指挥部发来的信息,敌军的轰炸机正朝着你所在的独木桥飞来!为了安全,你的部队必须撤下独木桥。独木桥的长度为 L,士兵们只能呆在坐标为整数的地方。所有士兵的速度都为 1,但一个士兵某一时刻来到了坐标为 0 或 L+1 的位置,他就离开了独木桥。

每个士兵都有一个初始面对的方向,他们会以匀速朝着这个方向行走,中途不会自己改变方向。但是,如果两个士兵面对面相遇,他们无法彼此通过对方,于是就分别转身,继续行走。转身不需要任何的时间。

由于先前的愤怒,你已不能控制你的士兵。甚至,你连每个士兵初始面对的方向都不知道。因此,你想要知道你的部队最少需要多少时间就可能全部撤离独木桥。另外,总部也在安排阻拦敌人的进攻,因此你还需要知道你的部队最多需要多少时间才能全部撤离独木桥。

输入格式

第一行共一个整数 L,表示独木桥的长度。桥上的坐标为 1,2,⋯ L。

第二行共一个整数 N,表示初始时留在桥上的士兵数目。

第三行共有 N 个整数,分别表示每个士兵的初始坐标。

输出格式

共一行,输出 2 个整数,分别表示部队撤离独木桥的最小时间和最大时间。2 个整数由一个空格符分开。


解题思路:

这个题看似显得很累赘,但是做过此类型题的一眼就能看穿,在《挑战程序设计竞赛》这本书上就有详细的解释,当然它们是蚂蚁过桥为背景。解这题的关键在于最大值的求解,我们知道最小值就是在独木桥两边的士兵直接往两端走就可以,走左边还是右边min一下,因为要求所有部队通过所以在所有值里面去一个最大值。对于最大时间的求解,那么我就让靠近左边的人往右边走,靠经右边的人往左边走,如果两个人碰头时,它们可以交换灵魂继续前进,这是《挑战程序设计竞赛》上思想,意思就是我变成他继续前进,他变成我继续前进,最后是对结果没有影响的。那么最大时间就是在最大值里面取一个最大值。

综上所述,最小时间是最小值里面的最大值,最大时间是最大值里面的最大值。


AC代码:
#include<iostream>
#include<algorithm>
using namespace std;
const int N=5e3+5;
int n,l,x;
int a[N];
int main(){cin>>l>>n;for(int i=0;i<n;i++){cin>>a[i];}sort(a,a+n);//先排序int minx=0;int maxx=0;for(int i=0;i<n;i++){minx=max(min(a[i],l+1-a[i]),minx);//最小时间maxx=max(maxx,max(a[i],l+1-a[i]));//最大时间}cout<<minx<<" "<<maxx<<endl;return 0;
}

例题三: 

AcWing 507. 积木大赛

题目:

春春幼儿园举办了一年一度的“积木大赛”。

今年比赛的内容是搭建一座宽度为 n 的大厦,大厦可以看成由 n 块宽度为 1 的积木组成,第 i 块积木的最终高度需要是 hi。

在搭建开始之前,没有任何积木(可以看成块高度为 0 的积木)。

接下来每次操作,小朋友们可以选择一段连续区间 [L,R],然后将第 L 块到第 R 块之间(含第 L 块和第 R 块)所有积木的高度分别增加 1。

小 M 是个聪明的小朋友,她很快想出了建造大厦的最佳策略,使得建造所需的操作次数最少。

但她不是一个勤于动手的孩子,所以想请你帮忙实现这个策略,并求出最少的操作次数

输入格式

输入包含两行,第一行包含一个整数 n,表示大厦的宽度。 

第二行包含 n 个整数,第 i 个整数为 hi。

输出格式

仅一行,即建造所需的最少操作数。

数据范围

1≤n≤105,
0≤hi≤10000

输入样例:
5
2 3 4 1 2
输出样例:
5

解题思路:

这可不是一道纯正的贪心,因为读完题就知道是差分了,但是为什么还要归到贪心里面,因为贪心是一种思想,上面三个题目都涉及到了最大、最小,一般这种就有贪心思想了,当然,这一个题,会了差分就迎刃而解了,具体的贪心还是体现在算法操作上,比如这个题中间的数最大,那么每次选择区间加一都尽量选上这个数,这样可以使操作次数最小。


AC代码:
#include<iostream>
using namespace std;
int n,ans;
const int N=1e5+5;
int h[N];
int main(){cin>>n;for(int i=1;i<=n;i++){cin>>h[i];}for(int i=n+1;i>=1;i--){h[i]=h[i]-h[i-1];//差分数组}for(int i=1;i<=n+1;i++){if(h[i]>0){ans+=h[i];}}cout<<ans<<endl;return 0;
}

其他例题:

第十四届蓝桥杯省赛大学C组(C/C++)三国游戏_c语言三国游戏-CSDN博客

AcWing 4262. 空调(每日一题)-CSDN博客

AcWing 1262. 鱼塘钓鱼(每日一题)-CSDN博客

AcWing 505. 火柴排队(每日一题)-CSDN博客


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

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

相关文章

SpringBoot3里的文件上传

需求分析&#xff1a; 在用户更换头像或者添加文章时&#xff0c;都需要携带一个图片的URL访问地址。当用户访问文件上传接口将图片的数据上传成功后&#xff0c;服务器会返回一个地址。我们后台需要提供一个文件上传的接口&#xff0c;用来接收前端提交的文件的数据并且返回文…

七夕情人节礼物有哪些走心礼物推荐,盘点惊喜爆棚的四大礼物分享

随着浪漫的七夕情人节的临近&#xff0c;恋人们开始寻找那些能够传达他们挚爱与深情的独特礼物&#xff0c;一份有心的礼物不仅能够成为情感的使者&#xff0c;还能在这一天为爱情增添更多甜蜜与回忆&#xff0c;在这个充满传说与浪漫的节日里&#xff0c;我们精心挑选了一系列…

查询表信息时有一个数据为null相关解决

查询的时候varchar类型的username一直查不到为null,这个问题干了我好久 当时我以为是连接mysql数据库的时候没有在url后面添加添加指定字符的编码、解码格式的参数约束.然后经过分析发现 我创建的这个Account对象 直接上结果&#xff0c;问题出在了setUsername()方法上 错误…

Scrapy入门篇

免责声明 本文的爬虫知识仅用于合法和合理的数据收集&#xff0c;使用者需遵守相关法律法规及目标网站的爬取规则&#xff0c;尊重数据隐私&#xff0c;合理设置访问频率&#xff0c;不得用于非法目的或侵犯他人权益。因使用网络爬虫产生的任何法律纠纷或损失&#xff0c;由使用…

用Java手写jvm之模拟方法调用指令invokexxx和方法返回指令xreturn

写在前面 源码 。 本文一起看下方法调用相关的指令invokexxx以及方法返回&#xff08;栈帧弹出线程栈&#xff09;相关的指令xReturn 。 1&#xff1a;正文 因为invokexxx指令和普通的指令不同&#xff0c;会创建一个新的栈帧&#xff0c;并压倒操作数栈中&#xff0c;所以我…

【python】Python中实现定时任务常见的几种方式原理分析与应用实战

✨✨ 欢迎大家来到景天科技苑✨✨ &#x1f388;&#x1f388; 养成好习惯&#xff0c;先赞后看哦~&#x1f388;&#x1f388; &#x1f3c6; 作者简介&#xff1a;景天科技苑 &#x1f3c6;《头衔》&#xff1a;大厂架构师&#xff0c;华为云开发者社区专家博主&#xff0c;…

【OpenCV C++20 学习笔记】腐蚀和膨胀

腐蚀和膨胀 形态学原理膨胀腐蚀 代码实现膨胀函数腐蚀函数运行结果 形态学原理 腐蚀和膨胀通常有以下用途&#xff1a; 去除噪音分离或合并图像中的元素找出图片上的强度的极大值区域和极小值区域 以下图作为原始图片&#xff1a; 膨胀 用核 B B B来扫描图像 A A A&#xff…

VBA学习(22):动态显示日历

这是在ozgrid.com论坛上看到的一个贴子&#xff0c;很有意思&#xff0c;本来使用公式是可以很方便在工作表中实现日历显示的&#xff0c;但提问者因其需要&#xff0c;想使用VBA实现动态显示日历&#xff0c;即根据输入的年份和月份在工作表中显示日历。 下面是实现该效果的VB…

喜报!DAP-seq文章6连发,总IF 95.2

2024年4月29日&#xff0c;河北农业大学林学院李保国山区产业开发与林果产业创新团队与园艺学院田义教授团队联合西北农林科技大学马锋旺教授团队及沈阳农业大学马跃教授团队在Plant Biotechnology Journal&#xff08;影响因子10.1&#xff09;上发表了题为“The MdVQ37-MdWRK…

2024最新版Python基础入门学习路线

Python基础入门学习路线可以概括为以下几个阶段&#xff0c;每个阶段都包含了关键的学习内容和目标&#xff1a; 一、Python语言基础 1. 初识Python语言 Python语言概述&#xff1a;了解Python的起源、特点、应用领域以及发展趋势。环境安装&#xff1a;学习如何在不同的操作系…

18987 随机数(测验)

这个问题可以通过使用集合&#xff08;set&#xff09;和排序来解决。集合是一种数据结构&#xff0c;它可以自动去除重复的元素。然后我们可以将集合中的元素转移到一个数组中&#xff0c;并对&#xfffd;&#xfffd;组进行排序。 以下是使用C的代码实现&#xff1a; #i…

浅谈哈希与哈希表(c++)

目录 一、哈希的基本概念&#xff08;一&#xff09;哈希函数的特性&#xff08;二&#xff09;哈希冲突 二、C 中的哈希表实现三、哈希表的性能分析四、哈希表的应用场景五、优化哈希表的策略六、例题讲解【模板】字符串哈希题目描述输入格式输出格式样例 #1样例输入 #1样例输…

工业5G路由器赋能户外组网远程监控及预警

随着物联网、大数据、云计算等技术的快速发展&#xff0c;工业领域对于远程监控、实时预警和数据传输的需求日益增长。特别是在户外复杂环境下&#xff0c;传统的有线网络组网方式面临着布线难度大、成本高、维护困难等问题。 工业5G路由器在户外组网远程监控预警应用基于高速…

Android开发之事件分发

#来自ウルトラマンゼロ&#xff08;哉阿斯&#xff09; 1 Activity 构成 平常布局展示在ContentView中。 2 事件分发 事件分发的本质其实就是把事件&#xff08;Touch&#xff09;封装成 MotionEvent 类&#xff0c;然后传递给 View 的层级处理。 MotionEvent 事件类型主要有…

RAG与Fine Tuning:如何选择正确的方法

今日份知识你摄入了么&#xff1f; 生成式人工智能有潜力改变你的业务和数据工程团队&#xff0c;但前提是要正确实施。那么&#xff0c;你的数据团队如何才能真正利用大型语言模型或生成式人工智能_&#xff08;GenAI&#xff09;_计划来驱动价值呢&#xff1f; 领先的组织通…

我在高职教STM32——I2C通信入门(1)

大家好,我是老耿,高职青椒一枚,一直从事单片机、嵌入式、物联网等课程的教学。对于高职的学生层次,同行应该都懂的,老师在课堂上教学几乎是没什么成就感的。正是如此,才有了借助CSDN平台寻求认同感和成就感的想法。在这里,我准备陆续把自己花了很多心思设计的教学课件分…

Sentinel-1 Level 1数据处理的详细算法定义(五)

《Sentinel-1 Level 1数据处理的详细算法定义》文档定义和描述了Sentinel-1实现的Level 1处理算法和方程,以便生成Level 1产品。这些算法适用于Sentinel-1的Stripmap、Interferometric Wide-swath (IW)、Extra-wide-swath (EW)和Wave模式。 今天介绍的内容如下: Sentinel-1 L…

Python爬虫新手指南及简单实战

网络爬虫是自动化获取网络信息的高效工具&#xff0c;Python因其强大的库支持和简洁的语法成为编写网络爬虫的首选语言。本教程将通过一个具体的案例&#xff08;基于Microsoft Edge浏览器的简单爬取&#xff09;&#xff0c;指导你使用Python实现一个完整的网络爬虫&#xff0…

NIO专题学习(一)

一、BIO/NIO/AIO介绍 1. 背景说明 在Java的软件设计开发中&#xff0c;通信架构是不可避免的。我们在进行不同系统或者不同进程之间的数据交互&#xff0c;或者在高并发的通信场景下都需要用到网络通信相关的技术。 对于一些经验丰富的程序员来说&#xff0c;Java早期的网络…

PXE 服务器搭建——启动界面设计实验

环境准备&#xff1a; 前期准备&#xff1a; 解决 kickstart 实验出现的 DHCP 的问题-CSDN博客 http://t.csdnimg.cn/5vZP0 当前准备&#xff1a; 两台虚拟机&#xff1a;RHEL7 OpenEuler(作为测试机器使用) ip&#xff1a;172.25.254.100 yum install syslinux.x…