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

算法-贪心算法简单介绍

news 来源：原创 2025/6/10 15:45:43

下面是贪心算法视频课的导学内容.

目录

    • 1. 什么是贪心算法?
    • 2. 贪心算法简单的三个例子:
      • 1. 找零问题
      • 2. 最小路径和问题
      • 3. 背包问题
    • 3. 贪心算法的特点
    • 4. 贪心算法学习的方式?

1. 什么是贪心算法?

简单来说, 我们称以局部最优进而使得全局最优的一种思想实现出来的算法为贪心算法.
其过程, 往往分为:

  1. 把解决问题分为若干部分
  2. 解决每一步的时候, 都选择当前看起来"最优"的选择
  3. “希望” 得到全局最优解

下面来解释两个引号词
“最优”: 上面说的意思是当前看来最优, 而不是从整体的角度看起来最优
“希望”: 意思是按这种思想去处理题目, 有可能会导致最后结果不是最优, 有可能从全局来看是最优结果的意思

2. 贪心算法简单的三个例子:

1. 找零问题

情景: 现在你有50块钱, 买了4块钱的东西, 卖家想要用最少的张数找你零钱.
在这里插入图片描述
此时可以试试贪心算法.

应该找你的钱数:

        50 - 4 = 46

按照贪心策略, 此时应该找你一张最大面额的, 因此是给你一张20的

        46 - 20 = 26 此时还需要找你26元

按照贪心策略, 此时应该找你一张最大面额的, 因此是给你一张20的

        26 - 20 = 6 此时还需要找你6元

按照贪心策略, 此时应该找你一张最大面额的, 因此是给你一张5元的

        6 - 5 = 1 此时还需要找你1元

按照贪心策略, 此时应该找你一张最大面额的, 因此是给你一张1元的

        1 - 1 = 0 此时还需要找你0元

此时找钱结束

其过程如下:
在这里插入图片描述

2. 最小路径和问题

起点在(0, 0)位置, 规定只能左右上下移动, 在这其中会路过许多方块. 每次路过方块需要加上对应的"路径值", 问如何才能到达目的地同时求和为最小?

按照贪心思想, 过程如下:
在这里插入图片描述

3. 背包问题

最大背包容量为: 8单位, 如何放一些物品, 使得该背包拿到的总价值最高?
在这里插入图片描述
假设我们按照V去贪心: ③ * 8 -> 总价值是: 1 * 8 = 8

假设我们按照W去贪心: ① * 1 + ③ * 3 -> 总价值是: 10 + 1 * 3 = 13

假设我们按照W/V去贪心: ① * 1 + ③ * 3 -> 总价值是: 10 + 1 * 3 = 13

3. 贪心算法的特点

  1. 贪心算法没有标准和模板, 贪心算法只是一种思想

  2. 贪心算法需要证明其对错, 对的需要其证明他是对的, 错的需要证明, 或者举反例

对于证明这块来说,

2-1 显然找零问题是对的, 证明如下:
在这里插入图片描述
2-2 最小路径和问题 和 背包问题都是错误的, 证明如下(举反例):
在这里插入图片描述

4. 贪心算法学习的方式?

  1. 遇到不会的很正常, 看多了解析就"可能"会了.
  2. 注重证明. 比如"背包"和"路径和"问题贪心出来都不是最优解.

EOF.

相关文章：

算法-贪心算法简单介绍

下面是贪心算法视频课的导学内容. 目录 1. 什么是贪心算法?2. 贪心算法简单的三个例子:1. 找零问题2. 最小路径和问题3. 背包问题 3. 贪心算法的特点4. 贪心算法学习的方式? 1. 什么是贪心算法? 简单来说, 我们称以局部最优进而使得全局最优的一种思想实现出来的算法为贪心…...

编程日记 2025/6/4 6:13:15

1Hive概览

1Hive概览 1hive简介2hive架构3hive与Hadoop的关系4hive与传统数据库对比5hive的数据存储 1hive简介 Hive是基于Hadoop的一个数据仓库工具，可以将结构化的数据文件映射为一张数据库表，并提供类SQL查询功能。 其本质是将SQL转换为MapReduce/Spark的任务进…...

编程日记 2025/6/4 3:29:14

Linux SUID提权

文章目录 1. SUID/SGID2. 查找SUID文件3. SUID/SGID提权3.1 SUID配置不当3.2 SUID systemctl提权3.3 $PATH变量劫持 参考 1. SUID/SGID SUID（Set User ID）意味着如果某个用户对属于自己的文件设置了这种权限，那么其他用户在执行这一脚本时也…...

编程日记 2025/6/4 3:28:58

RabbitMQ确保消息可靠性

消息丢失的可能性 支付服务先扣减余额和更新支付状态（这俩是同步调用），然后通过RabbitMq异步调用支付服务更新订单状态。但是有些情况下，可能订单已经支付 ，但是更新订单状态却失败了，这就出现了消息丢失。…...

编程日记 2025/6/4 3:31:05

用plotly制作一条带颜色的时间轴，显示学习情况

前一篇文章我写到用matplotlib制作一条带颜色的时间轴，显示学习情况-CSDN博客，这是我在工作地方写的程序，我回家后发现家里的笔记本用不了matplotlib，所以我尝试用plotly这另外的模块也写一段程序，让我的程序能够回家使…...

编程日记 2025/6/4 4:31:25

MySQL:索引

目录 1.MySQL索引是干什么的 2.铺垫知识 3.单个page的理解 4.页目录 单页情况 多页情况 1.MySQL索引是干什么的 MySQL的索引是提高查询效率，主要提高海量数据的检索速度。 2.铺垫知识 操作系统与磁盘之间IO的基本单位是4kb。 数据库是一个应用层软件&#…...

编程日记 2025/6/4 3:30:49

Kylin： `GLIBC_2.34‘ not found

需要查看服务器GLIBC版本 strings /lib64/libc.so.6 |grep GLIBC_如果没有，有两种办法，一种是libc.so.6降级，但是这样很容易将服务器搞崩溃 所以可以尝试下载对应版本 glibc 打包编译，重新建立软连，下列是RPM资源可以…...

编程日记 2025/6/3 13:04:55

ASP.NET Core - 依赖注入(四)

ASP.NET Core - 依赖注入（四） 4. ASP.NET Core默认服务5. 依赖注入配置变形 4. ASP.NET Core默认服务 之前讲了中间件，实际上一个中间件要正常进行工作，通常需要许多的服务配合进行，而中间件中的服务自然也是通过 Ioc…...

编程日记 2025/6/3 21:29:06

【全套】基于分类算法的学业警示预测信息管理系统

【全套】基于分类算法的学业警示预测信息管理系统 【摘 要】 随着网络技术的发展基于分类算法的学业警示预测信息管理系统是一种新的管理方式，同时也是现代学业预测信息管理的基础，利用互联网的时代与实际情况相结合来改变过去传统的学业预测信息管理中…...

编程日记 2025/6/4 1:35:58

《零基础Go语言算法实战》【题目 2-25】goroutine 的执行权问题

《零基础Go语言算法实战》 【题目 2-25】goroutine 的执行权问题 请说明以下这段代码为什么会卡死。 package main import ( "fmt" "runtime" ) func main() { var i byte go func() { for i 0; i < 255; i { } }() fmt.Println("start&quo…...

编程日记 2025/6/4 3:29:46

回归预测 | MATLAB实RVM相关向量机多输入单输出回归预测

回归预测 | MATLAB实RVM相关向量机多输入单输出回归预测 目录 回归预测 | MATLAB实RVM相关向量机多输入单输出回归预测预测效果基本介绍程序设计参考资料 预测效果 基本介绍 RVM-Adaboost相关向量机集成学习多输入单输出回归预测是一种先进的机器学习方法&#xff0c;用于处理…...

编程日记 2025/6/4 3:30:17

【OJ刷题】同向双指针问题3

这里是阿川的博客&#xff0c;祝您变得更强 ✨ 个人主页&#xff1a;在线OJ的阿川 &#x1f496;文章专栏&#xff1a;OJ刷题入门到进阶 &#x1f30f;代码仓库&#xff1a; 写在开头 现在您看到的是我的结论或想法&#xff0c;但在这背后凝结了大量的思考、经验和讨论 目录 1…...

编程日记 2025/6/4 3:17:00

数据挖掘实训：天气数据分析与机器学习模型构建

随着气候变化对各行各业的影响日益加剧&#xff0c;精准的天气预测已经变得尤为重要。降雨预测在日常生活中尤其关键&#xff0c;例如农业、交通和灾害预警等领域。本文将通过机器学习方法&#xff0c;利用历史天气数据预测明天是否会下雨&#xff0c;具体内容包括数据预处理、…...

编程日记 2025/6/4 3:15:39

RAG 带来的一些问题

RAG (Retrieval-Augmented Generation) 提高了查询的准确性&#xff0c;但也引入了一些新的问题。主要问题集中在信息检索和生成模型的结合方式上&#xff0c;这些问题影响了系统的性能、效率和输出质量。以下是 RAG 带来的主要问题以及相应的解决方法。 1. 依赖外部检索系统的…...

编程日记 2025/6/4 3:18:03

大疆上云API基于源码部署

文章目录 大疆上云API基于源码部署注意事项1、学习官网2、环境准备注意事项3、注册成为DJI开发者4、下载前后端运行所需要的包/依赖前端依赖下载后端所需要的Maven依赖包 用到的软件可以在这里下载5、MySQL数据库安装安装MySQL启动MySQL服务在IDEA中配置MySQL的连接信息 6、Red…...

编程日记 2025/6/4 3:16:44

【Python系列】Python 中使用 pymysql 连接 MySQL 数据库进行数据查询

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…...

编程日记 2025/6/3 16:49:21

【数据结构学习笔记】19：跳表（Skip List）

介绍 跳表是一个能在 O ( n l o g n ) O(nlogn) O(nlogn)时间完成查找、插入、删除的数据结构&#xff0c;相比于树形结构优点就是很好写&#xff08;所以也用于实现Redis ZSet&#xff09;。其核心思想就是维护一个元素有序的&#xff0c;能随机提升索引层数的链表。最下面一…...

编程日记 2025/6/4 3:17:47

《计算机网络》课后探研题书面报告_网际校验和算法

网际校验和算法 摘 要 本文旨在研究和实现网际校验和&#xff08;Internet Checksum&#xff09;算法。通过阅读《RFC 1071》文档理解该算法的工作原理&#xff0c;并使用编程语言实现网际校验和的计算过程。本项目将对不同类型的网络报文&#xff08;包括ICMP、TCP、UDP等&a…...

编程日记 2025/6/4 3:16:12

【论文阅读+复现】High-fidelity Person-centric Subject-to-Image Synthesis

以人物为中心的主体到图像的高保真合成&#xff0c;CVPR2024 code&#xff1a;CodeGoat24/Face-diffuser: [CVPR2024] Official implementation of High-fidelity Person-centric Subject-to-Image Synthesis. paper&#xff1a;2311.10329 背景 研究问题&#xff1a;这篇文…...

编程日记 2025/6/4 3:17:16

Flink集成TDEngine来批处理或流式读取数据进行流批一体化计算（Flink SQL)拿来即用的案例

Flink 以其流批一体化的编程模型而备受青睐。它支持高吞吐、低延迟的实时流计算，同时在批处理方面也表现出色。Flink 提供了丰富的 API，如 DataStream API 和 DataSet API，方便开发者进行数据处理操作，包括转换、聚合、连接等，使得开发者能够轻松构建复杂的数据处理逻辑。…...

编程日记 2025/6/4 3:15:55

Zookeeper特性与节点数据类型详解

1、 Zookeeper介绍 ZooKeeper 是一个开源的分布式协调框架&#xff0c;是Apache Hadoop 的一个子项目&#xff0c;主要用来解决分布式集群中应用系统的一致性问题。Zookeeper 的设计目标是将那些复杂且容易出错的分布式一致性服务封装起来&#xff0c;构成一个高效可靠的原语集…...

编程日记 2025/6/4 3:16:27

C# HslCommunication库

C# HslCommunication库是一个用于建立TCP连接并进行Modbus通讯的库。下面将详细介绍如何使用该库进行TCP通讯。 首先&#xff0c;需要在C#项目中引用HslCommunication库。 创建一个TCP连接对象&#xff0c;可以使用HslCommunication.ModBus.ModbusTcpNet类&#xff0c;例如&am…...

编程日记 2025/5/31 18:26:45

springMVC实现文件上传

目录 一、创建项目 二、引入依赖 三、web.xml 四、编写上传文件的jsp页面 五、spring-mvc.xml 六、controller 七、运行 一、创建项目 二、引入依赖 <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.o…...

编程日记 2025/6/1 15:43:18

【深度学习】Windows系统Anaconda + CUDA + cuDNN + Pytorch环境配置

在做深度学习内容之前&#xff0c;为GPU配置anaconda CUDA cuDNN pytorch环境&#xff0c;在网络上参考了很多帖子&#xff0c;但pytorch的安装部分都有些问题或者比较复杂繁琐&#xff0c;这里总结了相对简单快速的配置方式 文章目录 AnacondaCUDAcuDNNpytorchtorchtorchau…...

编程日记 2025/6/3 13:40:38

springboot整合rabbitmq

1. 添加依赖 首先&#xff0c;在你的 pom.xml 文件中添加 RabbitMQ 的依赖&#xff1a; <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-amqp</artifactId> </dependency> 2. 配置 RabbitMQ …...

编程日记 2025/6/2 23:00:50

【React】脚手架进阶

目录 暴露webpack配置package.json的变化修改webpack.config.js配置less修改域名、端口号浏览器兼容处理处理跨域 暴露webpack配置 react-scripts对脚手架中的打包命令进行封装&#xff0c;如何暴露这些打包配置呢&#xff1f;上篇写到在package.json中的scripts配置项中有eje…...

编程日记 2025/6/4 4:14:16

Unreal Engine 5 (UE5) Metahuman 的头部材质

在图中&#xff0c;你展示了 Unreal Engine 5 (UE5) Metahuman 的头部材质部分&#xff0c;列出了头部材质的多个元素。以下是对每个部分的解释&#xff1a; 材质解释 Element 0 - MI_HeadSynthesized_Baked 作用&#xff1a; 这是 Metahuman 的主要头部材质&#xff0c;控制整…...

编程日记 2025/6/4 1:36:02

当自动包布机遇上Profinet转ModbusTCP网关，“妙啊”，工业智能“前景无限

在自动化控制技术日新月异的当下&#xff0c;Profinet与ModbusTCP这两种协议在工业通信领域占据着举足轻重的地位。ModbusTCP是基于以太网的串行通信协议&#xff0c;而Profinet则是依托工业以太网的现场总线协议。它们在数据传输速度、实时性表现以及兼容性等方面各具特色。不…...

编程日记 2025/6/2 23:00:19

Elasticsearch 批量导入数据（_bluk方法）

官方API&#xff1a;https://www.elastic.co/guide/en/elasticsearch/reference/current/docs-bulk.html 建议先看API POST /<索引名>/_bulk 格式要求&#xff1a; POST _bulk { "index" : { "_index" : "test", "_id" : &q…...

编程日记 2025/6/3 20:25:47

lammps应用于热电材料

文章目录 1.热传导理论1.热导率2.晶格振动3.晶体热容4.声子平均自由程5.傅里叶定律 2.lammps计算Ar热导率3.lammps模拟SiGe热电材料4.平衡分子动力学(EMD) 1.热传导理论 1.热导率 热传递机制随介质材料相的不同而改变&#xff1a;固体(热传导)、液体(热对流)、气体(对流和辐射…...

编程日记 2025/6/3 5:06:40

SAP资产盘盈盘亏的过账处理、入账价值错误调整、资产减值准备

文章目录 一、SAP资产盘盈盘亏处理1、ABNAN盘盈 &#xff08;往年资产&#xff09; ABZON (当年资产&#xff09;2、ABAVN盘亏 二、资产价值入账错了&#xff08;价值多了或少了&#xff09;&#xff0c;怎么调账1、价值少了2、价值多了 三、资产减值准备1、启用重估2、指定间隔…...

编程日记 2025/6/2 23:00:34

Adobe与MIT推出自回归实时视频生成技术CausVid。AI可以边生成视频边实时播放！

传统的双向扩散模型&#xff08;顶部&#xff09;可提供高质量的输出&#xff0c;但存在显著的延迟&#xff0c;需要 219 秒才能生成 128 帧的视频。用户必须等待整个序列完成才能查看任何结果。相比之下CausVid将双向扩散模型提炼为几步自回归生成器&#xff08;底部&#xff…...

编程日记 2025/6/4 4:40:06

MYSQL学习笔记(一)：准备数据和数据库的最基本命令

前言&#xff1a; 学习和使用数据库可以说是程序员必须具备能力&#xff0c;这里将更新关于MYSQL的使用讲解&#xff0c;大概应该会更新30篇&#xff0c;涵盖入门、进阶、高级(一些原理分析);这一篇是入门准备数据和一些关于数据库的操作命令&#xff1b;虽然MYSQL命令很多&…...

编程日记 2025/6/4 4:39:50

求矩阵不靠边元素之和（PTA）C语言

求矩阵的所有不靠边元素之和&#xff0c;矩阵行的值m从键盘读入(2<m<10)&#xff0c;调用自定义函数Input实现矩阵元素从键盘输入&#xff0c;调用Sum函数实现求和。(只考虑float型&#xff0c;且不需考虑求和的结果可能超出float型能表示的范围)。 函数接口定义&#x…...

编程日记 2025/6/4 4:41:57

仿infobip模板功能-可通过占位符配置模板内容

模仿infobip制作的模板功能&#xff0c;正文可在任意位置加参数的功能。如下图所示&#xff1a;在正文中通过{{\d}}进行占位&#xff0c;在使用模板时&#xff0c;可在此位置自定制内容&#xff0c;并预览效果。 代码&#xff1a; <template><div class"templa…...

编程日记 2025/6/4 4:41:10

STM32第6章、WWDG

一、简介 WWDG&#xff1a;全称Window watchdog&#xff0c;即窗口看门狗&#xff0c;本质上是一个能产生系统复位信号和提前唤醒中断的计数器。 特性&#xff1a; 是一个递减计数器。 看门狗被激活后&#xff0c; 当递减计数器值从 0x40减到0x3F时会产生复位&#xff08;即T6位…...

编程日记 2025/6/4 4:41:41

没有正确使用HTTP Range Request，导致访问Azure Blob存储的视频没有实现流式播放

引文&#xff1a; 组里的小伙伴在修改视频播放相关的代码&#xff0c;修改之前的方案使用CDN转发&#xff0c;可以实现流式播放&#xff0c;修改之后的代码因为没有正确的使用Http Range Request, 导致画面访问Azure Blob存储的视频没有实现流式播放&#xff0c;整理下线索在这…...

编程日记 2025/6/3 10:15:15

React中Fiber树构建过程详解——react中render一个App组件(包含子组件)的流程详解

在 React 中&#xff0c;渲染一个包含子组件的组件涉及一系列底层流程&#xff0c;包括构建虚拟 DOM&#xff08;React Element&#xff09;、协调&#xff08;Reconciliation&#xff09;、Fiber 树管理和最终的 DOM 操作。以下是一个从底层解析的详细流程&#xff1a; 1. 初始…...

编程日记 2025/6/4 14:28:14

机器学习赋能的智能光子学器件系统研究与应用

在人工智能与光子学设计融合的背景下&#xff0c;科研的边界持续扩展&#xff0c;创新成果不断涌现。从理论模型的整合到光学现象的复杂模拟&#xff0c;从数据驱动的探索到光场的智能分析&#xff0c;机器学习正以前所未有的动力推动光子学领域的革新。据调查&#xff0c;目前…...

编程日记 2025/6/4 3:55:46

晨辉面试抽签和评分管理系统之七：面试成绩核算的三种方式

晨辉面试抽签和评分管理系统&#xff08;下载地址:www.chenhuisoft.cn&#xff09;是公务员招录面试、教师资格考试面试、企业招录面试等各类面试通用的考生编排、考生入场抽签、候考室倒计时管理、面试考官抽签、面试评分记录和成绩核算的面试全流程信息化管理软件。提供了考生…...

编程日记 2025/6/4 4:40:38

语音合成的预训练模型

语音合成的预训练模型 与 ASR（语音识别）和音频分类任务相比，语音合成的预训练模型检查点明显较少。在 Hugging Hub 上，可以找到近 300 个适合的检查点。 在这些预训练模型中，重点关注两种在 Huggingface Transformers 库中开箱即用的架构——SpeechT5 和 Massive Multili…...

编程日记 2025/6/4 4:40:54

Windows怎么搭建rust环境?

在Windows上搭建Rust开发环境相对简单&#xff0c;主要步骤如下&#xff1a; ### 1. 安装Rust 最简单的方法是使用官方提供的安装脚本。打开命令提示符&#xff08;Command Prompt&#xff09;或PowerShell&#xff0c;然后运行以下命令来下载并安装Rust&#xff1a; bash cu…...

编程日记 2025/6/2 23:35:52

【Flink】Flink内存管理

Flink内存整体结构图&#xff1a; JobManager内存管理 JVM 进程总内存(Total Process Memory)Flink总内存(Total Flink Memory)&#xff1a;JVM进程总内存减去JVM Metaspace(元空间)和JVM Overhead(运行时开销)上图解释&#xff1a; JVM进程总内存为2G;JVM运行时开销(JVM Overh…...

编程日记 2025/6/2 8:47:34

React方向：react中5种Dom的操作方式

1、通过原生JS获取Dom去操作 通过document.querySelector(#title)原生js的方式去拿到dom节点&#xff0c;然后去进行操作。 import {Component} from "react";class App extends Component {//定义获取Dom的函数handleGetDom(){let title document.querySelector(#t…...

编程日记 2025/6/2 23:37:45

K8s数据存储之详解（Detailed Explanation of K8s Data Storage）

K8s数据存储相关概念详解&#xff08;临时存储&#xff0c;节点存储&#xff0c;网络存储&#xff0c;PV/PVC&#xff09; 本篇文章分享一下存储卷和数据持久化的相关概念&#xff1a; 存储卷概述 临时存储卷&#xff08;Ephemeral Volumes&#xff09; 节点存储卷&#xff…...

编程日记 2025/6/2 22:19:59

PyTorch 中的 Dropout 解析

文章目录 一、Dropout 的核心作用数值示例&#xff1a;置零与缩放**训练阶段****推理阶段** 二、Dropout 的最佳使用位置与具体实例解析1. 放在全连接层后2. 卷积层后的使用考量3. BatchNorm 层与 Dropout 的关系4. Transformer 中的 Dropout 应用 三、如何确定 Dropout 的位置…...

编程日记 2025/6/2 8:26:06

计算机网络 （41）文件传送协议

前言 一、文件传送协议&#xff08;FTP&#xff09; 概述&#xff1a; FTP&#xff08;File Transfer Protocol&#xff09;是互联网上使用得最广泛的文件传送协议。FTP提供交互式的访问&#xff0c;允许客户指明文件的类型与格式&#xff08;如指明是否使用ASCII码&#xff0…...

编程日记 2025/6/4 6:55:23

AOSP 14及以上userdebug无法调试的问题

参考链接&#xff1a;原文...

编程日记 2025/6/2 23:36:23

【Vue】点击侧边导航栏，右侧main对应显示

需求&#xff1a;点击侧边导航栏&#xff0c;右侧main对应显示 通过v-if或v-show等指令来控制不同内容的显示隐藏来实现 注意&#xff1a; 使用v-if时候进行导航栏切换&#xff0c;右侧显示区域可能会出现样式错乱&#xff1b;使用v-show则不会出现此错误 <template>&…...

编程日记 2025/6/2 23:37:12

Python Selenium 库学习指南

Python Selenium 库学习指南 目录 Selenium 基础介绍 Selenium 是什么安装 SeleniumSelenium 的工作原理 Selenium 基本用法 启动浏览器定位元素常见操作&#xff1a;点击、输入、滚动 高级用法 切换窗口与标签页模拟鼠标操作与键盘输入动态加载的网页处理 等待机制 显式等待…...

编程日记 2025/6/1 10:25:56