算法进阶:贪心算法
贪心算法是一种简单而直观的算法思想,它在每一步选择中都采取在当前状态下最优的选择,以期望最终得到全局最优解。贪心算法通常适用于一些具有最优子结构的问题,即问题的最优解可以通过一系列局部最优解的选择得到。
贪心算法的基本思路是,每一步都选择当前状态下的局部最优解,并把它添加到当前解中。然后,根据已经做出的选择,对剩下的子问题进行求解。这个过程持续进行,直到得到全局最优解。
然而,贪心算法并不是适用于所有问题的。在一些情况下,贪心算法可能会得到次优解或者不正确的解。这是因为贪心算法在每一步都做出局部最优选择,并没有考虑到该选择对之后步骤的影响。
综上所述,贪心算法是一种简单而直观的算法思想,可以用来解决一些具有最优子结构的问题。
目录
贪心算法(找零问题)
背包问题
分数背包
数字拼接问题
常识:时间戳
活动选择问题
贪心算法(找零问题)


# 贪心算法
t = [100, 50, 20, 5, 1]
# 找零
def chang_money(n):m = [[0] for _ in range(len(t))]for i,money in enumerate(t):m[i] = n // moneyn = n % moneyreturn m,n
print(chang_money(376))
([3, 1, 1, 1, 1], 0)
背包问题


答:0-1背包问题不能使用贪心算法解决,
分数背包问题可以。
分数背包
先拿单位重量最值钱的物品(算法思想)
# 分数背包
# 贪心算法思想
goods = [(60,10),(100,20),(120,30)] #(价值,重量)
def fenshu_bag(goods,w):goods.sort(key=lambda x:x[0]//x[1],reverse=True) # 按照贪心算法进行拿取print(goods)m = [0 for _ in range(len(goods))] # 记录排好价值的物品拿多少total_val = 0 # 记录最终总价值for i,(prize,weight) in enumerate(goods): if weight <= w: # 如果背包能放得下m[i] = 1total_val += prizew -= weightelse: # 背包放不下m[i] = w / weighttotal_val += m[i] * prizew = 0breakreturn total_val,m
print(fenshu_bag(goods,50))
[(60, 10), (100, 20), (120, 30)] (240.0, [1, 1, 0.6666666666666666])
数字拼接问题

# 数字拼接问题
from functools import cmp_to_key
li = [32, 94, 128, 1286, 6, 71]
def xy_cmp(x,y):if x+y < y+x: # 说明y应该排在x的前面return 1elif x+y > y+x:return -1else:return 0
def number_join(li):li = list(map(str,li))li.sort(key=cmp_to_key(xy_cmp)) # 类似于冒泡 比较的是unicode编码return "".join(li)
print(number_join(li))
94716321286128
常识:时间戳
时间戳(Timestamp)是一种表示某个特定时刻的数字标识,它记录了从一个特定起始时间点到指定时刻所经过的秒数(或者毫秒数、微秒数 ,具体精度因系统和应用而异)。常见的时间戳有以下两种类型:
Unix 时间戳:Unix 系统广泛使用的时间表示方法,它以 1970 年 1 月 1 日 00:00:00 UTC(协调世界时)作为起始时间点,记录到指定时刻历经的秒数 。例如,Unix 时间戳为
1690579200对应的北京时间是 2023 年 7 月 29 日 00:00:00,因为从 1970 年 1 月 1 日 00:00:00 UTC 到这个时刻,恰好经过了 1690579200 秒。在 Python 中,可以使用time模块来获取和处理 Unix 时间戳:
import time
# 获取当前Unix时间戳
current_timestamp = time.time()
print(current_timestamp)
活动选择问题

# 活动选择问题
activities = [(1,4),(3,5),(0,6),(5,7),(3,9),(6,10),(8,11),(8,12),(2,14),(12,16)]
activities.sort(key=lambda x:x[1]) # 按照结束时间升序排列
def activities_selection(a):res = [a[0]]for i in range(1, len(a)):if a[i][0] >= res[-1][1]: # 活动的开始时间大于等于前一个活动的结束时间可以进行res.append(a[i])return res
print(activities_selection(activities))
[(1, 4), (5, 7), (8, 11), (12, 16)]
相关文章:
算法进阶:贪心算法
贪心算法是一种简单而直观的算法思想,它在每一步选择中都采取在当前状态下最优的选择,以期望最终得到全局最优解。贪心算法通常适用于一些具有最优子结构的问题,即问题的最优解可以通过一系列局部最优解的选择得到。 贪心算法的基本思路是&a…...
C++ 设计模式:工厂方法(Factory Method)
链接:C 设计模式 链接:C 设计模式 - 抽象工厂 链接:C 设计模式 - 原型模式 链接:C 设计模式 - 建造者模式 工厂方法(Factory Method)是创建型设计模式之一,它提供了一种创建对象的接口…...
手机联系人 查询 添加操作
Android——添加联系人_android 添加联系人-CSDN博客 上面连接添加联系人已测试 是可以 Android : 获取、添加、手机联系人-ContentResolver简单应用_contentresolver 添加联系人-CSDN博客...
【LeetCode】2506、统计相似字符串对的数目
【LeetCode】2506、统计相似字符串对的数目 文章目录 一、哈希表位运算1.1 哈希表位运算 二、多语言解法 一、哈希表位运算 1.1 哈希表位运算 每个字符串, 可用一个 int 表示. (每个字符 是 int 的一个位) 哈希表记录各 字符组合 出现的次数 步骤: 遇到一个字符串, 得到 ma…...
金仓数据库对象访问权限的管理
基础知识 对象的分类 数据库的表、索引、视图、缺省值、规则、触发器等等,都称为数据库对象,对象分为如下两类: 模式(SCHEMA)对象:可以理解为一个存储目录,包含视图、索引、数据类型、函数和操作符等。非模式对象:其他的数据库对象&#x…...
Qt 中实现系统主题感知
【写在前面】 在现代桌面应用程序开发中,系统主题感知是一项重要的功能,它使得应用程序能够根据用户的系统主题设置(如深色模式或浅色模式)自动调整其外观。 Qt 作为一个跨平台的C图形用户界面应用程序开发框架,提供…...
Modbus TCP 报文说明
Modbus TCP 报文说明 Modbus TCP 报文结构报文解析功能码说明Modbus 功能码与 PLC 地址的对应关系 Modbus TCP 报文结构 事务标识符(Transaction Identifier,2 字节): 用于匹配请求和响应,通常由客户端生成࿰…...
音视频入门基础:MPEG2-TS专题(24)——FFmpeg源码中,显示TS流每个packet的pts、dts的实现
音视频入门基础:MPEG2-TS专题系列文章: 音视频入门基础:MPEG2-TS专题(1)——MPEG2-TS官方文档下载 音视频入门基础:MPEG2-TS专题(2)——使用FFmpeg命令生成ts文件 音视频入门基础…...
大模型:OneFitsAll、Time - LLM、LLaTA
LLM数据集:ETT、Illness、Weather ETT、Illness、Weather在上述提到的论文中都是用于时间序列预测研究的真实世界数据集,以下是对它们的具体介绍: ETT数据集 内容:ETT是电力变压器温度(Electric Transformer Temperature)数据集,通常包含电力变压器在不同时间点的温度…...
连锁餐饮行业数据可视化分析方案
引言 随着连锁餐饮行业的迅速发展,市场竞争日益激烈。企业需要更加精准地把握运营状况、消费者需求和市场趋势,以制定科学合理的决策,提升竞争力和盈利能力。可视化数据分析可以帮助连锁餐饮企业整合多源数据,通过直观、动态的可…...
Ubuntu 下使用命令行将 U 盘格式化为 ext4、FAT32 和 exFAT 的详细教程
Ubuntu 下使用命令行将 U 盘格式化为 ext4、FAT32 和 exFAT 的详细教程 作者:Witheart更新时间:20241228 本教程将详细介绍如何将 U 盘格式化为 ext4、FAT32 和 exFAT 文件系统,同时包括如何安装必要工具(如 exfat-utils&#x…...
多说话人ASR的衡量指标和有效计算工具包
WER (Word Error Rate) 定义:预测的识别语音序列于groundtruth抄本之间的编辑距离 除以 ground truth抄本的单词数量 编辑距离 (预测的识别语音序列,groundtruth 抄本)/ ground truth抄本的单词数量 英文定义:It is g…...
英伟达(NVIDIA)
本文来自智谱清言 ------------------------------ 英伟达(NVIDIA)是一家成立于1993年的美国跨国科技公司,由黄仁勋、克里斯马拉科夫斯基和柯蒂斯普里姆共同创立。公司总部位于加利福尼亚州圣克拉拉市。英伟达最初专注于图形芯片的设计&…...
【环境配置】Jupyter Notebook切换虚拟环境
在Jupyter Notebook中是可以切换虚拟环境的,以下是几种常见的方法: 方法一:使用nb_conda_kernels扩展(适用于Anaconda环境) 安装 如果你使用的是Anaconda环境,首先确保你已经安装了 nb_conda 包。如果没…...
嵌入式单片机窗口看门狗控制与实现
窗口看门狗 注意:WWDG外设没有独立的时钟源,而是挂载在APB1总线下,APB1总线外设时钟为42MHZ。 了解WWDG外设的使用流程,可以参考stm32f4xx_wwdg.c的开头注释,具体流程如下图所示...
NiChart 多模态神经影像(structural MRI,functional MRI,and diffusion MRI)处理和分析工具包安装
NiChart多模态神经影像部署 NiChart 本地安装Git clone 问题personal access token PAT 问题 NiChart 云端注册AWS验证问题 NiChart 是UPenn大学,Christos Davatzikos教授开发的一个多模态MRI影像,structural (sMRI), diffusion (dMRI), and …...
Es搭建——单节点——Linux
Es搭建——单节点——Linux 一、安装 下载安装包: 官网下载地址:https://www.elastic.co/downloads/elasticsearch 上传包到linux 切换到安装目录下 解压:tar -zxvf elasticsearch-7.17.1-linux-x86_64.tar.gz 重命名安装文件夹 mv elastics…...
Python自动化测试之线上流量回放:录制、打标、压测与平台选择
在自动化测试中,线上流量回放是一项关键技术,可以模拟真实用户的请求并重现线上场景,验证系统的性能和稳定性。本文将介绍Python自动化测试中的线上流量回放技术,并提供实战代码,帮助你了解流量的录制、打标、压测发起…...
k-Means聚类算法 HNUST【数据分析技术】(2025)
1.理论知识 K-means算法,又称为k均值算法。K-means算法中的k表示的是聚类为k个簇,means代表取每一个聚类中数据值的均值作为该簇的中心,或者称为质心,即用每一个的类的质心对该簇进行描述。K-Means算法接受参数K;然后将…...
STM32学习之 按键/光敏电阻 控制 LED/蜂鸣器
STM32学习之 按键/光敏电阻 控制 LED/蜂鸣器 1、按键控制 LED 按键:常见的输入设备,按下导通,松手断开 按键抖动:由子按键内部使用的是机械式弹簧片来进行通断的、所以在按下和松手的瞬间会伴随有一连串的抖动 按键控制LED接线图: 要有工程…...
测试微信模版消息推送
进入“开发接口管理”--“公众平台测试账号”,无需申请公众账号、可在测试账号中体验并测试微信公众平台所有高级接口。 获取access_token: 自定义模版消息: 关注测试号:扫二维码关注测试号。 发送模版消息: import requests da…...
QMC5883L的驱动
简介 本篇文章的代码已经上传到了github上面,开源代码 作为一个电子罗盘模块,我们可以通过I2C从中获取偏航角yaw,相对于六轴陀螺仪的yaw,qmc5883l几乎不会零飘并且成本较低。 参考资料 QMC5883L磁场传感器驱动 QMC5883L磁力计…...
SCAU期末笔记 - 数据分析与数据挖掘题库解析
这门怎么题库答案不全啊日 来简单学一下子来 一、选择题(可多选) 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘:专注于发现数据中…...
论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一)
宇树机器人多姿态起立控制强化学习框架论文解析 论文解读:交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一) 论文解读:交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化…...
OpenLayers 分屏对比(地图联动)
注:当前使用的是 ol 5.3.0 版本,天地图使用的key请到天地图官网申请,并替换为自己的key 地图分屏对比在WebGIS开发中是很常见的功能,和卷帘图层不一样的是,分屏对比是在各个地图中添加相同或者不同的图层进行对比查看。…...
全志A40i android7.1 调试信息打印串口由uart0改为uart3
一,概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本:2014.07; Kernel版本:Linux-3.10; 二,Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01),并让boo…...
python报错No module named ‘tensorflow.keras‘
是由于不同版本的tensorflow下的keras所在的路径不同,结合所安装的tensorflow的目录结构修改from语句即可。 原语句: from tensorflow.keras.layers import Conv1D, MaxPooling1D, LSTM, Dense 修改后: from tensorflow.python.keras.lay…...
Java数值运算常见陷阱与规避方法
整数除法中的舍入问题 问题现象 当开发者预期进行浮点除法却误用整数除法时,会出现小数部分被截断的情况。典型错误模式如下: void process(int value) {double half = value / 2; // 整数除法导致截断// 使用half变量 }此时...
NPOI操作EXCEL文件 ——CAD C# 二次开发
缺点:dll.版本容易加载错误。CAD加载插件时,没有加载所有类库。插件运行过程中用到某个类库,会从CAD的安装目录找,找不到就报错了。 【方案2】让CAD在加载过程中把类库加载到内存 【方案3】是发现缺少了哪个库,就用插件程序加载进…...
Golang——9、反射和文件操作
反射和文件操作 1、反射1.1、reflect.TypeOf()获取任意值的类型对象1.2、reflect.ValueOf()1.3、结构体反射 2、文件操作2.1、os.Open()打开文件2.2、方式一:使用Read()读取文件2.3、方式二:bufio读取文件2.4、方式三:os.ReadFile读取2.5、写…...
