当前位置: 首页 > news >正文

算法系列之贪心算法

e540d597-0ebc-418e-be26-015086b19459.jpg

在算法中,贪心算法(Greedy Algorithm)是一种常见的解决优化问题的算法。贪心算法的核心思想是:在每一步选择中都采取当前状态下最优的选择,即贪心的做出局部最优的决策,从而希望最终能够得到全局最优解。尽管贪心算法并不总是能够得到全局最优解,但在许多实际问题中,它能够提供足够好的解决方案,并且具有较高的计算效率。

本文将详细介绍贪心算法的基本概念、优缺点、实现步骤以及适用场景,并通过示例问题来展示贪心算法的应用。

基本概念

贪心算法它在每一步选择中都做出局部最优的选择,希望通过一系列局部最优的选择最终达到全局最优。贪心算法不会考虑过去的决策,而是一路向前的进行贪心的选择,不断缩小问题的范围,直至问题被解决。

我们通过找零问题来了解下贪心算法的工作原理:

问题描述:给定不同面额的硬币和一个总金额,要求用最少数量的硬币凑成该金额。

贪心策略:每次选择不大于且最接近剩余金额的最大的硬币,直到凑够总金额。

如图所示:我们需要找到凑够181元金额最少的硬币

_20250222204509.jpg

优点及局限性

优点:

  • 高效性:贪心算法通常具有较高的计算效率,适用于大规模问题。

  • 简单性:贪心算法的实现通常较为简单,易于理解和编码。

缺点:

  • 局部最优不一定全局最优:贪心算法并不总是能够得到全局最优解,有时只能得到近似解。

  • 适用范围有限:贪心算法仅适用于具有贪心选择性质和最优子结构的问题。

示例:

比如币种有【1,20,50】,金额为60的话贪心算法只能找到 50+1*10 的兑换组合,有11张,而动态规划可以找到 20*3共3张的最优解。

贪心算法的实现步骤

贪心算法的实现通常包括以下几个步骤:

  1. 问题建模:将问题抽象为一个优化问题,明确目标函数和约束条件。

  2. 选择策略:确定每一步的局部最优选择策略。

  3. 迭代求解:从初始状态开始,逐步应用选择策略,直到达到终止条件。

  4. 验证解的有效性:验证最终得到的解是否满足问题的要求,并判断是否为全局最优解。

适用场景

  1. 最优化问题

问题需要找到最大值或最小值。

  • 找零问题(用最少数量的硬币找零)。
  • 最小生成树问题(Prim算法、Kruskal算法)。
  • 最短路径问题(Dijkstra算法)。
  1. 区间问题

问题涉及区间选择或区间调度。

  • 活动选择问题(选择最多的互不冲突的活动)。
  • 区间覆盖问题(用最少的区间覆盖所有点)。
  1. 分配问题

问题涉及资源的分配或任务的调度。

  • 背包问题(分数背包问题,贪心算法可解)。
  • 任务调度问题(最小化完成时间或最大化任务数量)。
  1. 组合问题

问题涉及从一组元素中选择子集,满足某些条件。

  • 霍夫曼编码(构建最优前缀编码)。
  • 集合覆盖问题(近似解法)。

Java 实现示例

我们就用代码实现我们上边所示的找零问题,金额 161,面额【1,5,10,20,50,100】。代码如下:

/*** 贪心算法* 金额 161,面额[1,5,10,20,50,100],求最少的硬币个数*/
public class GreedyCoin {/*** 求解最少硬币个数* @param amount* @param coins* @return*/public static int minCoin(int amount, int[] coins) {//排序硬币面值Arrays.sort(coins);//初始化张数int count = 0;//循环面值,从大到小for (int i = coins.length - 1; i >= 0; i--) {count += amount / coins[i];amount = amount % coins[i];}// 如果金额没有完全凑齐,返回-1if(amount > 0){return -1;}return count;}public static void main(String[] args) {int amount = 161;int[] coins = {1,5,10,20,50,100};System.out.println(minCoin(amount, coins));}
}

示例题:观看⽂艺汇演

  • 问题描述

某公园将举⾏多场⽂艺表演,很多演出都是同时进⾏,⼀个⼈只能同时观看⼀场演出,且不能迟到早退,由于演出分布在不同的演出场地,所以连续观看的演出最少有 15 分钟的时间间隔,⼩明是⼀个狂热的⽂艺迷,想观看尽可能多的演出。现给出演出时间表,请帮⼩明计算他最多能观看⼏场演出。

  • 输⼊

第⼀⾏为⼀个数 N ,表⽰演出场数, 1 <= N <= 1000 。
接下来 N ⾏,每⾏两个空格分割的整数,第⼀个整数 T 表⽰演出的开始时间,第⼆个整数 L 表⽰
演出的持续时间, T 和 L 的单位为分钟, 0 <= T <= 1440, 0 < L <= 100 。

  • 输出

最多能观看的演出场数。

  • 示例

示例1

输入

2
720 120
840 120

输出

1

示例2

输入

2
20 60
100 60

输出

2

示例3

输入

4
10 20
100 20
150 60
80 40

输出

3
  • 问题分析

我们可以储存每⼀场演出的开始和结束时间,即按照 [start, end] 的⽅式进⾏储存。由于题⽬要求每间隔 15 分钟才能够看下⼀场演出,所以我们可以把每⼀场演出的结束时间再加上 15 分钟,这样题⽬就转变为:考虑所有不重叠的 [start, end] 区间的最⼤数⽬。

我们按开始时间对这些区间进行排序, 情况1:演出2的开始时间在演出1之后,就可以看完演出1再看演出2; 情况2:演出2的开始时间在演出1的期间,结束时间在演出1的结束时间之后,看完演出1无法看演出2 情况3:演出2的结束时间在演出1的结束时间之前,没必要看演出1。

  • 代码实现
/*** 文艺演出类*/
public class Performance implements Comparable<Performance>{int start; // 演出开始时间int end;   // 演出结束时间public Performance(int start, int end) {this.start = start;this.end = end;}@Overridepublic int compareTo(Performance other) {return this.start - other.start; // 按开始时间从小到大排序}
}/*** 观看⽂艺汇演贪心算法
*/
public class GreedyPerformance {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int N = scanner.nextInt();List<Performance> performances = new ArrayList<>();for (int i = 0; i < N; i++) {int start = scanner.nextInt();int during = scanner.nextInt();int end = start + during + 15;performances.add(new Performance(start, end));}Collections.sort(performances);int count = 0; // 观看演出的场数int lastEnd = 0; // 上一场演出的结束时间,初始化为0for(Performance performance:performances){int start = performance.start;int end = performance.end;// 如果当前演出的开始时间大于上一场演出的结束时间,则观看if(start >= lastEnd){count++;lastEnd=end;// 如果当前演出的开始时间小于上一场演出的结束时间,当前演出的结束时间大于上一场的结束时间,则不能观看}else if(start < lastEnd &&  lastEnd<= end){continue;// 如果当前演出的结束时间小于上一场的结束时间,则观看当前场}else if(lastEnd > end){lastEnd=end;}}System.out.println(count);}}

总结

贪心算法是一种简单而高效的优化策略,适用于许多实际问题。尽管它并不总是能够得到全局最优解,但在许多情况下,贪心算法能够提供足够好的解决方案,并且具有较高的计算效率。理解贪心算法的基本原理和适用场景,能够帮助我们在实际问题中更好地应用这一策略。

相关文章:

算法系列之贪心算法

在算法中&#xff0c;贪心算法&#xff08;Greedy Algorithm&#xff09;是一种常见的解决优化问题的算法。贪心算法的核心思想是&#xff1a;在每一步选择中都采取当前状态下最优的选择&#xff0c;即贪心的做出局部最优的决策&#xff0c;从而希望最终能够得到全局最优解。尽…...

将产品照片(form.productPhotos)转为 JSON 字符串发送给后端

文章目录 1. 前端 form.productPhotos 的当前处理a. 组件绑定b. 当前发送逻辑 2. 如何将 form.productPhotos 转为 JSON 字符串发送给后端a. 修改前端 save() 方法b. 确保 esave API 支持接收字符串 基于你提供的 identify-form.vue 代码&#xff0c;我将分析如何将产品照片&a…...

『大模型笔记』详细对比GraphRAG与传统RAG!

详细对比GraphRAG与传统RAG! 文章目录 详细对比GraphRAG与传统RAG!要点最终内容1. GraphRAG的作用与应用场景2. GraphRAG与传统RAG的对比3. GraphRAG的工作原理4. GraphRAG如何提高准确性和提供完整答案5. GraphRAG在开发和维护中的优势6. GraphRAG对生产环境的影响7. GraphR…...

安全面试3

文章目录 一个单位的一级域名可能不止一个&#xff0c;怎么收集某个单位的所有域名&#xff0c;注意不是子域名用转义字符防御时&#xff0c;如果遇到数据库的列名或是表名本身就带着特殊字符&#xff0c;应该怎么做宽字节注入原理防御宽字节注入的方法 基于黑白名单的修复&…...

软件测试:1、单元测试

1. 单元测试的基本概念 单元&#xff08;Unit&#xff09;&#xff1a;软件系统的基本组成单位&#xff0c;可以是函数、模块、方法或类。 单元测试&#xff08;Unit Testing&#xff09;&#xff1a;对软件单元进行的测试&#xff0c;验证代码的正确性、规范性、安全性和性能…...

球队训练信息管理系统设计与实现(代码+数据库+LW)

摘 要 传统办法管理信息首先需要花费的时间比较多&#xff0c;其次数据出错率比较高&#xff0c;而且对错误的数据进行更改也比较困难&#xff0c;最后&#xff0c;检索数据费事费力。因此&#xff0c;在计算机上安装球队训练信息管理系统软件来发挥其高效地信息处理的作用&a…...

【Bluedroid】AVRCP 连接源码分析(二)

接着上一篇【Bluedroid】AVRCP 连接源码分析(一)-CSDN博客,继续AVRCP连接的源码分析。 getcapabilities_cmd packages/modules/Bluetooth/system/btif/src/btif_rc.cc /***************************************************************************** Function …...

OSS(对象存储服务)

OSS&#xff08;对象存储服务&#xff09; 是一种用于存储和管理非结构化数据的云存储服务&#xff0c;其核心设计面向海量数据的高扩展性、高可靠性和低成本存储。以下从定义、核心原理、架构特点和应用场景等方面详细介绍&#xff1a; 一、什么是OSS&#xff1f; OSS&#x…...

《深入理解JVM》实战笔记(二): 类加载机制与类加载器

序言 Java 语言的强大之处之一在于其动态加载的能力&#xff0c;使得 Java 程序可以在运行时加载新的类&#xff0c;而不需要在编译时确定所有的类信息。这一切都离不开 JVM 的类加载机制。本篇博客将详细探讨 JVM 的类加载过程以及类加载器的工作原理&#xff0c;帮助你更深入…...

ChromeDriver下载

平时为了下个驱动&#xff0c;到处找挺麻烦&#xff0c;收集了很多无偿分享给需要的人&#xff0c;仅供学习和交流。 ChromeDriver 102.0.5005.61 ChromeDriver 105.0.5195.102 ChromeDriver 108.0.5359.71 ChromeDriver 111.0.5563.64 ChromeDriver 116.0.5845.97 Chrom…...

《深度学习实战》第1集:深度学习基础回顾与框架选择

本专栏系列博文旨在帮助读者从深度学习的基础知识逐步进阶到前沿技术&#xff0c;涵盖理论、实战和行业应用。每集聚焦一个核心知识点&#xff0c;并结合实际项目进行实践&#xff0c;避免空谈理论&#xff0c;简洁明快&#xff0c;快速切入代码&#xff0c;所有代码都经过验证…...

Docker 部署AnythingLLM

两个指令搞定 1.下载镜像 docker pull mintplexlabs/anythingllm 2.运行容器 export STORAGE_LOCATION$HOME/anythingllm mkdir -p $STORAGE_LOCATION chmod -R 777 $STORAGE_LOCATION touch "$STORAGE_LOCATION/.env" docker run -d -p 3001:3001 \ --cap-add SY…...

泰山派RK3566移植QT,动鼠标时出现屏幕闪烁

总结&#xff1a; 交叉编译到 泰山派rk3566跑调海康摄像头的qt应用程序失败了。 X11无效窗口。 移植QT注意 屏幕分辨率不要改。改了执行QT的时候&#xff0c;framebuffer识别不出设备。 命令行安装QT-Creator sudo install 类似的指令安装Qt-Creator时&#xff0c;可能找不到编…...

关于Java 反射的简单易懂的介绍

目录 #0.总览 #1. 类的反射 ①介绍 ②获取 ③作用 获取构造函数&#xff1a; 创建实例&#xff1a; 字段操作&#xff1a; 方法操作&#xff1a; 获取修饰符&#xff1a; #2.总结 #0.总览 反射&#xff0c;官方是这样介绍它的&#xff1a; Reflection is a …...

市场趋势中突破确认的多维度判断方法

波动率突破策略是众多交易者广泛采用的重要交易策略之一。而在这一策略中&#xff0c;准确判断突破是否有效&#xff0c;是决定交易成败的关键环节。仅仅依据单一因素来确认突破&#xff0c;往往会使交易者陷入误判的困境&#xff0c;导致不必要的损失。因此&#xff0c;采用多…...

网络空间安全(2)应用程序安全

前言 应用程序安全&#xff08;Application Security&#xff0c;简称AppSec&#xff09;是一个综合性的概念&#xff0c;它涵盖了应用程序从开发到部署&#xff0c;再到后续维护的整个过程中的安全措施。 一、定义与重要性 定义&#xff1a;应用程序安全是指识别和修复应用程序…...

【MyBatis】CRUD、配置解析、ResultMap、分页实现

目录标题 1、Mybatis简介1.1、什么是MyBatis1.2、持久化1.3、持久层1.4、为什么需要MybatisMyBatis的优点 2.1、代码演示搭建实验数据库导入MyBatis相关 jar 包 03、CRUD操作3.1、namespace3.2、select3.3、insert3.4、update3.5、delete 04、MyBatis配置解析4、配置解析4.3、m…...

Linux系统编程之高级信号处理

概述 在前一篇文章中&#xff0c;我们介绍了signal函数、sigaction函数等基本的信号处理方法。在本篇中&#xff0c;我们将介绍信号处理的一些高级用法&#xff0c;包括&#xff1a;阻塞与解除阻塞、定时器等。 阻塞与解除阻塞 有时候&#xff0c;我们不希望某个信号立即被处理…...

深度学习驱动的车牌识别:技术演进与未来挑战

一、引言 1.1 研究背景 在当今社会&#xff0c;智能交通系统的发展日益重要&#xff0c;而车牌识别作为其关键组成部分&#xff0c;发挥着至关重要的作用。车牌识别技术广泛应用于交通管理、停车场管理、安防监控等领域。在交通管理中&#xff0c;它可以用于车辆识别、交通违…...

钉钉快捷免登录 通过浏览器打开第三方系统,

一、钉钉内跳转至浏览器的实现 使用钉钉JSAPI的跳转接口 在钉钉内通过dd.biz.navigation.openLink方法强制在系统浏览器中打开链接。此方法需在钉钉开发者后台配置应用权限&#xff0c;确保应用具备调用该API的资格37。 示例代码&#xff1a; dd.ready(() > {dd.biz.navigat…...

idea大量爆红问题解决

问题描述 在学习和工作中&#xff0c;idea是程序员不可缺少的一个工具&#xff0c;但是突然在有些时候就会出现大量爆红的问题&#xff0c;发现无法跳转&#xff0c;无论是关机重启或者是替换root都无法解决 就是如上所展示的问题&#xff0c;但是程序依然可以启动。 问题解决…...

大型活动交通拥堵治理的视觉算法应用

大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动&#xff08;如演唱会、马拉松赛事、高考中考等&#xff09;期间&#xff0c;城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例&#xff0c;暖城商圈曾因观众集中离场导致周边…...

【HarmonyOS 5.0】DevEco Testing:鸿蒙应用质量保障的终极武器

——全方位测试解决方案与代码实战 一、工具定位与核心能力 DevEco Testing是HarmonyOS官方推出的​​一体化测试平台​​&#xff0c;覆盖应用全生命周期测试需求&#xff0c;主要提供五大核心能力&#xff1a; ​​测试类型​​​​检测目标​​​​关键指标​​功能体验基…...

CMake基础:构建流程详解

目录 1.CMake构建过程的基本流程 2.CMake构建的具体步骤 2.1.创建构建目录 2.2.使用 CMake 生成构建文件 2.3.编译和构建 2.4.清理构建文件 2.5.重新配置和构建 3.跨平台构建示例 4.工具链与交叉编译 5.CMake构建后的项目结构解析 5.1.CMake构建后的目录结构 5.2.构…...

如何为服务器生成TLS证书

TLS&#xff08;Transport Layer Security&#xff09;证书是确保网络通信安全的重要手段&#xff0c;它通过加密技术保护传输的数据不被窃听和篡改。在服务器上配置TLS证书&#xff0c;可以使用户通过HTTPS协议安全地访问您的网站。本文将详细介绍如何在服务器上生成一个TLS证…...

三体问题详解

从物理学角度&#xff0c;三体问题之所以不稳定&#xff0c;是因为三个天体在万有引力作用下相互作用&#xff0c;形成一个非线性耦合系统。我们可以从牛顿经典力学出发&#xff0c;列出具体的运动方程&#xff0c;并说明为何这个系统本质上是混沌的&#xff0c;无法得到一般解…...

均衡后的SNRSINR

本文主要摘自参考文献中的前两篇&#xff0c;相关文献中经常会出现MIMO检测后的SINR不过一直没有找到相关数学推到过程&#xff0c;其中文献[1]中给出了相关原理在此仅做记录。 1. 系统模型 复信道模型 n t n_t nt​ 根发送天线&#xff0c; n r n_r nr​ 根接收天线的 MIMO 系…...

让回归模型不再被异常值“带跑偏“,MSE和Cauchy损失函数在噪声数据环境下的实战对比

在机器学习的回归分析中&#xff0c;损失函数的选择对模型性能具有决定性影响。均方误差&#xff08;MSE&#xff09;作为经典的损失函数&#xff0c;在处理干净数据时表现优异&#xff0c;但在面对包含异常值的噪声数据时&#xff0c;其对大误差的二次惩罚机制往往导致模型参数…...

Kafka入门-生产者

生产者 生产者发送流程&#xff1a; 延迟时间为0ms时&#xff0c;也就意味着每当有数据就会直接发送 异步发送API 异步发送和同步发送的不同在于&#xff1a;异步发送不需要等待结果&#xff0c;同步发送必须等待结果才能进行下一步发送。 普通异步发送 首先导入所需的k…...

Ubuntu Cursor升级成v1.0

0. 当前版本低 使用当前 Cursor v0.50时 GitHub Copilot Chat 打不开&#xff0c;快捷键也不好用&#xff0c;当看到 Cursor 升级后&#xff0c;还是蛮高兴的 1. 下载 Cursor 下载地址&#xff1a;https://www.cursor.com/cn/downloads 点击下载 Linux (x64) &#xff0c;…...