贪心算法解题框架+经典反例分析,效率提升300%
贪心算法是一种在每一步选择中都采取当前状态下的最优决策,从而希望最终达到全局最优解的算法策略。以下从其定义、特点、一般步骤、应用场景及实例等方面进行讲解:
定义与基本思想
• 贪心算法在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,它所做出的仅仅是在某种意义上的局部最优解。它通常以自顶向下的方式进行,每一步都选择当前的最优解,而不考虑之前或之后的步骤。
特点
• 无后效性:即某个状态以前的过程不会影响以后的状态,只与当前状态有关。这使得贪心算法在每一步决策时,只需要考虑当前的状态信息,而不必考虑整个问题的历史信息。
• 局部最优选择:贪心算法在每一步都选择当前看起来最优的决策,而不考虑整体的最优解。这种局部最优选择策略是贪心算法的核心特点,也是其与动态规划等其他算法的主要区别之一。
一般解题步骤
- 问题分析:明确问题的目标和约束条件,确定问题是否适合用贪心算法求解。一般来说,如果问题具有最优子结构性质和贪心选择性质,就可以考虑使用贪心算法。
- 贪心策略设计:根据问题的特点,设计一个贪心策略。贪心策略的好坏直接影响算法的正确性和效率。例如,在活动安排问题中,贪心策略可以是按照活动结束时间的先后顺序来选择活动。
- 算法实现:根据贪心策略,实现具体的算法。在实现过程中,需要注意数据结构的选择和操作,以提高算法的效率。
- 正确性证明:虽然贪心算法通常比较直观,但为了确保算法的正确性,需要对贪心策略进行证明。证明方法通常有归纳法、反证法等。
应用场景
一、区间调度问题
【核心思路】:通过排序区间端点,选择不重叠区间的最大数量或最优安排方式。
【解决思路】:
- 排序策略:按区间右端点从小到大排序。
- 贪心选择:依次选择最早结束且不与已选区间重叠的区间。
- 优化目标:最大化不重叠区间数量。
【经典题型】:
线段覆盖:选择最多不重叠线段,按右端点排序后贪心选择。
纪念品分组:将物品按价格排序后,双指针组合最大可能的配对,使组数最少。
智力大冲浪:按扣款数从大到小排序,尽量在截止时间前完成任务以减少罚款5。
种树问题:按区间右端点排序,从后向前填充以满足多个区间需求。
洛谷例题:P1803(线段覆盖)、P1094(纪念品分组)、P1230(智力大冲浪)、P1250(种树)。
参考P1094纪念品分组
二、排序选择问题
【核心思路】:通过排序后选择局部最优解,通常与性价比、时间顺序相关。
【解决思路】:
- 部分背包:按单位价值(价值/重量)降序排序,优先拿取高性价比物品。
- 排队接水:按接水时间升序排序,最小化总等待时间。
【 典型场景】:
◦ 部分背包问题:按单位价值排序,优先拿取性价比高的物品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的基础上添加了新的类型,除此之外没有任何区别 事件绑定 function App() { const handleClick()>{ console.log(button被点击了); } return( <div className"App"> <button onClick{handleClick}>click me</button> </di…...
一体机:DeepSeek性能的“隐形枷锁”!
一体机是DeepSeek交付的最佳方式吗? 恰恰相反,一体机是阻碍DeepSeek提升推理性能的最大绊脚石。 为啥? 只因DeepSeek这个模型有点特殊,它是个高稀疏度的MoE模型。 MoE这种混合专家模型,设计的初衷是通过“激活一堆专…...
ALBEF的动量蒸馏(Momentum distillation)
简单记录学习~ 一、传统 ITC Loss 的局限性 One-Hot Label 的缺陷 传统对比学习依赖严格对齐的图文对,通过交叉熵损失(如 softmax 归一化的相似度矩阵)强制模型将匹配的图文对相似度拉高,非匹配对相似度压低11。但 one…...
浏览器WEB播放RTSP
注意:浏览器不能直接播放RTSP,必须转换后都能播放。这一点所有的播放都是如此。 参考 https://github.com/kyriesent/node-rtsp-stream GitHub - phoboslab/jsmpeg: MPEG1 Video Decoder in JavaScript 相关文件方便下载 https://download.csdn.net…...
将PDF转为Word的在线工具
参考视频:外文翻译 文章目录 一、迅捷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.关于我的博客 注:读…...
机器学习-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入门 (NoSQL, Not Only SQL) 非关系型数据库 关系型数据库:以 表格 的形式存在,以 行和列 的形式存取数据,一系列的行和列被…...
【keil】一种将STM32的armcc例程转换为armclang的方式
【keil】一种将所有armcc例程转换为armclang的方式 改的原因第一步下载最新arm6第二步编译成功 第三步去除一些warning编译成功 我这边用armclang去编译的话,主要是freertos中的portmacro.h和port.c会报错 改的原因 我真的服了,现在大部分的单片机例程都…...
计算机视觉算法实战——表面缺陷检测(表面缺陷检测)
✨个人主页欢迎您的访问 ✨期待您的三连 ✨ ✨个人主页欢迎您的访问 ✨期待您的三连 ✨ ✨个人主页欢迎您的访问 ✨期待您的三连✨ 1. 引言 表面缺陷检测是计算机视觉领域中的一个重要研究方向,旨在通过图像处理和机器学习技术自动检测产品表面的缺陷&…...
window下的docker内使用gpu
Windows 上使用 Docker GPU需要进行一系列的配置和步骤。这是因为 Docker 在 Windows 上的运行环境与 Linux 有所不同,需要借助 WSL 2(Windows Subsystem for Linux 2)和 NVIDIA Container Toolkit 来实现 GPU 的支持。以下是详细的流程: 一、环境准备 1.系统要求 Window…...
Modbus协议(TCP)
从今开始,会详细且陆续整理各类的通信协议,以便在需要且自身忘记的情况下,迅速复习。如有错误之处,还请批评指正。 一、Modbus协议的简述 Modbus协议作为应用层协议,基于主从设备模型,主设备负责请求消息&…...
虚拟系统配置实验报告
一、实验拓扑图 二、实验配置 要求一: 虚拟系统: 设置管理: 进行信息配置 R1配置 虚拟系统配置 a: b: c: 测试 a–>b: 检测...
Agentic系统:负载均衡与Redis缓存优化
摘要 本文在前文Agentic系统的基础上,新增负载均衡(动态调整线程数以避免API限流)和缓存机制(使用Redis存储搜索结果,减少API调用)。通过这些优化,系统在高并发场景下更加稳定高效。代码完整可…...
28-文本左右对齐
给定一个单词数组 words 和一个长度 maxWidth ,重新排版单词,使其成为每行恰好有 maxWidth 个字符,且左右两端对齐的文本。 你应该使用 “贪心算法” 来放置给定的单词;也就是说,尽可能多地往每行中放置单词。必要时可…...
建筑兔零基础自学python记录39|实战词云可视化项目——章节分布10(上)
这次我们来制作《红楼梦》各章节的分布情况: 源代码: 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工具中的横向渗透利器及其使用场景对比详解
在渗透测试中,横向移动(Lateral Movement)是指攻击者在获得一个系统的控制权限后,通过网络进一步渗透到其他系统的过程。Impacket 是一款强大的渗透测试工具集,提供了多种实现横向渗透的脚本,常见的工具包括…...
Admin.Net中的消息通信SignalR解释
定义集线器接口 IOnlineUserHub public interface IOnlineUserHub {/// 在线用户列表Task OnlineUserList(OnlineUserList context);/// 强制下线Task ForceOffline(object context);/// 发布站内消息Task PublicNotice(SysNotice context);/// 接收消息Task ReceiveMessage(…...
AtCoder 第409场初级竞赛 A~E题解
A Conflict 【题目链接】 原题链接:A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串,只有在同时为 o 时输出 Yes 并结束程序,否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...
解锁数据库简洁之道:FastAPI与SQLModel实战指南
在构建现代Web应用程序时,与数据库的交互无疑是核心环节。虽然传统的数据库操作方式(如直接编写SQL语句与psycopg2交互)赋予了我们精细的控制权,但在面对日益复杂的业务逻辑和快速迭代的需求时,这种方式的开发效率和可…...
【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)
服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...
基于Uniapp开发HarmonyOS 5.0旅游应用技术实践
一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架,支持"一次开发,多端部署",可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务,为旅游应用带来…...
定时器任务——若依源码分析
分析util包下面的工具类schedule utils: ScheduleUtils 是若依中用于与 Quartz 框架交互的工具类,封装了定时任务的 创建、更新、暂停、删除等核心逻辑。 createScheduleJob createScheduleJob 用于将任务注册到 Quartz,先构建任务的 JobD…...
1.3 VSCode安装与环境配置
进入网址Visual Studio Code - Code Editing. Redefined下载.deb文件,然后打开终端,进入下载文件夹,键入命令 sudo dpkg -i code_1.100.3-1748872405_amd64.deb 在终端键入命令code即启动vscode 需要安装插件列表 1.Chinese简化 2.ros …...
sqlserver 根据指定字符 解析拼接字符串
DECLARE LotNo NVARCHAR(50)A,B,C DECLARE xml XML ( SELECT <x> REPLACE(LotNo, ,, </x><x>) </x> ) DECLARE ErrorCode NVARCHAR(50) -- 提取 XML 中的值 SELECT value x.value(., VARCHAR(MAX))…...
leetcodeSQL解题:3564. 季节性销售分析
leetcodeSQL解题:3564. 季节性销售分析 题目: 表:sales ---------------------- | Column Name | Type | ---------------------- | sale_id | int | | product_id | int | | sale_date | date | | quantity | int | | price | decimal | -…...
前端开发面试题总结-JavaScript篇(一)
文章目录 JavaScript高频问答一、作用域与闭包1.什么是闭包(Closure)?闭包有什么应用场景和潜在问题?2.解释 JavaScript 的作用域链(Scope Chain) 二、原型与继承3.原型链是什么?如何实现继承&a…...
