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

【贪心算法】简介

news 来源：原创 2025/8/22 1:31:56

1.贪心算法

 贪心策略：解决问题的策略，局部最优----》全局最优

（1）把解决问题的过程分成若干步

（2）解决每一步的时候，都选择当前看起来的“最优”的算法

（3）“希望”得到全局最优解

例一：找零问题

只有一张50元，买了4元，如何找零？（店家有[20,10,5,1]）

解答：50-4=46，来凑46

首先找最大的20元，46-20=26

再找最大的20元，26-6=6

再找20元太多了，再找10元太多了，再找5元，6-5=1

再找5元太多了，再找1元，1-1=0

例二：最小路径和

例三：背包问题

背包最大容量：8

123
体积v541
价值w1071

从体积考虑：一直选体积最小的1，选了8个3号物品 

从价值考虑：一直选当前可选的价值最高的，1号物品，3个3号物品

按性价比考虑：w/v：2，1.75，1一直选择性价比最高的，1号物品，3个3号物品

2.贪心算法的特点

（1）贪心策略的提出是没有标准和模板的

（2）可能每一道题的贪心策略都是不相同的

3.贪心策略的正确性

因为有可能“贪心策略”是一个错误的方法

正确的贪心策略需要“证明”（数学中的证明方法都可以）

证明：找零问题的正确性

[20,10,5,1]

假设最优解为：A,B,C,D

根据题目可知，能用面额大的尽量用

则B<=1,C<=1,D<=4

假设贪心解为：[a,b,c,d]

最优解为：[A,B,C,D]

因此有：

（1）a>=A

（2）a>A不可能，因为B<=1,C<=1,D<=4，加在一起10+5+1*4=19无法到达20

（3）a=A

（4）b>=B

（5）b>B不可能，因为C<=1,D<=4，加在一起5+1*4=9无法到达10

（6）b=B

相关文章：

【贪心算法】简介

1.贪心算法 贪心策略&#xff1a;解决问题的策略&#xff0c;局部最优----》全局最优 &#xff08;1&#xff09;把解决问题的过程分成若干步 &#xff08;2&#xff09;解决每一步的时候&#xff0c;都选择当前看起来的“最优”的算法 &#xff08;3&#xff09;“希望”得…...

编程日记 2025/8/22 1:31:56

狮子座大数据分析（python爬虫版）

十二星座爱情性格 - 星座屋 首先找到一个星座网站&#xff0c;作为基础内容&#xff0c;来获取信息 网页爬取与信息提取 我们首先利用爬虫技术&#xff08;如 Python 中的 requests 与 BeautifulSoup 库&#xff09;获取页面内容。该页面&#xff08;xzw.com/astro/leo/&…...

编程日记 2025/8/19 10:14:01

【商城实战(20)】商品管理功能深化实战

【商城实战】专栏重磅来袭&#xff01;这是一份专为开发者与电商从业者打造的超详细指南。从项目基础搭建&#xff0c;运用 uniapp、Element Plus、SpringBoot 搭建商城框架&#xff0c;到用户、商品、订单等核心模块开发&#xff0c;再到性能优化、安全加固、多端适配&#xf…...

编程日记 2025/8/22 17:12:23

YC 孵化项目 Pinch：实时语音翻译视频会议平台；Mistral OCR：能处理多语言多模态复杂文档丨日报

开发者朋友们大家好&#xff1a; 这里是 「RTE 开发者日报」 &#xff0c;每天和大家一起看新闻、聊八卦。 我们的社区编辑团队会整理分享 RTE&#xff08;Real-Time Engagement&#xff09; 领域内「有话题的 技术 」、「有亮点的 产品 」、「有思考的 文章 」、「有态度的 …...

编程日记 2025/8/21 16:37:58

数据库原理6

1.数据是信息的载体 2.数据库应用程序人员的主要职责&#xff1a;编写应用系统的程序模块 3.关系规范化理论主要属于数据库理论的研究范畴 4.数据库主要有检索和修改&#xff08;包括插入&#xff0c;删除&#xff0c;更新&#xff09;两大操作 5.概念模型又称为语义模型。…...

编程日记 2025/8/22 17:05:22

深度学习与大模型基础-向量

大家好&#xff01;今天我们来聊聊向量&#xff08;Vector&#xff09;。别被这个词吓到&#xff0c;其实向量在我们的生活中无处不在&#xff0c;只是我们没注意罢了。 1. 向量是什么&#xff1f; 简单来说&#xff0c;向量就是有大小和方向的量。比如你从家走到学校&#x…...

编程日记 2025/8/19 16:00:20

OpenManus：3小时复刻 Manus（OpenManus安装指南）

项目地址&#xff1a;GitHub - mannaandpoem/OpenManus: No fortress, purely open ground. OpenManus is Coming. 安装指南 我们提供两种安装方式。推荐使用方式二&#xff08;uv&#xff09;&#xff0c;因为它能提供更快的安装速度和更好的依赖管理。 方式一&#xff1a;使…...

编程日记 2025/8/22 17:05:21

2025年渗透测试面试题总结-快某手-安全实习生（一面、二面）（题目+回答）

网络安全领域各种资源&#xff0c;学习文档&#xff0c;以及工具分享、前沿信息分享、POC、EXP分享。不定期分享各种好玩的项目及好用的工具&#xff0c;欢迎关注。 目录 快某手-安全实习生 一面 一、Linux操作&#xff1a;查看进程PID的5种方法 二、Elasticsearch&#x…...

编程日记 2025/8/20 13:51:40

【微信小程序】uniapp开发微信小程序

uniapp开发微信小程序 1、上拉加载 下拉刷新 import { onReachBottom, onPullDownRefresh } from dcloudio/uni-app;配置允许下拉刷新&#xff1a; {"path" : "pages/pet/pet","style" : {"navigationBarTitleText" : ""…...

编程日记 2025/8/22 4:54:23

动态规划_最大子数组和

53. 最大子数组和 给你一个整数数组 nums &#xff0c;请你找出一个具有最大和的连续子数组&#xff08;子数组最少包含一个元素&#xff09;&#xff0c;返回其最大和。 子数组是数组中的一个连续部分。 示例 1&#xff1a;输入&#xff1a;nums [-2,1,-3,4,-1,2,1,-5,4] …...

编程日记 2025/8/22 17:03:33

从零开始的python学习（五）P71+P72+P73+P74

本文章记录观看B站python教程学习笔记和实践感悟&#xff0c;视频链接&#xff1a;【花了2万多买的Python教程全套&#xff0c;现在分享给大家&#xff0c;入门到精通(Python全栈开发教程)】 https://www.bilibili.com/video/BV1wD4y1o7AS/?p6&share_sourcecopy_web&v…...

编程日记 2025/8/22 17:08:38

Vue3实战学习（Element-Plus常用组件的使用(输入框、下拉框、单选框多选框、el-image图片)）(上)(5)

目录 一、Vue3工程环境配置、项目基础脚手架搭建、Vue3基础语法、Vue3集成Element-Plus的详细教程。(博客链接如下) 二、Element-Plus常用组件使用。 &#xff08;1&#xff09;el-input。(input输入框) <1>正常状态的el-input。 <2>el-input的disable状态。 <3…...

编程日记 2025/8/22 17:09:18

HarmonyOS学习第18天:多媒体功能全解析

一、开篇引入 在当今数字化时代&#xff0c;多媒体已经深度融入我们的日常生活。无论是在工作中通过视频会议进行沟通协作&#xff0c;还是在学习时借助在线课程的音频讲解加深理解&#xff0c;亦或是在休闲时光用手机播放音乐放松身心、观看视频打发时间&#xff0c;多媒体功…...

编程日记 2025/8/22 17:08:39

多模态融合的分类、跨模态对齐的方法

两者的主要区别 维度扩模态对齐扩模态融合目标对齐模态间的表示&#xff0c;使其语义一致融合模态间的信息&#xff0c;生成联合表示关注点模态间的相似性和语义一致性模态间的互补性和信息整合空间映射到共享的公共语义空间生成新的联合特征空间方法对比学习、共享空间、注意…...

编程日记 2025/8/22 17:12:23

软件高级架构师 - 软件工程

补充中 测试 测试类型 静态测试 动态测试 测试阶段 单元测试中&#xff0c;包含性能测试&#xff0c;如下&#xff1a; 集成测试中&#xff0c;包含以下&#xff1a; 维护 遗留系统处置 高水平低价值&#xff1a;采取集成 对于这类系统&#xff0c;采取 集成 的方式&…...

编程日记 2025/8/22 17:06:50

Uniapp项目运行到微信小程序、H5、APP等多个平台教程

摘要&#xff1a;Uniapp作为一款基于Vue.js的跨平台开发框架&#xff0c;支持“一次开发&#xff0c;多端部署”。本文将手把手教你如何将Uniapp项目运行到微信小程序、H5、APP等多个平台&#xff0c;并解析常见问题。 一、环境准备 在开始前&#xff0c;请确保已安装以下工具…...

编程日记 2025/8/22 7:19:11

【JavaWeb12】数据交换与异步请求：JSON与Ajax的绝妙搭配是否塑造了Web的交互革命?

文章目录 &#x1f30d;一. 数据交换--JSON❄️1. JSON介绍❄️2. JSON 快速入门❄️3. JSON 对象和字符串对象转换❄️4. JSON 在 java 中使用❄️5. 代码演示 &#x1f30d;二. 异步请求--Ajax❄️1. 基本介绍❄️2. JavaScript 原生 Ajax 请求❄️3. JQuery 的 Ajax 请求 &a…...

编程日记 2025/8/22 17:12:24

2025-03-10 吴恩达机器学习1——机器学习概述

文章目录 1 监督学习1.1 回归1.2 分类 2 无监督学习2.1 聚类2.2 异常检测2.3 降维 3 使用 Jupyter Notebook ​ 1959 年&#xff0c;Arthur Samuel 将机器学习定义如下&#xff1a; ​ Field of study that gives computers the ability to learn without being explicitly pro…...

编程日记 2025/8/22 5:20:56

Spring Boot整合WebSocket

目录 ?引言 1.WebSocket 基础知识 ?1.1 什么是 WebSocket&#xff1f; ?1.2 WebSocket 的应用场景 ?2.Spring Boot WebSocket 整合步骤 2.1 创建 Spring Boot 项目 2.2 添加 Maven 依赖 2.3 配置 WebSocket 2.4 创建 WebSocket 控制器 2.5 创建前端页面 引言 在…...

编程日记 2025/8/22 2:37:45

PostgreSQL - Windows PostgreSQL 下载与安装

Windows PostgreSQL 下载与安装 1、PostgreSQL 下载 下载地址&#xff1a;https://www.enterprisedb.com/downloads/postgres-postgresql-downloads 2、PostgreSQL 安装 启动安装程序 -> 点击 【Next】 指定安装路径 -> 点击 【Next】 默认勾选 -> 点击 【Next】 指…...

编程日记 2025/8/22 17:03:33

【Java面试题汇总】Java面试100道最新合集！

1.说说你对面向对象的理解 得分点 封装,继承,多态、概念、实现方式和优缺点 面向对象的三大基本特征是&#xff1a;封装、继承、多态。 封装&#xff1a;将对象的状态和行为包装在一个类中并对外界隐藏实现的细节&#xff0c;可以通过访问修饰符控制成员的访问权限&#xff0c…...

编程日记 2025/8/22 17:05:24

【LLM】kimi 1.5模型架构和训练流程

note 推出两个多模态模型&#xff0c;深度思考模型 long-CoT 对标 o1&#xff0c;通用模型 short-CoT 模型对标 gpt-4o。 文章目录 note一、kimi 1.5模型训练流程预训练SFT训练long-CoT SFTRL训练long2short 小结Reference 一、kimi 1.5模型训练流程 推出两个多模态模型&…...

编程日记 2025/8/22 17:07:32

Android Studio 配置国内镜像源

Android Studio版本号&#xff1a;2022.1.1 Patch 2 1、配置gradle国内镜像&#xff0c;用腾讯云 镜像源地址&#xff1a;https\://mirrors.cloud.tencent.com/gradle 2、配置Android SDK国内镜像 地址&#xff1a;Index of /AndroidSDK/...

编程日记 2025/8/22 17:05:24

永洪科技深度分析实战，零售企业的销量预测

随着人工智能技术的不断发展&#xff0c;智能预测已经成为各个领域的重要应用之一。现在&#xff0c;智能预测技术已经广泛应用于金融、零售、医疗、能源等领域&#xff0c;为企业和个人提供决策支持。 智能预测技术通过分析大量的数据&#xff0c;利用机器学习和深度学习算法…...

编程日记 2025/8/22 17:10:14

Pytorch实现之利用CGAN鉴别真假图像

简介 简介：利用生成对抗网络来鉴别是真图像还是假图像。 论文题目：Detection and Identification of Fake Images Using Conditional Generative Adversarial Networks (CGANs) （基于条件生成对抗网络（CGAN）的假图像检测与识别） 会议：16th IEEE International Confer…...

编程日记 2025/8/22 13:43:24

开源模型时代的 AI 开发革命：Dify 技术深度解析

开源模型时代的AI开发革命&#xff1a;Dify技术深度解析 引言&#xff1a;AI开发的开源新纪元 在生成式AI技术突飞猛进的2025年&#xff0c;开源模型正成为推动行业创新的核心力量。据统计&#xff0c;全球超过80%的AI开发者正在使用开源模型构建应用&#xff0c;这一趋势不仅…...

编程日记 2025/8/18 3:04:16

网络DNS怎么更改?

访问速度慢或某些网站无法打开?改变网络DNS设置可能会帮助解决这些问题。本文将详细介绍如何更改网络DNS&#xff0c;包括更改的原因、具体步骤。 一、为什么要更改DNS? 更改DNS的原因有很多&#xff0c;以下是一些主要的考虑因素&#xff1a;某些公共DNS服务器的响应速度比…...

编程日记 2025/8/22 17:08:40

计算机网络篇：基础知识总结与基于长期主义的内容更新

基础知识总结 和 MySQL 类似&#xff0c;我同样花了一周左右的时间根据 csview 对计算机网络部分的八股文进行了整理&#xff0c;主要的内容包括&#xff1a;概述、TCP 与 UDP、IP、HTTP&#xff0c;其中我个人认为最重要的是 TCP 这部分的内容。 在此做一篇目录索引&#xf…...

编程日记 2025/8/19 17:53:13

使用miniforge安装python并用pycharm打开使用

1.安装miniforge 参考文章:https://blog.csdn.net/loujiand/article/details/119976302 https://blog.csdn.net/qq_41946216/article/details/129481760 下载地址&#xff1a; 先从github下载miniforge&#xff1a;https://github.com/conda-forge/miniforge 2.使用conda命令…...

编程日记 2025/8/20 4:52:54

如何实现wordpress搜索自字义字段内容

有些网站需要根据自定义段字的内容来做为搜索项&#xff0c;比如&#xff0c;房产中介公司wordpress网站&#xff0c;需要搜索同一区域内容的楼盘&#xff0c;然后展示出内容。 不废话了&#xff0c;在function.php直接加上代码 add_action(posts_search, function($search, …...

编程日记 2025/8/21 17:29:19

【华为OD机考真题】- 星际篮球争霸赛（Java）

1. 题目描述 具体题目描述如下&#xff1a; 在星球争霸篮球赛对抗赛中&#xff0c;最大的宇宙战队希望每个人都能拿到 MVP&#xff0c;MVP 的条件是单场最高分得分获得者。 可以并列&#xff0c;所以宇宙战队决定在比赛中&#xff0c;尽可能让更多队员上场,并且让所有得分的选手…...

编程日记 2025/8/16 12:35:25

LeetCode 376. 摆动序列 java题解

https://leetcode.cn/problems/wiggle-subsequence/description/ 只要不满足摆动条件&#xff0c;就不更新count和prediff 当 prevDiff 取等号时&#xff0c;比如 prevDiff 0&#xff0c;在这种情况下&#xff0c;如果 currDiff > 0&#xff0c;说明从持平状态转变为上升…...

编程日记 2025/8/20 16:51:56

PyCharm 接入 DeepSeek、OpenAI、Gemini、Mistral等大模型完整版教程（通用）！

PyCharm 接入 DeepSeek、OpenAI、Gemini、Mistral等大模型完整版教程&#xff08;通用&#xff09;&#xff01; 当我们成功接入大模型时&#xff0c;可以选中任意代码区域进行解答&#xff0c;共分为三个区域&#xff0c;分别是选中区域、提问区域以及回答区域&#xff0c;我…...

编程日记 2025/8/22 11:17:04

使用RabbitMQ实现流量削峰填谷

原理 流量削峰填谷是指在面对突发的高流量时&#xff0c;通过消息队列将瞬时大量请求暂时存储起来&#xff0c;并逐步处理这些请求&#xff0c;从而避免系统过载。RabbitMQ 作为消息中间件可以很好地支持这一需求&#xff0c;特别是结合其延时消息插件&#xff08;rabbitmq_de…...

编程日记 2025/8/19 6:10:15

Apache Commons Lang3 和 Commons Net 详解

目录 1. Apache Commons Lang3 1.1 什么是 Apache Commons Lang3&#xff1f; 1.2 主要功能 1.3 示例代码 2. Commons Net 2.1 什么是 Commons Net&#xff1f; 2.2 主要功能 2.3 示例代码 3. 总结 3.1 Apache Commons Lang3 3.2 Commons Net 3.3 使用建议 4. 参考…...

编程日记 2025/8/22 4:47:11

ACE学习2——write transaction

用于处理缓存行的数据更新到主内存&#xff08;main memory&#xff09;的操作。 以下是用于更新主内存的几种事务类型&#xff1a; WriteBack&#xff1a; WriteBack事务用于将cache中的dirty态的cacheline写回主存&#xff0c;以释放cache中的cacheline&#xff0c;用于存…...

编程日记 2025/8/20 19:16:42

mac本地安装运行Redis-单机

记录一下我以前用的连接服务器的跨平台SSH客户端。 因为还要准备毕设...... 服务器又过期了&#xff0c;只能把redis安装下载到本地了。 目录 1.github下载Redis 2.安装homebrew 3.更新GCC 4.自行安装Redis 5.通过 Homebrew 安装 Redis 安装地址&#xff1a;https://git…...

编程日记 2025/8/16 12:46:08

sparkTTS window 安装

SparkTTS 的简介 Spark-TTS是一种基于SpardAudio团队提出的 BiCodec 构建的新系统&#xff0c;BiCodec 是一种单流语音编解码器&#xff0c;可将语音策略性地分解为两种互补的标记类型&#xff1a;用于语言内容的低比特率语义标记和用于说话者特定属性的固定长度全局标记。这种…...

编程日记 2025/8/16 11:53:53

颠覆语言认知的革命！神经概率语言模型如何突破人类思维边界？

颠覆语言认知的革命&#xff01;神经概率语言模型如何突破人类思维边界&#xff1f; 一、传统模型的世纪困境&#xff1a;当n-gram遇上"月光族难题" 令人震惊的案例&#xff1a;2012年Google语音识别系统将 用户说&#xff1a;“我要还信用卡” 系统识别&#xff…...

编程日记 2025/8/21 12:25:28

大语言模型从理论到实践（第二版）-学习笔记（绪论）

大语言模型的基本概念 1.理解语言是人工智能算法获取知识的前提 2.语言模型的目标就是对自然语言的概率分布建模 3.词汇表 V 上的语言模型&#xff0c;由函数 P(w1w2 wm) 表示&#xff0c;可以形式化地构建为词序列 w1w2 wm 的概率分布&#xff0c;表示词序列 w1w2 wm…...

编程日记 2025/8/19 5:42:47

2.1 Vite + Vue 3 + TS 项目脚手架深度配置

文章目录 **一、环境准备与技术选型****二、项目初始化与基础架构****三、工程化配置深度优化****四、代码规范与质量保障****五、Vue 3 深度集成****六、TypeScript 高级配置****七、第三方库集成****八、构建优化策略****九、企业级最佳实践****十、扩展配置参考****本章核心…...

编程日记 2025/8/20 1:20:44

deepin安装rust

一、环境 操作系统&#xff1a;deepin V23 二、下载离线安装包 下载链接&#xff1a; https://forge.rust-lang.org/infra/other-installation-methods.html https://static.rust-lang.org/dist/rust-1.85.0-x86_64-unknown-linux-gnu.tar.xz 当时最新稳定版本为1.85。 三、解…...

编程日记 2025/8/19 3:05:36

【愚公系列】《Python网络爬虫从入门到精通》045-Charles的SSL证书的安装

标题详情作者简介愚公搬代码头衔华为云特约编辑&#xff0c;华为云云享专家&#xff0c;华为开发者专家&#xff0c;华为产品云测专家&#xff0c;CSDN博客专家&#xff0c;CSDN商业化专家&#xff0c;阿里云专家博主&#xff0c;阿里云签约作者&#xff0c;腾讯云优秀博主&…...

编程日记 2025/8/21 16:33:32

UniApp 运行的微信小程序如何进行深度优化

UniApp 运行的微信小程序如何进行深度优化 目录 引言性能优化 1. 减少包体积2. 优化页面加载速度3. 减少 setData 调用4. 使用分包加载 代码优化 1. 减少不必要的代码2. 使用条件编译3. 优化图片资源 用户体验优化 1. 优化交互体验2. 预加载数据3. 使用骨架屏 调试与监控 1. …...

编程日记 2025/8/16 10:20:49

Hadoop安装文件解压报错：无法创建符号链接。。。

您可能需要管理员身份运行winRAR; 客户端没有所需的特权&#xff1b; cmd进入该目录下&#xff0c;输入命令(本地解压)&#xff1a;start winrar x -y hadoop-2.10.1.tar.gz...

编程日记 2025/8/16 12:02:41

Redis6.2.6下载和安装

简介 Redis 是一种开源&#xff08;BSD 许可&#xff09;、内存中数据结构存储&#xff0c;用作数据库、缓存和消息代理。Redis 提供了数据结构&#xff0c;例如字符串、散列、列表、集合、带有范围查询的排序集合、位图、超级日志、地理空间索引和流。Redis 内置复制、Lua 脚…...

编程日记 2025/8/16 11:24:47

【AI】神经网络｜机器学习——图解Transformer（完整版）

Transformer是一种基于注意力机制的序列模型，最初由Google的研究团队提出并应用于机器翻译任务。与传统的循环神经网络（RNN）和卷积神经网络（CNN）不同，Transformer仅使用自注意力机制（self-attention）来处理输入序列和输出序列，因此可以并行计算，极大地提高了计算效率…...

编程日记 2025/8/21 2:33:54

超过 37000 台 VMwareESXi 服务器可能受到持续攻击威胁

近日&#xff0c;威胁监测平台影子服务器基金会&#xff08;The Shadowserver Foundation&#xff09;发布报告&#xff0c;指出超 3.7 万个互联网暴露的威睿&#xff08;VMware&#xff09;ESXi 实例存在严重安全隐患&#xff0c;极易受到 CVE-2025-22224 漏洞的攻击。该漏洞属…...

编程日记 2025/8/21 10:48:41

多宠识别：基于计算机视觉的智能宠物管理系统架构解析

一、行业痛点与技术方案演进 在多宠家庭场景中&#xff0c;传统方案面临三大技术瓶颈&#xff1a; 1. 生物特征混淆&#xff1a;同品种/毛色宠物识别准确率低于65% 2. 动态场景适应&#xff1a;进食/奔跑状态下的误检率达30% 3. 数据孤岛问题&#xff1a;离线设备无法实现持续…...

编程日记 2025/8/16 9:53:14

mobaxterm，闪退处理方法

mobaxterm&#xff0c;使用过程中突然闪退&#xff0c; 具体表现为&#xff1a;登录远程服务器成功&#xff0c;开始闪退 登录失败不闪退 一开始以为是&#xff0c;服务器做了控制&#xff0c;后来才发现是mobaxterm软件的问题。 问题解决方法&#xff1a; 勾选工具ssh&…...

编程日记 2025/8/16 10:01:37