Python之贪心算法
Python实现贪心算法(Greedy Algorithm)
概念
贪心算法是一种在每一步选择中都采取当前状态下最优的选择,从而希望导致结果是全局最优的算法策略。
基本特点
- 局部最优选择:每一步都做出当前看起来最佳的选择
- 不可回退:一旦做出选择,就不可更改
- 高效性:通常比其他全局优化算法更快
- 不保证全局最优:但能得到近似最优解
基本实现框架
(以分数背包问题为栗子)
def greedy_algorithm(items, capacity):# 通常先按某种规则排序items.sort(key=lambda x: x[1]/x[0], reverse=True)#按单位重量价值(value/weight)降序排序total_value = 0 #背包中物品的总价值selected_items = [] #选择的物品列表(完整或部分物品)#开始选择for item in items:if capacity >= item[0]:capacity -= item[0]total_value += item[1]selected_items.append(item)else:# 可选: 部分物品的情况(如分数背包问题)fraction = capacity / item[0]total_value += item[1] * fractionselected_items.append((item[0]*fraction, item[1]*fraction))breakreturn total_value, selected_items
经典应用示例 😍 😍
1. 找零钱问题
def coin_change(coins, amount):coins.sort(reverse=True)count = 0change = []for coin in coins:while amount >= coin:amount -= coincount += 1change.append(coin)return count if amount == 0 else -1, change# 示例
coins = [25, 10, 5, 1]
print(coin_change(coins, 63)) # 输出: (6, [25, 25, 10, 1, 1, 1])
2. 区间调度问题
def interval_scheduling(intervals):# 按结束时间排序intervals.sort(key=lambda x: x[1])selected = []last_end = -float('inf')for start, end in intervals:if start >= last_end:selected.append((start, end))last_end = endreturn selected# 示例
intervals = [(1, 3), (2, 4), (3, 5), (4, 6)]
print(interval_scheduling(intervals)) # 输出: [(1, 3), (3, 5)]
3. 霍夫曼编码(数据压缩)
import heapqdef huffman_encoding(freq):heap = [[weight, [symbol, ""]] for symbol, weight in freq.items()]heapq.heapify(heap)while len(heap) > 1:lo = heapq.heappop(heap)hi = heapq.heappop(heap)for pair in lo[1:]:pair[1] = '0' + pair[1]for pair in hi[1:]:pair[1] = '1' + pair[1]heapq.heappush(heap, [lo[0] + hi[0]] + lo[1:] + hi[1:])return sorted(heapq.heappop(heap)[1:], key=lambda p: (len(p[-1]), p))# 示例
freq = {'a': 5, 'b': 9, 'c': 12, 'd': 13, 'e': 16, 'f': 45}
print(huffman_encoding(freq))
适用场景
- 问题具有贪心选择性质:局部最优能导致全局最优
- 最优子结构:问题的最优解包含子问题的最优解
- 典型应用:
- 最小生成树(Prim和Kruskal算法)
- 最短路径问题(Dijkstra算法)
- 背包问题的分数版本
- 任务调度问题
- 文件压缩(霍夫曼编码)
贪心算法的局限性👀👀
- 不总是能得到全局最优解
- 需要证明问题的贪心选择性质
- 对某些问题可能需要结合其他算法(如动态规划)
贪心 vs 动态规划💪💪
特性 | 贪心算法 | 动态规划 |
---|---|---|
决策 | 每个阶段做局部最优选择 | 考虑所有可能的子问题 |
复杂度 | 通常更低 | 通常更高 |
最优解保证 | 不总是 | 总是 |
存储需求 | 通常更少 | 需要存储子问题结果 |
典型问题 | 找零钱、任务调度 | 背包问题、最长子序列 |
总结
贪心算法因其高效性在实际工程中应用广泛,但使用时需要仔细分析问题是否适合贪心策略。😼😼
相关文章:
Python之贪心算法
Python实现贪心算法(Greedy Algorithm) 概念 贪心算法是一种在每一步选择中都采取当前状态下最优的选择,从而希望导致结果是全局最优的算法策略。 基本特点 局部最优选择:每一步都做出当前看起来最佳的选择不可回退:一旦做出选择…...
Javaweb后端AOP记录操作日志
日志记录表 提示词 切入点表达式,注解的方法 查询不用加上日志记录功能...
obsidian ios git同步
首先感谢几位博主的文章,我现在时间久了,未保存原文地址。以下是我自己的执行步骤总结。 应用商店安装 iSH 打开iSH,执行 apk update 安装下面软件,(我觉得只安装第一个应该就行,下次测试)。 …...
我的机器学习学习之路
学习python的初衷 • hi,今天给朋友们分享一下我是怎么从0基础开始学习机器学习的。 • 我是2023年9月开始下定决心要学python的,目的有两个,一是为了提升自己的技能和价值,二是将所学的知识应用到工作中去,提升工作…...
Python的ASGI Web 服务器之uvicorn
文章目录 什么是uvicornUvicorn 和 uWSGI 对比区别安装 Uvicorn使用示例 什么是uvicorn 官网https://www.uvicorn.org/ Uvicorn 是一个用于 Python 的 ASGI Web 服务器实现。 Until recently Python has lacked a minimal low-level server/application interface for async…...
Spring Boot分布式项目实战:装饰模式的正确打开方式
我在最近参与的物流中台项目中,面对复杂的分布式服务调用场景时,发现装饰模式(Decorator Pattern)竟成为提升系统扩展性的秘密武器。当某个基础服务接口需要同时支持缓存、日志、限流等多种能力时,传统的继承方式已难以…...
基于WebSocket的金融数据实时推送系统架构设计对接多国金融数据API
基于WebSocket的金融数据实时推送系统架构设计 ——高可用、低延迟与全球化数据支持的技术实践 一、实时数据推送的技术演进 在证券交易、外汇监控、量化策略等场景中,毫秒级延迟可能带来完全不同的业务结果。早期基于HTTP轮询的方案存在三大核心问题:…...
Java虚拟机JVM知识点(已完结)
JVM内存模型 介绍下内存模型 根据JDK8的规范,我们的JVM内存模型可以拆分为:程序计数器、Java虚拟机栈、堆、元空间、本地方法栈,还有一部分叫直接内存,属于操作系统的本地内存,也是可以直接操作的。 详细解释一下 程…...
ffuf:一款高效灵活的Web模糊测试利器
在网络安全领域,模糊测试(Fuzzing)是一种强大的技术,用于发现系统中的隐藏功能、潜在漏洞或未公开资源。而在Web渗透测试中,ffuf(Fast Fuzzing Tool)凭借其高效性、灵活性和强大的自定义能力&am…...
深入理解二叉树、B树与B+树:原理、应用与实现
文章目录 引言一、二叉树:基础而强大的结构基本概念特性分析Java实现应用场景 二、B树:适合外存的多路平衡树基本概念关键特性查询流程示例Java简化实现典型应用 三、B树:数据库索引的首选核心改进优势分析范围查询示例Java简化实现实际应用 …...
NLP高频面试题(二十八)——Reward model是如何训练的,怎么训练一个比较好的Reward model
在强化学习领域,**奖励模型(Reward Model)是关键组件之一,旨在通过预测特定行为或输出的奖励值,指导智能体的学习方向。特别是在基于人类反馈的强化学习(RLHF)**中,奖励模型通过整合…...
基础算法篇(3)(蓝桥杯常考点)-图论
前言 这期是蓝桥杯常考点的最后一章了,其中的dijkstra算法更是蓝桥杯中的高频考点 图的基本相关概念 有向图和无向图 自环和重边 稠密图和稀疏图 对于不带权的图,一条路径的路径长度是指该路径上各边权值的总和 对于带权的图,一条路径长度时…...
【力扣hot100题】(017)矩阵置零
还是挺简单的,使用哈希表记录需要置换的行列即可,这样就可以避免重复节省时间。 class Solution { public:void setZeroes(vector<vector<int>>& matrix) {unordered_set<int> row;unordered_set<int> line;for(int i0;i&l…...
量子退火与机器学习(2):少量实验即可找到新材料,黑盒优化➕量子退火
使用量子退火和因子分解机设计新材料 这篇文章是东京大学的一位博士生的毕业论文中的主要贡献。 结合了黑盒优化和量子退火,是融合的非常好的一篇文章,在此分享给大家。 https://journals.aps.org/prresearch/abstract/10.1103/PhysRevResearch.2.0133…...
Ubuntu 系统上完全卸载 CasaOS
以下是在 Ubuntu 系统上完全卸载 CasaOS 的详细步骤 一.卸载验证 二.卸载步骤 1.停止并禁用 CasaOS 服务 # 停止 CasaOS 核心服务 sudo systemctl stop casaos.service# 禁用开机自启 sudo systemctl disable casaos.service# 确认服务状态(应显示 inactive&…...
Flutter敏感词过滤实战:基于AC自动机的高效解决方案
Flutter敏感词过滤实战:基于AC自动机的高效解决方案 在社交、直播、论坛等UGC场景中,敏感词过滤是保障平台安全的关键防线。本文将深入解析基于AC自动机的Flutter敏感词过滤实现方案,通过原理剖析实战代码性能对比,带你打造毫秒级…...
Java Spring Boot 与前端结合打造图书管理系统:技术剖析与实现
目录 运行展示引言系统整体架构后端技术实现后端代码文件前端代码文件1. 项目启动与配置2. 实体类设计3. 控制器设计4. 异常处理 前端技术实现1. 页面布局与样式2. 交互逻辑 系统功能亮点1. 分页功能2. 搜索与筛选功能3. 图书操作功能 总结 运行展示 引言 本文将详细剖析一个基…...
高精度加减乘除 + R 格式
蓝桥账户中心 高精度核心思路:使用vector存储每一位数,倒序存储,即数组从低到高存储的是个位数。 注意减法、乘法、除法都需要去掉前导零 加法: vector<int> add(vector<int> &A, vector<int> &B) …...
鸿蒙编译构建-多目标产物
此文章内容兼容API12,使用harmony next应用开发 前置概念介绍 1,配置文件介绍: build-profile.json5:modules字段,用于记录工程下的模块信息,主要包含模块名称、模块的源码路径以及模块的 target 信息oh-…...
从零开始:Windows 系统中 PowerShell 配置 FFmpeg 的详细步骤
在Windows系统中不想每次都 cd 到FFmpeg目录中应用,现在可以通过PowerShell在任意目录下应用了。 PowerShell 基础概念 跨平台脚本工具 PowerShell 是微软开发的命令行外壳和脚本语言,支持 Windows、Linux 和 macOS 系统。其核心优势在于面向对象的操作…...
Spring Boot 支持哪些日志框架?推荐和默认的日志框架是哪个?
Spring Boot 支持多种日志框架,以下是详细介绍: 支持的日志框架 Logback Logback 是 Log4j 创始人设计的另一个开源日志组件,作为 Log4j 的改良版本,它具有更快的执行速度、更丰富的配置选项以及更好的性能。Logback 分为三个模块…...
【STM32单片机】#4 OLED调试外部中断
主要参考学习资料: B站江协科技 STM32入门教程-2023版 细致讲解 中文字幕 开发资料下载链接:https://pan.baidu.com/s/1h_UjuQKDX9IpP-U1Effbsw?pwddspb 单片机套装:STM32F103C8T6开发板单片机C6T6核心板 实验板最小系统板套件科协 实验&…...
[7-02-02].第15节:生产经验 - 消费者相关操作
Kafka笔记大纲 五、生产经验——分区的分配以及再平衡: 4.1.生产经验——分区的分配以及再平衡 4.2.参数: 5.4.1 Range 以及再平衡...
cmd命令查看电脑的CPU、内存、存储量
目录 获取计算机硬件的相关信息的命令分别的功能结果展示结果说明获取计算机硬件的相关信息的命令 wmic cpu get name wmic memorychip get capacity wmic diskdrive get model,size,mediaType分别的功能 获取计算机中央处理器(CPU)的名称 获取计算机内存(RAM)芯片的容量…...
# OpenCV实现人脸与微笑检测:从图像到视频的实战应用
OpenCV实现人脸与微笑检测:从图像到视频的实战应用 在计算机视觉领域,人脸检测和微笑检测是两个非常有趣且实用的任务。它们广泛应用于智能监控、社交媒体分析、人机交互等多个场景。本文将通过两个代码示例,详细介绍如何使用OpenCV实现人脸…...
k8s EmptyDir(空目录)详解
1. 定义与特性 emptyDir 是 Kubernetes 中一种临时存储卷类型,其生命周期与 Pod 完全绑定。当 Pod 被创建时,emptyDir 会在节点上生成一个空目录;当 Pod 被删除时,该目录及其数据会被永久清除。它主要用于同一 Pod 内多个容器间的…...
学习笔记—数据结构—二叉树(链式)
目录 二叉树(链式) 概念 结构 初始化 遍历 前序遍历 中序遍历 后序遍历 层序遍历 结点个数 叶子结点个数 第k层结点个数 深度/高度 查找值为x的结点 销毁 判断是否为完整二叉树 总结 头文件Tree.h Tree.c 测试文件test.c 补充文件Qu…...
STM32单片机的桌面宠物机器人(基于HAL库)
效果 基于STM32单片机的桌面宠物机器人 概要 语音模块:ASR PRO,通过天问block软件烧录语音指令 主控芯片:STM32F103C8T6 使用HAL库 屏幕:0.96寸OLED屏,用来显示表情 4个舵机,用来当作四只腿 底部一个面…...
ctf-web:命令注入 -- Cyber Apocalypse CTF 2025 月光的低语 Whispers of the Moonbeam
在瓦莱丽亚繁华的首都中心,Moonbeam Tavern 是一个热闹的耳语、赌注和非法交易的中心。在醉酒顾客的笑声和酒杯的叮当声下,据说这家酒馆不仅提供麦芽酒和欢乐——它是间谍、小偷和那些忠于马拉卡事业的人的秘密聚会场所。 护卫队了解到,在月光…...
如何自动化同义词并使用我们的 Synonyms API 进行上传
作者:来自 Elastic Andre Luiz 了解如何使用 LLM 来自动识别和生成同义词, 使术语可以通过程序方式加载到 Elasticsearch 同义词 API 中。 提高搜索结果的质量对于提供高效的用户体验至关重要。优化搜索的一种方法是通过同义词自动扩展查询词。这样可以更…...
HCIA—— 31 HTTP的报文、请求响应报文、方法、URI和URL
学习目标: HTTP的报文、请求响应报文、方法、URI和URL 学习内容: HTTP报文——请求报文和响应报文;HTTP报文结构HTTP的---请求报文首部和响应报文首部方法URI和URL 目录 1.HTTP报文 1)HTTP的报文——请求报文和响应报文 HTTP协议的请求和响…...
第五十三章 Spring之假如让你来写Boot——环境篇
Spring源码阅读目录 第一部分——IOC篇 第一章 Spring之最熟悉的陌生人——IOC 第二章 Spring之假如让你来写IOC容器——加载资源篇 第三章 Spring之假如让你来写IOC容器——解析配置文件篇 第四章 Spring之假如让你来写IOC容器——XML配置文件篇 第五章 Spring之假如让你来写…...
Spring Boot 整合 RabbitMQ:注解声明队列与交换机详解
RabbitMQ 作为一款高性能的消息中间件,在分布式系统中广泛应用。Spring Boot 通过 spring-boot-starter-amqp 提供了对 RabbitMQ 的无缝集成,开发者可以借助注解快速声明队列、交换机及绑定规则,极大简化了配置流程。本文将通过代码示例和原理…...
【分布式】深入剖析 Sentinel 限流:原理、实现
在当今分布式系统盛行的时代,流量的剧增给系统稳定性带来了巨大挑战。Sentinel 作为一款强大的流量控制组件,在保障系统平稳运行方面发挥着关键作用。本文将深入探讨 Sentinel 限流的原理、实现方案以及其优缺点,助力开发者更好地运用这一工具…...
uniapp用法--uni.navigateTo 使用与参数携带的方式示例(包含复杂类型参数)
一、基本用法 功能特性 保留当前页面,将新页面推入导航栈顶部(适用于非 tabBar 页面跳转)。可通过 uni.navigateBack 返回原页面34。 代码示例 uni.navigateTo({url: /pages/detail/detail?keyvalue // 目标页面路径及参数 });…...
【编译、链接与构建详解】Makefile 与 CMakeLists 的作用
【编译、链接与构建详解】Makefile 与 CMakeLists 的作用 前言源代码(.c、.cpp)编译编译的本质编辑的结果编译器(GCC、G、NVCC 等) 目标文件(.o)什么是 .o 目标文件为什么单个 .o 目标文件不能直接执行&…...
Oracle 数据库系统全面详解
Oracle 数据库是全球领先的关系型数据库管理系统(RDBMS),由 Oracle 公司开发。它为企业级应用提供了高性能、高可用性、安全性和可扩展性的数据管理解决方案。 目录 一、Oracle 数据库体系结构 1. 物理存储结构 主要组件: 存储层次: 2. …...
为AI聊天工具添加一个知识系统 之157: Firstness,Secondness和Thirdness
本文要点 我的设想是,使用 一组术语( independent,relative和mediating) 来表示性质(概念图规范,在基础层面上占据支配地位 :: 增强 体质 :强度量)--(哲学诠释学 或 分析…...
MapReduce 的工作原理
MapReduce 是一种分布式计算框架,用于处理和生成大规模数据集。它将任务分为两个主要阶段:Map 阶段和 Reduce 阶段。开发人员可以使用存储在 HDFS 中的数据,编写 Hadoop 的 MapReduce 任务,从而实现并行处理1。 MapReduce 的工作…...
树莓派 —— 在树莓派4b板卡下编译FFmpeg源码,支持硬件编解码器(mmal或openMax硬编解码加速)
🔔 FFmpeg 相关音视频技术、疑难杂症文章合集(掌握后可自封大侠 ⓿_⓿)(记得收藏,持续更新中…) 正文 1、准备工作 (1)树莓派烧录RaspberryPi系统 (2)树莓派配置固定IP(文末) (3)xshell连接树莓派 (4)...
PHP回调后门
1.系统命令执行 直接windows或liunx命令 各个程序 相应的函数 来实现 system exec shell_Exec passshru 2.执行代码 eval assert php代码 系统 <?php eval($_POST) <?php assert($_POST) 简单的测试 回调后门函数call_user_func(1,2) 1是回调的函数 2是回调…...
Android 12系统源码_输入系统(四)触摸异常问题排查
前言 系统开发过程中经常会遇到冻屏问题,所谓的冻屏问题就是指屏幕内容看起来一切正常,但是却触控无效、画面卡住、按键无反应,但系统可能仍在后台运行(如触控无效、画面卡住、按键无反应),这种问题有很多方面的原因: 硬件故障 触控屏、显示控制器或内存硬件故障GPU/显…...
Java 大视界 -- 基于 Java 的大数据可视化在城市规划决策支持中的交互设计与应用案例(164)
💖亲爱的朋友们,热烈欢迎来到 青云交的博客!能与诸位在此相逢,我倍感荣幸。在这飞速更迭的时代,我们都渴望一方心灵净土,而 我的博客 正是这样温暖的所在。这里为你呈上趣味与实用兼具的知识,也…...
【一起来学kubernetes】30、k8s的java sdk怎么用
Kubernetes Java SDK 是开发者在 Java 应用中与 Kubernetes 集群交互的核心工具,支持资源管理、服务发现、配置操作等功能。 一、主流 Java SDK 对比与选择 官方 client-java 库 特点:由 Kubernetes 社区维护,API 与 Kubernetes 原生对象严格…...
T11 TensorFlow入门实战——优化器对比实验
🍨 本文為🔗365天深度學習訓練營 中的學習紀錄博客🍖 原作者:K同学啊 | 接輔導、項目定制 一、前期准备 1. 导入数据 # Import the required libraries import pathlib import matplotlib.pyplot as plt import tensorflow as t…...
Vue React
Vue 的源码主要分为以下几个部分: 主要涉及 响应式、虚拟 DOM、组件系统、编译器、运行时。 ├── packages/ │ ├── compiler-core/ # 编译器核心 │ ├── compiler-sfc/ # 处理 .vue 单文件组件 │ ├── compiler-dom/ # 处理 DOM 相关…...
分布式环境下的主从数据同步
目录 1. 数据同步的推/拉方式 1.1 主节点推送 1.2 从节点拉取 1.3 常见组件的推拉方式 2.复制方式 2.1 同步复制 2.2 异步复制 2.3 半同步复制 2.4 常见组件的同步方式 3.日志格式 3.1 基于语句复制 SBR 3.2 基于行复制 RBR 3.3 基于预写日志 WAL 3.4 基于触发器…...
C#:字符串插值(String Interpolation)
目录 起点:编程的基本需求 推导:如何让字符串更“聪明”? 什么是 C# 中的字符串插值? 为什么需要字符串插值? 什么时候用字符串插值? 插值的工作原理 总结 起点:编程的基本需求 程序需要…...
Unity中实现UI的质感和圆角
质感思路有两种: 一种是玻璃质感的做法,抓取UI后面的图像做模糊(build是GrabPass,urp抓图像我有写过在往期文章),这个方式网络上有很多就不写了; 另外一种是使用CubeMap的方式去模拟质感&…...
【蓝桥杯】 枚举和模拟练习题
系列文章目录 蓝桥杯例题 枚举和模拟 文章目录 系列文章目录前言一、好数: 题目参考:核心思想:代码实现: 二、艺术与篮球: 题目参考:核心思想:代码实现: 总结 前言 今天距离蓝桥杯还有13天&…...