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

贪心算法解题框架+经典反例分析,效率提升300%

贪心算法是一种在每一步选择中都采取当前状态下的最优决策,从而希望最终达到全局最优解的算法策略。以下从其定义、特点、一般步骤、应用场景及实例等方面进行讲解:

定义与基本思想

• 贪心算法在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,它所做出的仅仅是在某种意义上的局部最优解。它通常以自顶向下的方式进行,每一步都选择当前的最优解,而不考虑之前或之后的步骤。
特点
• 无后效性:即某个状态以前的过程不会影响以后的状态,只与当前状态有关。这使得贪心算法在每一步决策时,只需要考虑当前的状态信息,而不必考虑整个问题的历史信息。
• 局部最优选择:贪心算法在每一步都选择当前看起来最优的决策,而不考虑整体的最优解。这种局部最优选择策略是贪心算法的核心特点,也是其与动态规划等其他算法的主要区别之一。

一般解题步骤

  1. 问题分析:明确问题的目标和约束条件,确定问题是否适合用贪心算法求解。一般来说,如果问题具有最优子结构性质和贪心选择性质,就可以考虑使用贪心算法。
  2. 贪心策略设计:根据问题的特点,设计一个贪心策略。贪心策略的好坏直接影响算法的正确性和效率。例如,在活动安排问题中,贪心策略可以是按照活动结束时间的先后顺序来选择活动。
  3. 算法实现:根据贪心策略,实现具体的算法。在实现过程中,需要注意数据结构的选择和操作,以提高算法的效率。
  4. 正确性证明:虽然贪心算法通常比较直观,但为了确保算法的正确性,需要对贪心策略进行证明。证明方法通常有归纳法、反证法等。

应用场景

一、区间调度问题

【核心思路】:通过排序区间端点,选择不重叠区间的最大数量或最优安排方式。

【解决思路】:

  1. 排序策略:按区间右端点从小到大排序。
  2. 贪心选择:依次选择最早结束且不与已选区间重叠的区间。
  3. 优化目标:最大化不重叠区间数量。

【经典题型】:
线段覆盖:选择最多不重叠线段,按右端点排序后贪心选择。
纪念品分组:将物品按价格排序后,双指针组合最大可能的配对,使组数最少。
智力大冲浪:按扣款数从大到小排序,尽量在截止时间前完成任务以减少罚款5。
种树问题:按区间右端点排序,从后向前填充以满足多个区间需求。
洛谷例题:P1803(线段覆盖)、P1094(纪念品分组)、P1230(智力大冲浪)、P1250(种树)。

参考P1094纪念品分组

二、排序选择问题

【核心思路】:通过排序后选择局部最优解,通常与性价比、时间顺序相关。

【解决思路】:

  1. 部分背包:按单位价值(价值/重量)降序排序,优先拿取高性价比物品。
  2. 排队接水:按接水时间升序排序,最小化总等待时间。

【 典型场景】:
◦ 部分背包问题:按单位价值排序,优先拿取性价比高的物品37。
◦ 排队接水:按接水时间升序排列,总等待时间最小35。
◦ 陶陶摘苹果:按摘取所需体力排序,优先摘取消耗小的苹果3。
• 洛谷例题:P2240(部分背包)、P1223(排队接水)、P1478(陶陶摘苹果)、P4995(跳跳!)。

参考P2240部分背包问题

三.构造最优解问题

【核心思路】:通过删除或调整元素构造最小/最大值,需处理边界条件
【高频题目】:
◦ 删数问题:删除k个数字使剩余数最小,需从左到右删除第一个递减序列的前驱389。
◦ 铺设道路:通过相邻差值累加计算最小天数,递推处理连续区间9。
◦ 分组问题:将连续数值分组,使用栈维护最小长度的最大可能9。
• 洛谷例题:P1106(删数问题)、P5019(铺设道路)、P4447(AHOI2018分组)。

参考P1106删数问题

四、反悔贪心与堆优化

核心思路:通过**优先队列(堆)**动态维护当前最优选择,支持撤销操作。
• 典型应用:
◦ 合并果子:每次合并最小的两堆,用小根堆优化时间复杂度7。
◦ 推销员问题:结合最大疲劳值与距离的权衡,分情况选择最优策略10。
• 洛谷例题:P1090(合并果子)、P2672(推销员)。

参考P1090合并果子

五、特殊策略问题

核心思路:需结合题目特性设计贪心规则,如数学归纳或调整法。
• 常见题型:
◦ 小A的糖果:遍历调整相邻盒子的糖果数,确保总和不超过限制37。
◦ 跳跳!:在最大和最小值之间跳跃,最大化总能量3。
◦ 哈夫曼编码:合并频率最小的节点,构造最优前缀树25。
• 洛谷例题:P3817(小A的糖果)、P4995(跳跳!)、P2168(荷马史诗)。

相关文章:

贪心算法解题框架+经典反例分析,效率提升300%

贪心算法是一种在每一步选择中都采取当前状态下的最优决策,从而希望最终达到全局最优解的算法策略。以下从其定义、特点、一般步骤、应用场景及实例等方面进行讲解: 定义与基本思想 • 贪心算法在对问题求解时,总是做出在当前看来是最好的选…...

策略设计模式-下单

1、定义一个下单context类 通过这类来判断具体使用哪个实现类,可以通过一些枚举或者条件来判断 import com.alibaba.fastjson.JSON; import com.tc.common.exception.BusinessException; import com.tc.common.user.YjkUserDetails; import com.tc.institution.cons…...

Go加spy++隐藏窗口

最近发现有些软件的窗口就像狗皮膏药一样,关也关不掉,一点就要登录,属实是有点不爽了。 窗口的进程不能杀死,但是窗口我不想要。思路很简单,用 spy 找到要隐藏的窗口的句柄,然后调用 Windows 的 ShowWindo…...

React基础之tsx语法

tsx在jsx的基础上添加了新的类型&#xff0c;除此之外没有任何区别 事件绑定 function App() { const handleClick()>{ console.log(button被点击了); } return( <div className"App"> <button onClick{handleClick}>click me</button> </di…...

一体机:DeepSeek性能的“隐形枷锁”!

一体机是DeepSeek交付的最佳方式吗&#xff1f; 恰恰相反&#xff0c;一体机是阻碍DeepSeek提升推理性能的最大绊脚石。 为啥&#xff1f; 只因DeepSeek这个模型有点特殊&#xff0c;它是个高稀疏度的MoE模型。 MoE这种混合专家模型&#xff0c;设计的初衷是通过“激活一堆专…...

ALBEF的动量蒸馏(Momentum distillation)

简单记录学习~ 一、‌传统 ITC Loss 的局限性‌ ‌One-Hot Label 的缺陷‌ 传统对比学习依赖严格对齐的图文对&#xff0c;通过交叉熵损失&#xff08;如 softmax 归一化的相似度矩阵&#xff09;强制模型将匹配的图文对相似度拉高&#xff0c;非匹配对相似度压低‌11。但 one…...

浏览器WEB播放RTSP

注意&#xff1a;浏览器不能直接播放RTSP&#xff0c;必须转换后都能播放。这一点所有的播放都是如此。 参考 https://github.com/kyriesent/node-rtsp-stream GitHub - phoboslab/jsmpeg: MPEG1 Video Decoder in JavaScript 相关文件方便下载 https://download.csdn.net…...

将PDF转为Word的在线工具

参考视频&#xff1a;外文翻译 文章目录 一、迅捷PDF转换器二、Smallpdf 一、迅捷PDF转换器 二、Smallpdf...

03. 对象的创建,存储和访问原理

文章目录 01. 对象创建1.1 创建过程概览1.2 类加载检查1.3 为对象分配内存1.4 将内存空间初始化为零值1.5 设置对象的必要信息1.6 总结 02. 对象的内存布局2.1 对象头区域2.2 实例数据区域2.3 对齐填充区域2.4 总结 03. 对象的访问定位其他介绍01.关于我的博客 注&#xff1a;读…...

机器学习-GBDT算法

目录 一. GBDT 核心思想 二. GBDT 工作原理 ​**(1) 损失函数优化** ​**(2) 负梯度拟合** ​**(3) 模型更新** 三. GBDT 的关键步骤 四. GBDT 的核心优势 ​**(1) 高精度与鲁棒性** ​**(2) 处理缺失值** ​**(3) 特征重要性分析** ​五. GBDT 的缺点 ​**(1) 训练…...

redis基础结构

title: redis基础结构 date: 2025-03-04 08:39:12 tags: redis categories: redis笔记 Redis入门 &#xff08;NoSQL, Not Only SQL&#xff09; 非关系型数据库 关系型数据库&#xff1a;以 表格 的形式存在&#xff0c;以 行和列 的形式存取数据&#xff0c;一系列的行和列被…...

【keil】一种将STM32的armcc例程转换为armclang的方式

【keil】一种将所有armcc例程转换为armclang的方式 改的原因第一步下载最新arm6第二步编译成功 第三步去除一些warning编译成功 我这边用armclang去编译的话&#xff0c;主要是freertos中的portmacro.h和port.c会报错 改的原因 我真的服了&#xff0c;现在大部分的单片机例程都…...

计算机视觉算法实战——表面缺陷检测(表面缺陷检测)

✨个人主页欢迎您的访问 ✨期待您的三连 ✨ ✨个人主页欢迎您的访问 ✨期待您的三连 ✨ ✨个人主页欢迎您的访问 ✨期待您的三连✨ ​ ​​​ 1. 引言 表面缺陷检测是计算机视觉领域中的一个重要研究方向&#xff0c;旨在通过图像处理和机器学习技术自动检测产品表面的缺陷&…...

window下的docker内使用gpu

Windows 上使用 Docker GPU需要进行一系列的配置和步骤。这是因为 Docker 在 Windows 上的运行环境与 Linux 有所不同,需要借助 WSL 2(Windows Subsystem for Linux 2)和 NVIDIA Container Toolkit 来实现 GPU 的支持。以下是详细的流程: 一、环境准备 1.系统要求 Window…...

Modbus协议(TCP)

从今开始&#xff0c;会详细且陆续整理各类的通信协议&#xff0c;以便在需要且自身忘记的情况下&#xff0c;迅速复习。如有错误之处&#xff0c;还请批评指正。 一、Modbus协议的简述 Modbus协议作为应用层协议&#xff0c;基于主从设备模型&#xff0c;主设备负责请求消息&…...

虚拟系统配置实验报告

一、实验拓扑图 二、实验配置 要求一&#xff1a; 虚拟系统&#xff1a; 设置管理&#xff1a; 进行信息配置 R1配置 虚拟系统配置 a&#xff1a; b&#xff1a; c&#xff1a; 测试 a–>b&#xff1a; 检测...

Agentic系统:负载均衡与Redis缓存优化

摘要 本文在前文Agentic系统的基础上&#xff0c;新增负载均衡&#xff08;动态调整线程数以避免API限流&#xff09;和缓存机制&#xff08;使用Redis存储搜索结果&#xff0c;减少API调用&#xff09;。通过这些优化&#xff0c;系统在高并发场景下更加稳定高效。代码完整可…...

28-文本左右对齐

给定一个单词数组 words 和一个长度 maxWidth &#xff0c;重新排版单词&#xff0c;使其成为每行恰好有 maxWidth 个字符&#xff0c;且左右两端对齐的文本。 你应该使用 “贪心算法” 来放置给定的单词&#xff1b;也就是说&#xff0c;尽可能多地往每行中放置单词。必要时可…...

建筑兔零基础自学python记录39|实战词云可视化项目——章节分布10(上)

这次我们来制作《红楼梦》各章节的分布情况&#xff1a; 源代码&#xff1a; import pandas as pd import numpy as np import matplotlib.pyplot as pltdf_hlm pd.read_csv("hlm.txt", names["hlm_texts"]).dropna()df_hlm df_hlm[~df_hlm.hlm_texts.s…...

Impacket工具中的横向渗透利器及其使用场景对比详解

在渗透测试中&#xff0c;横向移动&#xff08;Lateral Movement&#xff09;是指攻击者在获得一个系统的控制权限后&#xff0c;通过网络进一步渗透到其他系统的过程。Impacket 是一款强大的渗透测试工具集&#xff0c;提供了多种实现横向渗透的脚本&#xff0c;常见的工具包括…...

Java 语言特性(面试系列2)

一、SQL 基础 1. 复杂查询 &#xff08;1&#xff09;连接查询&#xff08;JOIN&#xff09; 内连接&#xff08;INNER JOIN&#xff09;&#xff1a;返回两表匹配的记录。 SELECT e.name, d.dept_name FROM employees e INNER JOIN departments d ON e.dept_id d.dept_id; 左…...

Java 语言特性(面试系列1)

一、面向对象编程 1. 封装&#xff08;Encapsulation&#xff09; 定义&#xff1a;将数据&#xff08;属性&#xff09;和操作数据的方法绑定在一起&#xff0c;通过访问控制符&#xff08;private、protected、public&#xff09;隐藏内部实现细节。示例&#xff1a; public …...

python/java环境配置

环境变量放一起 python&#xff1a; 1.首先下载Python Python下载地址&#xff1a;Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个&#xff0c;然后自定义&#xff0c;全选 可以把前4个选上 3.环境配置 1&#xff09;搜高级系统设置 2…...

解决Ubuntu22.04 VMware失败的问题 ubuntu入门之二十八

现象1 打开VMware失败 Ubuntu升级之后打开VMware上报需要安装vmmon和vmnet&#xff0c;点击确认后如下提示 最终上报fail 解决方法 内核升级导致&#xff0c;需要在新内核下重新下载编译安装 查看版本 $ vmware -v VMware Workstation 17.5.1 build-23298084$ lsb_release…...

系统设计 --- MongoDB亿级数据查询优化策略

系统设计 --- MongoDB亿级数据查询分表策略 背景Solution --- 分表 背景 使用audit log实现Audi Trail功能 Audit Trail范围: 六个月数据量: 每秒5-7条audi log&#xff0c;共计7千万 – 1亿条数据需要实现全文检索按照时间倒序因为license问题&#xff0c;不能使用ELK只能使用…...

HTML 列表、表格、表单

1 列表标签 作用&#xff1a;布局内容排列整齐的区域 列表分类&#xff1a;无序列表、有序列表、定义列表。 例如&#xff1a; 1.1 无序列表 标签&#xff1a;ul 嵌套 li&#xff0c;ul是无序列表&#xff0c;li是列表条目。 注意事项&#xff1a; ul 标签里面只能包裹 li…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院挂号小程序

一、开发准备 ​​环境搭建​​&#xff1a; 安装DevEco Studio 3.0或更高版本配置HarmonyOS SDK申请开发者账号 ​​项目创建​​&#xff1a; File > New > Create Project > Application (选择"Empty Ability") 二、核心功能实现 1. 医院科室展示 /…...

大语言模型如何处理长文本?常用文本分割技术详解

为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...

高等数学(下)题型笔记(八)空间解析几何与向量代数

目录 0 前言 1 向量的点乘 1.1 基本公式 1.2 例题 2 向量的叉乘 2.1 基础知识 2.2 例题 3 空间平面方程 3.1 基础知识 3.2 例题 4 空间直线方程 4.1 基础知识 4.2 例题 5 旋转曲面及其方程 5.1 基础知识 5.2 例题 6 空间曲面的法线与切平面 6.1 基础知识 6.2…...

2023赣州旅游投资集团

单选题 1.“不登高山&#xff0c;不知天之高也&#xff1b;不临深溪&#xff0c;不知地之厚也。”这句话说明_____。 A、人的意识具有创造性 B、人的认识是独立于实践之外的 C、实践在认识过程中具有决定作用 D、人的一切知识都是从直接经验中获得的 参考答案: C 本题解…...