【算法思想】贪心

💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。
img

  • 推荐:kuan 的首页,持续学习,不断总结,共同进步,活到老学到老
  • 导航
    • 檀越剑指大厂系列:全面总结 java 核心技术点,如集合,jvm,并发编程 redis,kafka,Spring,微服务,Netty 等
    • 常用开发工具系列:罗列常用的开发工具,如 IDEA,Mac,Alfred,electerm,Git,typora,apifox 等
    • 数据库系列:详细总结了常用数据库 mysql 技术点,以及工作中遇到的 mysql 问题等
    • 懒人运维系列:总结好用的命令,解放双手不香吗?能用一个命令完成绝不用两个操作
    • 数据结构与算法系列:总结数据结构和算法,不同类型针对性训练,提升编程思维,剑指大厂

非常期待和您一起在这个小小的网络世界里共同探索、学习和成长。💝💝💝 ✨✨ 欢迎订阅本专栏 ✨✨

博客目录

    • 一.介绍
      • 1.什么是贪心算法?
      • 2.步骤
      • 3.应用
      • 2.贪心模版
    • 二.贪心的例子
      • 1.Dijkstra
      • 2.Prim
      • 3.Kruskal
      • 4.其它贪心的例子
      • 5.常见问题及解答

一.介绍

1.什么是贪心算法?

贪心算法(Greedy Algorithm)是一种常见的问题求解策略,通常用于优化问题。贪心算法的核心思想是在每一步都做出当前看起来最优的选择,而不考虑全局最优解。贪心算法通常适用于那些具有贪心选择性质的问题,即局部最优解也是全局最优解的一部分。

称之为贪心算法或贪婪算法,核心思想是

  1. 将寻找最优解的问题分为若干个步骤
  2. 每一步骤都采用贪心原则,选取当前最优解
  3. 因为没有考虑所有可能,局部最优的堆叠不一定让最终解最优

2.步骤

贪心算法是一种在每一步选择中都采取在当前状态下最好或最优(即最有利)的选择,从而希望导致结果是最好或最优的算法。这种算法通常用于求解优化问题,如最小生成树、背包问题等。

以下是贪心算法的一般特点和步骤:

  1. 选择策略:从问题的所有可行选择中,选择当前看起来最优的一个。这个选择通常基于一定的规则或者评估函数。

  2. 可行性检验:检查所做的选择是否合法,即是否满足问题的约束条件。

  3. 局部最优性:贪心算法只关注当前步骤的最优解,而不考虑整体问题的最优解。这是贪心算法与动态规划等其他算法的主要不同之处。

  4. 迭代:重复执行步骤 1 和步骤 2,直到达到问题的结束条件或者找到一个近似的解。

3.应用

贪心算法的应用范围广泛,可以用于解决许多优化问题,如:

  • 最小生成树问题:如 Kruskal 算法和 Prim 算法用于构建最小生成树。
  • 最短路径问题:如 Dijkstra 算法和 Bellman-Ford 算法用于寻找最短路径。
  • 调度问题:如任务调度、会议安排等。
  • 背包问题:给定一组物品和一个背包,每个物品有一定的重量和价值,要求在不超过背包容量的情况下,尽可能多地装入物品。
  • 活动选择问题:在一个活动集合中,每次只能参加一个活动,问如何安排时间以最大化所有活动的收益。
  • 编辑距离问题:给定两个字符串,求它们之间的最小编辑距离(即将一个字符串转换为另一个字符串所需的最少操作次数)。
  • 网络流问题:给定一张有向图和一些起点和终点,求最大流量。
  • 找零问题:给定一定数量的硬币和需要找零的金额,求使用最少的硬币数。

贪心算法的优点在于它们通常比其他复杂算法更快,因为它们不需要考虑所有可能的解决方案。然而,贪心算法的局限性在于它们不能保证一定找到全局最优解,因此在某些情况下可能会得到次优解或者不可行解。因此,在使用贪心算法时,需要仔细分析问题的特性,以确定它是否适合使用贪心策略。有时候,贪心算法可以与其他算法结合使用,以获得更好的结果。

2.贪心模版

下面是一个使用 Java 编写的通用贪心算法模板,你可以根据具体问题进行适当的修改和扩展:

import java.util.Arrays;public class GreedyAlgorithm {public static void main(String[] args) {// 在这里输入问题的输入数据// 例如,如果是一个数组或者列表,可以这样初始化:int[] inputArray = {5, 2, 1, 9, 3};// 调用贪心算法函数int result = greedyAlgorithm(inputArray);// 输出结果System.out.println("最终结果: " + result);}public static int greedyAlgorithm(int[] input) {// 在这里实现贪心算法的逻辑// 请根据问题的具体要求编写贪心策略// 以下是一个简单的示例:找到数组中的最小元素int minElement = input[0];for (int i = 1; i < input.length; i++) {if (input[i] < minElement) {minElement = input[i];}}return minElement;}
}

这个模板中,你可以将问题特定的输入数据放在main函数中,然后调用greedyAlgorithm函数来执行贪心算法。在greedyAlgorithm函数中,你需要根据问题的特性编写相应的贪心策略。

请注意,这只是一个基本的模板,实际上,贪心算法的实现会根据具体问题的不同而有所不同。你需要根据问题的需求来设计合适的贪心策略,并根据具体情况修改模板。

二.贪心的例子

1.Dijkstra

// ...
while (!list.isEmpty()) {// 选取当前【距离最小】的顶点Vertex curr = chooseMinDistVertex(list);// 更新当前顶点邻居距离updateNeighboursDist(curr);// 移除当前顶点list.remove(curr);// 标记当前顶点已经处理过curr.visited = true;
}
  • 没找到最短路径的例子:负边存在时,可能得不到正确解
  • 问题出在贪心的原则会认为本次已经找到了该顶点的最短路径,下次不会再处理它(curr.visited = true)
  • 与之对比,Bellman-Ford 并没有考虑局部距离最小的顶点,而是每次都处理所有边,所以不会出错,当然效率不如 Dijkstra

2.Prim

// ...
while (!list.isEmpty()) {// 选取当前【距离最小】的顶点Vertex curr = chooseMinDistVertex(list);// 更新当前顶点邻居距离updateNeighboursDist(curr);// 移除当前顶点list.remove(curr);// 标记当前顶点已经处理过curr.visited = true;
}

3.Kruskal

// ...
while (list.size() < size - 1) {// 选取当前【距离最短】的边Edge poll = queue.poll();// 判断两个集合是否相交int i = set.find(poll.start);int j = set.find(poll.end);if (i != j) { // 未相交list.add(poll);set.union(i, j); // 相交}
}

4.其它贪心的例子

  • 选择排序、堆排序

  • 拓扑排序

  • 并查集合中的 union by size 和 union by height

  • 哈夫曼编码

  • 钱币找零,英文搜索关键字

    • change-making problem
    • find Minimum number of Coins
  • 任务编排

  • 求复杂问题的近似解

5.常见问题及解答

  1. 贪心算法一定会找到最优解吗?
    答:不一定。贪心算法只保证在每一步选择中都是最优的,但并不能保证整个问题的最优解。例如,背包问题中的贪心算法可能会导致最后一个物品没有被装入背包。
  2. 如何判断一个问题是否适合用贪心算法解决?
    答:一个问题如果可以用递归的方式分解成若干个子问题,且每个子问题都有明确的最优解(即局部最优),那么这个问题就可以用贪心算法解决。
  3. 贪心算法的时间复杂度是多少?
    答:贪心算法的时间复杂度取决于问题的规模和具体实现。一般来说,对于规模较小的问题,贪心算法的时间复杂度可以达到 O(nlogn)或 O(n^2);对于规模较大的问题,可能需要 O(n^3)或更高。

觉得有用的话点个赞 👍🏻 呗。
❤️❤️❤️本人水平有限,如有纰漏,欢迎各位大佬评论批评指正!😄😄😄

💘💘💘如果觉得这篇文对你有帮助的话,也请给个点赞、收藏下吧,非常感谢!👍 👍 👍

🔥🔥🔥Stay Hungry Stay Foolish 道阻且长,行则将至,让我们一起加油吧!🌙🌙🌙

img

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

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

相关文章

Linux基础知识 总结

Linux基础知识 总结 1、Clion的简单介绍 CLion是以IntelliJ为基础&#xff0c;专为开发C及C所设计的跨平台IDE&#xff0c;可以在Windows、Linux及MacOS使用&#xff0c;这里我是在ubuntu 16.0.4基础上安装。2、下载 Linux版Clion的.tar.gz的压缩包 wget https://download.j…

这本书竟然把JAVA讲的如此透彻!漫画JAVA火爆出圈!

亲爱的粉丝们&#xff0c;你是否曾经为学习JAVA而苦恼&#xff1f;繁复的代码和复杂的逻辑常常让人感到头大。不过&#xff0c;今天我要为大家介绍一本神奇的书——《漫画JAVA》&#xff0c;它以图文并茂的方式&#xff0c;轻松诙谐地讲解了JAVA的方方面面。在这篇文章中&#…

【postgresql】ERROR: cannot alter type of a column used by a view or rule

修改字段类型 由varchar 改为int8。 具体sql alter table company alter column city_id type int8 using city_id::int8; 返回错误信息 > ERROR: cannot alter type of a column used by a view or rule DETAIL: rule _RETURN on view search_qy depends on column …

nodejs+vue 医院病历管理系统

系统使用权限分别包括管理员、病人和医生&#xff0c;其中管理员拥有着最大的权限&#xff0c;同时管理员的功能模块也是最多的&#xff0c;管理员可以对系统上所有信息进行管理。用户可以修改个人信息&#xff0c;对医院病历信息进行查询&#xff0c;对住院信息进行添加、修改…

【操作系统笔记十四】科普:POSIX 是什么

注&#xff1a;本文转载自该文章posix是什么都不知道&#xff0c;还好意思说你懂Linux&#xff1f; Linux开发者越来越多&#xff0c;但是仍然有很多人整不明白POSIX是什么。本文就带着大家来了解一下到底什么是POSIX&#xff0c;了解他的历史和重要性。 一、什么是 POSIX&…

RK3568驱动指南|第五期-中断-第44章 共享工作队列实验

瑞芯微RK3568芯片是一款定位中高端的通用型SOC&#xff0c;采用22nm制程工艺&#xff0c;搭载一颗四核Cortex-A55处理器和Mali G52 2EE 图形处理器。RK3568 支持4K 解码和 1080P 编码&#xff0c;支持SATA/PCIE/USB3.0 外围接口。RK3568内置独立NPU&#xff0c;可用于轻量级人工…

Excel 语法

目录 语法 逐步创建公式 对单元格使用公式 另一个例子 语法 Excel中的一个公式用于进行数学计算。公式总是以单元格中键入的等号开头&#xff0c;然后是您的计算。 注意&#xff1a;您可以通过选择单元格并键入等号&#xff08;&#xff09;来声明该单元格 逐步创建公式…

【Java 基础篇】Java 模块化详解

Java 9引入了一项重要的功能&#xff1a;模块化&#xff08;Module System&#xff09;。模块化是一种将代码和资源封装到可重用和独立的单元中的方法&#xff0c;它有助于改善代码的可维护性、可重用性和安全性。本文将介绍Java模块化的基本概念、如何创建和使用模块以及一些最…

基于微信小程序的美术馆预约平台设计与实现(源码+lw+部署文档+讲解等)

前言 &#x1f497;博主介绍&#xff1a;✌全网粉丝10W,CSDN特邀作者、博客专家、CSDN新星计划导师、全栈领域优质创作者&#xff0c;博客之星、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java、小程序技术领域和毕业项目实战✌&#x1f497; &#x1f447;&#x1f3fb;…

SLAM从入门到精通(IMU参数的读取)

【 声明&#xff1a;版权所有&#xff0c;欢迎转载&#xff0c;请勿用于商业用途。 联系信箱&#xff1a;feixiaoxing 163.com】 上一篇文章我们说过&#xff0c;对于差速轮来说&#xff0c;旋转的计算很多程度上依赖于thetatan(theta)这个公式来进行的。但是&#xff0c;我们也…

以太坊代币标准ERC20、ERC165、ERC721

两个概念 ERC(Ethereum Request for Comment) 以太坊意见征集稿EIP(Ethereum Improvement Proposals)以太坊改进提案 ERC和EIP用于使得以太坊更加完善&#xff1b;在ERC中提出了很多标准&#xff0c;用的最多的标准就是它的Token标准; 有哪些标准详细见https://eips.ethereum…

中国TO B投资,迈入第二周期

2023年,中国TOB正在愈发成熟,迈进第二个周期的趋势已经体现在融资金额上。 作者|斗斗 编辑|皮爷 出品|产业家 TOB&#xff0c;依旧是一级市场的大热门。 统计数据显示&#xff0c;截止2023年8月31日&#xff0c;TOB领域共发生融资事件406起&#xff0c;同比2022年减少…

phpstudy2016 RCE漏洞验证

文章目录 漏洞描述漏洞验证 漏洞描述 PHPStudyRCE&#xff08;Remote Code Execution&#xff09;&#xff0c;也称为phpstudy_backdoor漏洞&#xff0c;是指PHPStudy软件中存在的一个远程代码执行漏洞。 漏洞验证 打开phpstudy2016&#xff0c;用bp自带的浏览器访问www目录下…

Vue3+element-plus切换标签页时数据保留问题

记录一次切换标签页缓存失效问题&#xff0c;注册路由时name不一致可能会导致缓存失效

Unity中Shader通道ColorMask

文章目录 [TOC](文章目录) 前言一、ColorMask是用来干什么的二、怎么做到和 Unity UI 中的 Shader 一样根据UI层级自动适配Shader中模板测试值1、借鉴Unity官方的 UI Shader 前言 Unity中Shader通道ColorMask 一、ColorMask是用来干什么的 ColorMask RGB | A | 0 | R、G、B、…

雨课堂 运动与健康 网课参考资料

整理于网络&#xff1a;仅用于学习交流讨论&#xff0c;侵删 参考文档&#xff1a;https://www.doc88.com/p-99629779008847.html 参考视频&#xff1a; 运动与健康&#xff08;2021年秋网课答案 69题版本&#xff09;_哔哩哔哩 | https://www.bilibili.com/video/av210112837/…

WebGL 用鼠标控制物体旋转

目录 鼠标控制物体旋转 如何实现物体旋转 示例程序&#xff08;RotateObject.js&#xff09; 代码详解 示例效果 鼠标控制物体旋转 有时候&#xff0c;WebGL程序需要让用户通过鼠标操作三维物体。这一节来分析示例程序RotateObject&#xff0c;该程序允许用户通过拖动&…

DT 卡通材质学习 一

渐变着色器 相交线 笔刷和卡通结合使用 修改器

计算机类软件方向适合参加的比赛

前言 博主是一名计算机专业的大三学生&#xff0c;在校时候参加了很多比赛和训练营&#xff0c;现在给大家博主参加过的几个的比赛&#xff0c;希望能给大一大二的学生提供一点建议。 正文 最近也有比赛的&#xff0c;我会从时间线上来给大家推荐一些比赛&#xff0c;并且给…

大屏大概是怎么个开发法(前端)

写在前面&#xff0c;博主是个在北京打拼的码农&#xff0c;从事前端工作5年了&#xff0c;做过十多个大大小小不同类型的项目&#xff0c;最近心血来潮在这儿写点东西&#xff0c;欢迎大家多多指教。 对于文章中出现的任何错误请大家批评指出&#xff0c;一定及时修改。有任何…