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

算法进阶:贪心算法

贪心算法是一种简单而直观的算法思想,它在每一步选择中都采取在当前状态下最优的选择,以期望最终得到全局最优解。贪心算法通常适用于一些具有最优子结构的问题,即问题的最优解可以通过一系列局部最优解的选择得到。

贪心算法的基本思路是,每一步都选择当前状态下的局部最优解,并把它添加到当前解中。然后,根据已经做出的选择,对剩下的子问题进行求解。这个过程持续进行,直到得到全局最优解。

然而,贪心算法并不是适用于所有问题的。在一些情况下,贪心算法可能会得到次优解或者不正确的解。这是因为贪心算法在每一步都做出局部最优选择,并没有考虑到该选择对之后步骤的影响。

综上所述,贪心算法是一种简单而直观的算法思想,可以用来解决一些具有最优子结构的问题。

目录

贪心算法(找零问题)

背包问题

分数背包

数字拼接问题

常识:时间戳

活动选择问题


贪心算法(找零问题)

# 贪心算法
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)]

相关文章:

算法进阶:贪心算法

贪心算法是一种简单而直观的算法思想&#xff0c;它在每一步选择中都采取在当前状态下最优的选择&#xff0c;以期望最终得到全局最优解。贪心算法通常适用于一些具有最优子结构的问题&#xff0c;即问题的最优解可以通过一系列局部最优解的选择得到。 贪心算法的基本思路是&a…...

C++ 设计模式:工厂方法(Factory Method)

链接&#xff1a;C 设计模式 链接&#xff1a;C 设计模式 - 抽象工厂 链接&#xff1a;C 设计模式 - 原型模式 链接&#xff1a;C 设计模式 - 建造者模式 工厂方法&#xff08;Factory Method&#xff09;是创建型设计模式之一&#xff0c;它提供了一种创建对象的接口&#xf…...

手机联系人 查询 添加操作

Android——添加联系人_android 添加联系人-CSDN博客 上面连接添加联系人已测试 是可以 Android : 获取、添加、手机联系人-ContentResolver简单应用_contentresolver 添加联系人-CSDN博客...

【LeetCode】2506、统计相似字符串对的数目

【LeetCode】2506、统计相似字符串对的数目 文章目录 一、哈希表位运算1.1 哈希表位运算 二、多语言解法 一、哈希表位运算 1.1 哈希表位运算 每个字符串, 可用一个 int 表示. (每个字符 是 int 的一个位) 哈希表记录各 字符组合 出现的次数 步骤: 遇到一个字符串, 得到 ma…...

金仓数据库对象访问权限的管理

基础知识 对象的分类 数据库的表、索引、视图、缺省值、规则、触发器等等&#xff0c;都称为数据库对象&#xff0c;对象分为如下两类: 模式(SCHEMA)对象:可以理解为一个存储目录&#xff0c;包含视图、索引、数据类型、函数和操作符等。非模式对象:其他的数据库对象&#x…...

Qt 中实现系统主题感知

【写在前面】 在现代桌面应用程序开发中&#xff0c;系统主题感知是一项重要的功能&#xff0c;它使得应用程序能够根据用户的系统主题设置&#xff08;如深色模式或浅色模式&#xff09;自动调整其外观。 Qt 作为一个跨平台的C图形用户界面应用程序开发框架&#xff0c;提供…...

Modbus TCP 报文说明

Modbus TCP 报文说明 Modbus TCP 报文结构报文解析功能码说明Modbus 功能码与 PLC 地址的对应关系 Modbus TCP 报文结构 事务标识符&#xff08;Transaction Identifier&#xff0c;2 字节&#xff09;&#xff1a; 用于匹配请求和响应&#xff0c;通常由客户端生成&#xff0…...

音视频入门基础:MPEG2-TS专题(24)——FFmpeg源码中,显示TS流每个packet的pts、dts的实现

音视频入门基础&#xff1a;MPEG2-TS专题系列文章&#xff1a; 音视频入门基础&#xff1a;MPEG2-TS专题&#xff08;1&#xff09;——MPEG2-TS官方文档下载 音视频入门基础&#xff1a;MPEG2-TS专题&#xff08;2&#xff09;——使用FFmpeg命令生成ts文件 音视频入门基础…...

大模型:OneFitsAll、Time - LLM、LLaTA

LLM数据集:ETT、Illness、Weather ETT、Illness、Weather在上述提到的论文中都是用于时间序列预测研究的真实世界数据集,以下是对它们的具体介绍: ETT数据集 内容:ETT是电力变压器温度(Electric Transformer Temperature)数据集,通常包含电力变压器在不同时间点的温度…...

连锁餐饮行业数据可视化分析方案

引言 随着连锁餐饮行业的迅速发展&#xff0c;市场竞争日益激烈。企业需要更加精准地把握运营状况、消费者需求和市场趋势&#xff0c;以制定科学合理的决策&#xff0c;提升竞争力和盈利能力。可视化数据分析可以帮助连锁餐饮企业整合多源数据&#xff0c;通过直观、动态的可…...

Ubuntu 下使用命令行将 U 盘格式化为 ext4、FAT32 和 exFAT 的详细教程

Ubuntu 下使用命令行将 U 盘格式化为 ext4、FAT32 和 exFAT 的详细教程 作者&#xff1a;Witheart更新时间&#xff1a;20241228 本教程将详细介绍如何将 U 盘格式化为 ext4、FAT32 和 exFAT 文件系统&#xff0c;同时包括如何安装必要工具&#xff08;如 exfat-utils&#x…...

多说话人ASR的衡量指标和有效计算工具包

WER (Word Error Rate) 定义&#xff1a;预测的识别语音序列于groundtruth抄本之间的编辑距离 除以 ground truth抄本的单词数量 编辑距离 &#xff08;预测的识别语音序列&#xff0c;groundtruth 抄本&#xff09;/ ground truth抄本的单词数量 英文定义&#xff1a;It is g…...

英伟达(NVIDIA)

本文来自智谱清言 ------------------------------ 英伟达&#xff08;NVIDIA&#xff09;是一家成立于1993年的美国跨国科技公司&#xff0c;由黄仁勋、克里斯马拉科夫斯基和柯蒂斯普里姆共同创立。公司总部位于加利福尼亚州圣克拉拉市。英伟达最初专注于图形芯片的设计&…...

【环境配置】Jupyter Notebook切换虚拟环境

在Jupyter Notebook中是可以切换虚拟环境的&#xff0c;以下是几种常见的方法&#xff1a; 方法一&#xff1a;使用nb_conda_kernels扩展&#xff08;适用于Anaconda环境&#xff09; 安装 如果你使用的是Anaconda环境&#xff0c;首先确保你已经安装了 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大学&#xff0c;Christos Davatzikos教授开发的一个多模态MRI影像&#xff0c;structural (sMRI), diffusion (dMRI)&#xff0c; and …...

Es搭建——单节点——Linux

Es搭建——单节点——Linux 一、安装 下载安装包&#xff1a; 官网下载地址&#xff1a;https://www.elastic.co/downloads/elasticsearch 上传包到linux 切换到安装目录下 解压&#xff1a;tar -zxvf elasticsearch-7.17.1-linux-x86_64.tar.gz 重命名安装文件夹 mv elastics…...

Python自动化测试之线上流量回放:录制、打标、压测与平台选择

在自动化测试中&#xff0c;线上流量回放是一项关键技术&#xff0c;可以模拟真实用户的请求并重现线上场景&#xff0c;验证系统的性能和稳定性。本文将介绍Python自动化测试中的线上流量回放技术&#xff0c;并提供实战代码&#xff0c;帮助你了解流量的录制、打标、压测发起…...

k-Means聚类算法 HNUST【数据分析技术】(2025)

1.理论知识 K-means算法&#xff0c;又称为k均值算法。K-means算法中的k表示的是聚类为k个簇&#xff0c;means代表取每一个聚类中数据值的均值作为该簇的中心&#xff0c;或者称为质心&#xff0c;即用每一个的类的质心对该簇进行描述。K-Means算法接受参数K&#xff1b;然后将…...

STM32学习之 按键/光敏电阻 控制 LED/蜂鸣器

STM32学习之 按键/光敏电阻 控制 LED/蜂鸣器 1、按键控制 LED 按键:常见的输入设备&#xff0c;按下导通&#xff0c;松手断开 按键抖动:由子按键内部使用的是机械式弹簧片来进行通断的、所以在按下和松手的瞬间会伴随有一连串的抖动 按键控制LED接线图&#xff1a; 要有工程…...

变量 varablie 声明- Rust 变量 let mut 声明与 C/C++ 变量声明对比分析

一、变量声明设计&#xff1a;let 与 mut 的哲学解析 Rust 采用 let 声明变量并通过 mut 显式标记可变性&#xff0c;这种设计体现了语言的核心哲学。以下是深度解析&#xff1a; 1.1 设计理念剖析 安全优先原则&#xff1a;默认不可变强制开发者明确声明意图 let x 5; …...

三维GIS开发cesium智慧地铁教程(5)Cesium相机控制

一、环境搭建 <script src"../cesium1.99/Build/Cesium/Cesium.js"></script> <link rel"stylesheet" href"../cesium1.99/Build/Cesium/Widgets/widgets.css"> 关键配置点&#xff1a; 路径验证&#xff1a;确保相对路径.…...

MFC内存泄露

1、泄露代码示例 void X::SetApplicationBtn() {CMFCRibbonApplicationButton* pBtn GetApplicationButton();// 获取 Ribbon Bar 指针// 创建自定义按钮CCustomRibbonAppButton* pCustomButton new CCustomRibbonAppButton();pCustomButton->SetImage(IDB_BITMAP_Jdp26)…...

今日科技热点速览

&#x1f525; 今日科技热点速览 &#x1f3ae; 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售&#xff0c;主打更强图形性能与沉浸式体验&#xff0c;支持多模态交互&#xff0c;受到全球玩家热捧 。 &#x1f916; 人工智能持续突破 DeepSeek-R1&…...

什么?连接服务器也能可视化显示界面?:基于X11 Forwarding + CentOS + MobaXterm实战指南

文章目录 什么是X11?环境准备实战步骤1️⃣ 服务器端配置(CentOS)2️⃣ 客户端配置(MobaXterm)3️⃣ 验证X11 Forwarding4️⃣ 运行自定义GUI程序(Python示例)5️⃣ 成功效果![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/55aefaea8a9f477e86d065227851fe3d.pn…...

提升移动端网页调试效率:WebDebugX 与常见工具组合实践

在日常移动端开发中&#xff0c;网页调试始终是一个高频但又极具挑战的环节。尤其在面对 iOS 与 Android 的混合技术栈、各种设备差异化行为时&#xff0c;开发者迫切需要一套高效、可靠且跨平台的调试方案。过去&#xff0c;我们或多或少使用过 Chrome DevTools、Remote Debug…...

【UE5 C++】通过文件对话框获取选择文件的路径

目录 效果 步骤 源码 效果 步骤 1. 在“xxx.Build.cs”中添加需要使用的模块 &#xff0c;这里主要使用“DesktopPlatform”模块 2. 添加后闭UE编辑器&#xff0c;右键点击 .uproject 文件&#xff0c;选择 "Generate Visual Studio project files"&#xff0c;重…...

Unity VR/MR开发-VR开发与传统3D开发的差异

视频讲解链接&#xff1a;【XR马斯维】VR/MR开发与传统3D开发的差异【UnityVR/MR开发教程--入门】_哔哩哔哩_bilibili...

李沐--动手学深度学习--GRU

1.GRU从零开始实现 #9.1.2GRU从零开始实现 import torch from torch import nn from d2l import torch as d2l#首先读取 8.5节中使用的时间机器数据集 batch_size,num_steps 32,35 train_iter,vocab d2l.load_data_time_machine(batch_size,num_steps) #初始化模型参数 def …...

GeoServer发布PostgreSQL图层后WFS查询无主键字段

在使用 GeoServer&#xff08;版本 2.22.2&#xff09; 发布 PostgreSQL&#xff08;PostGIS&#xff09;中的表为地图服务时&#xff0c;常常会遇到一个小问题&#xff1a; WFS 查询中&#xff0c;主键字段&#xff08;如 id&#xff09;莫名其妙地消失了&#xff01; 即使你在…...