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

关于贪心算法的一个小结

下面的内容主要参考了数据结构与算法之美。

贪心算法的应用有:

  1. 霍夫曼编码(Huffman Coding)

  2. Prim和Kruskal最小生成树算法

  3. 01背包问题(当允许取部分物品的时候)

  4. 分糖果
    我们有m个糖果和n个孩子。我们现在要把糖果分给这些孩子吃,但是糖果少,孩子多(m<n),所以糖果只能分配给一部分孩子。每个糖果的大小不等,这m个糖果的大小分别是s1,s2,s3,……,sm。除此之外,每个孩子对糖果大小的需求也是不一样的,只有糖果的大小大于等于孩子的对糖果大小的需求的时候,孩子才得到满足。假设这n个孩子对糖果大小的需求分别是g1,g2,g3,……,gn。
    如何分配糖果,能尽可能满足最多数量的孩子?
    我们可以把这个问题抽象成,从n个孩子中,抽取一部分孩子分配糖果,让满足的孩子的个数(期望值)是最大的。这个问题的限制值就是糖果个数m。
    我们现在来看看如何用贪心算法来解决。对于一个孩子来说,如果小的糖果可以满足,我们就没必要用更大的糖果,这样更大的就可以留给其他对糖果大小需求更大的孩子。另一方面,对糖果大小需求小的孩子更容易被满足,所以,我们可以从需求小的孩子开始分配糖果。因为满足一个需求大的孩子跟满足一个需求小的孩子,对我们期望值的贡献是一样的。
    我们每次从剩下的孩子中,找出对糖果大小需求最小的,然后发给他剩下的糖果中能满足他的最小的糖果,这样得到的分配方案,也就是满足的孩子个数最多的方案。

  5. 假设我们有n个区间,区间的起始端点和结束端点分别是[l1, r1],[l2, r2],[l3, r3],……,[ln, rn]。我们从这n个区间中选出一部分区间,这部分区间满足两两不相
    交(端点相交的情况不算相交),最多能选出多少个区间呢?
    这个问题的解决思路是这样的:我们假设这n个区间中最左端点是lmin,最右端点是rmax。这个问题就相当于,我们选择几个不相交的区间,从左到右将[lmin,rmax]覆盖上。我们按照起始端点从小到大的顺序对这n个区间排序。
    我们每次选择的时候,左端点跟前面的已经覆盖的区间不重合的,右端点又尽量小的,这样可以让剩下的未覆盖区间尽可能的大,就可以放置更多的区间。这实
    际上就是一种贪心的选择方法。

  6. 在一个非负整数 a 中,我们希望从中移除 k 个数字,让剩下的数字值最小,如何选择移除哪 k 个数字呢?
    由最高位开始,比较低一位数字,如高位大,移除,若高位小,则向右移一位继续比较两个数字,直到高位大于低位则移除,循环k次,如:
    4556847594546移除5位-》455647594546-》45547594546-》4547594546-》4447594546-》444594546

  7. 假设有 n 个人等待被服务,但是窗口只有一个,每个需要被服务的时间长度是不同的,如何安排被服务的先后顺序,才能让这 n 个人总的等待时间最短
    由等待时间最短的开始服务

注意:Dijkstra不是贪心算法,事实上它是动态规划算法,求得的解全局最优解

相关文章:

关于贪心算法的一个小结

下面的内容主要参考了数据结构与算法之美。 贪心算法的应用有&#xff1a; 霍夫曼编码&#xff08;Huffman Coding&#xff09; Prim和Kruskal最小生成树算法 01背包问题(当允许取部分物品的时候) 分糖果 我们有m个糖果和n个孩子。我们现在要把糖果分给这些孩子吃&#xff…...

五、DQL-2.基本查询

一、数据准备 1、删除表employee&#xff1a; drop table employee; 2、创建表emp&#xff1a; 3、添加数据&#xff1a; 4、查看表数据&#xff1a; 【代码】 -- 查询数据--------------------------------------------------------- drop table emp;-- 数据准备-----------…...

SSL证书常见问题:SSL证书的概念和作用

什么是SSL证书&#xff1f; SSL证书是一种数字证书&#xff0c;它与身份证、驾照的功能一样&#xff0c;用于证明网站的身份。SSL证书是由全球信任的证书颁发机构&#xff08;CA&#xff09;在验证服务器身份后颁发&#xff0c;安装SSL证书后会激活HTTPS协议&#xff0c;在用户…...

J2EEXML建模

目录 用一个xml-config文件实例&#xff1a; 先看config.xml文件 再看 ActionModel ConfigModel ActionNotFoundException ForwardNotFoundException ConfigModelFactory ActionDuplicateDefinitionException ForwardDuplicateDefinitionException InvalidPathExcept…...

vue中export和export default

参考&#xff1a;vue中export和export default的使用 参考&#xff1a;vue里的export default...

转职做项目经理,我为什么选择PMP?

老实说&#xff0c;在学习PMP之前&#xff0c;我做了很长时间的思想斗争&#xff0c;一是平时工作有些忙&#xff0c;没有大块儿时间集中学习&#xff1b;二是不确定考完之后是否真能用上。但现在我可以很明确的告诉每一个想学习PMP的人&#xff1a;放心学吧&#xff0c;知识不…...

LangChain(5)Conversational Agents

Large Language Models (LLMs) 在语义知识方面表现不错&#xff0c;但也有一些不足&#xff0c;如&#xff1a;不能正确计算数学公式、无法获取最新知识新闻 通过 Agents 可以赋予 LLMs 更多能力&#xff0c;让LLM能够计算、上网查询 agent 简单使用 from langchain import …...

【云原生】Kubernetes临时容器

临时容器 特性状态&#xff1a; Kubernetes v1.25 [stable] 本页面概述了临时容器&#xff1a;一种特殊的容器&#xff0c;该容器在现有 Pod 中临时运行&#xff0c;以便完成用户发起的操作&#xff0c;例如故障排查。 你会使用临时容器来检查服务&#xff0c;而不是用它来构建…...

Jenkins+Robot 接口自动化测试

目录 前言&#xff1a; 设计目标 项目说明 目录结构 配置 jenkins 1.安装插件 2.配置项目 前言&#xff1a; JenkinsRobot是一种常见的接口自动化测试方案&#xff0c;可以实现自动化的接口测试和持续集成。Jenkins是一个流行的持续集成工具&#xff0c;而Robot Framew…...

【Visual Studio Code】---自定义键盘快捷键设置

概述 一个好的文章能够帮助开发者完成更便捷、更快速的开发。书山有路勤为径&#xff0c;学海无涯苦作舟。我是秋知叶i、期望每一个阅读了我的文章的开发者都能够有所成长。 一、进入键盘快捷键设置 1、进入键盘快捷键设置方法1 使用快捷键进入键盘快捷键设置先按 Ctrl K再…...

FastEdit ⚡:在10秒内编辑大型语言模型

概述&#xff1a; 这个仓库旨在通过一个单一的命令&#xff0c;有效地将新鲜且定制化的知识注入到大型语言模型中&#xff0c;以辅助开发人员的工作。 支持的模型&#xff1a;○ GPT-J (6B)○ LLaMA (7B/13B)○ BLOOM (7.1B)○ Falcon (7B)○ Baichuan (7B/13B)○ InternLM (7…...

SpringBoot + Docker 实现一次构建到处运行

一、容器化部署的好处 Docker 作为一种新兴的虚拟化方式&#xff0c;它可以更高效的利用系统资源&#xff0c;不需要进行硬件虚拟以及运行完整操作系统等额外开销。 传统的虚拟机技术启动应用服务往往需要数分钟&#xff0c;而 Docker 容器应用&#xff0c;由于直接运行宿主内…...

Spring-Cloud-Gateway如何自定义断言工厂?

遇到这么一个面试题&#xff1a;如何在网关做配置&#xff0c;实现只有在早晨9点到下午18点之间接口才允许访问&#xff0c;其他时间访问都是404。 我们知道网关的一个重要的作用就是路由转发&#xff0c;路由表的配置大概是这个样子: spring:cloud:gateway:routes:- id: user…...

Android平台如何高效率实现GB28181对接?

技术背景 GB28181协议是一种用于设备状态信息报送的协议&#xff0c;可以在不同设备之间进行通信和数据传输。 在安卓系统上实现GB/T 28181非常必要&#xff0c;GB28181协议实现分两部分&#xff0c;一部分是信令&#xff0c;另外一部分就是媒体数据的编码。 信令主要包括S…...

vue2 实现后台管理系统左侧菜单联动实现 tab根据路由切换联动内容,并支持移动端框架

效果图&#xff1a; pc端 移动端 由于代码比较多&#xff0c;我这里就不一一介绍了&#xff0c;可以去我的git上把项目拉下来 git地址https://gitee.com/Flechazo7/htglck.git 后台我是用node写的有需要的可以评论联系...

一本通1910:【00NOIP普及组】计算器的改良题解

今天是编程集训的第二天&#xff0c;也是我来到CSDN整整1年。感谢所有阅读过我的文章的人&#xff0c;谢谢。 今天的比赛难度略低于昨天&#xff0c;但这道题也卡了我好久。 进入正题 题目&#xff1a; 题目描述&#xff1a; NCL是一家专门从事计算器改良与升级的实验室&a…...

golang网络编程学习-1rpc

网络编程主要的内容是&#xff1a; 1.TCP网络编程 2.http服务 3.rpc服务 4.websocket服务 一、rpc RPC 框架----- 远程过程调用协议RPC&#xff08;Remote Procedure Call Protocol)-----允许像调用本地服务一样调用远程服务。 RPC是指远程过程调用&#xff0c;也就是说两台服…...

【MQTT】Esp32数据上传采集:最新mqtt插件(支持掉线、真机调试错误等问题)

前言 这是我在Dcloud发布的插件-最完整Mqtt示例代码&#xff08;解决掉线、真机调试错误等问题&#xff09;&#xff0c;经过整改优化和替换Mqtt的js文件使一些市场上出现的问题得以解决&#xff0c;至于跨端出问题&#xff0c;可能原因有很多&#xff0c;例如&#xff0c;合法…...

基于PyQt5的UI界面开发——对基本控件的介绍

基本控件介绍 在PyQt中&#xff0c;控件是用户界面上的可见元素。控件可以包括按钮、标签、文本框、进度条等。每个控件都有自己的属性和方法&#xff0c;可以通过编程方式进行调整和操作。 以下是一些常用的PyQt控件&#xff1a; QLabel&#xff08;标签&#xff09;&#…...

flink 报错:Caused by: java.lang.RuntimeException: Assigned key must not be null!

问题描述 不同情况下需要找对应的解决方法&#xff0c;这里介绍的解决方法不能拓展到别的场景。 场景描述&#xff1a; flink job 的开发过程中遇到这样的需求&#xff0c;需要先 map 处理&#xff0c;然后把返回的 DataStream 作为输入&#xff0c;流入别的 map 中。这里我们遇…...

铭豹扩展坞 USB转网口 突然无法识别解决方法

当 USB 转网口扩展坞在一台笔记本上无法识别,但在其他电脑上正常工作时,问题通常出在笔记本自身或其与扩展坞的兼容性上。以下是系统化的定位思路和排查步骤,帮助你快速找到故障原因: 背景: 一个M-pard(铭豹)扩展坞的网卡突然无法识别了,扩展出来的三个USB接口正常。…...

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; 左…...

51c自动驾驶~合集58

我自己的原文哦~ https://blog.51cto.com/whaosoft/13967107 #CCA-Attention 全局池化局部保留&#xff0c;CCA-Attention为LLM长文本建模带来突破性进展 琶洲实验室、华南理工大学联合推出关键上下文感知注意力机制&#xff08;CCA-Attention&#xff09;&#xff0c;…...

树莓派超全系列教程文档--(62)使用rpicam-app通过网络流式传输视频

使用rpicam-app通过网络流式传输视频 使用 rpicam-app 通过网络流式传输视频UDPTCPRTSPlibavGStreamerRTPlibcamerasrc GStreamer 元素 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 使用 rpicam-app 通过网络流式传输视频 本节介绍来自 rpica…...

【入坑系列】TiDB 强制索引在不同库下不生效问题

文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...

2.Vue编写一个app

1.src中重要的组成 1.1main.ts // 引入createApp用于创建应用 import { createApp } from "vue"; // 引用App根组件 import App from ./App.vue;createApp(App).mount(#app)1.2 App.vue 其中要写三种标签 <template> <!--html--> </template>…...

Java 加密常用的各种算法及其选择

在数字化时代&#xff0c;数据安全至关重要&#xff0c;Java 作为广泛应用的编程语言&#xff0c;提供了丰富的加密算法来保障数据的保密性、完整性和真实性。了解这些常用加密算法及其适用场景&#xff0c;有助于开发者在不同的业务需求中做出正确的选择。​ 一、对称加密算法…...

LINUX 69 FTP 客服管理系统 man 5 /etc/vsftpd/vsftpd.conf

FTP 客服管理系统 实现kefu123登录&#xff0c;不允许匿名访问&#xff0c;kefu只能访问/data/kefu目录&#xff0c;不能查看其他目录 创建账号密码 useradd kefu echo 123|passwd -stdin kefu [rootcode caozx26420]# echo 123|passwd --stdin kefu 更改用户 kefu 的密码…...

CVPR2025重磅突破:AnomalyAny框架实现单样本生成逼真异常数据,破解视觉检测瓶颈!

本文介绍了一种名为AnomalyAny的创新框架&#xff0c;该方法利用Stable Diffusion的强大生成能力&#xff0c;仅需单个正常样本和文本描述&#xff0c;即可生成逼真且多样化的异常样本&#xff0c;有效解决了视觉异常检测中异常样本稀缺的难题&#xff0c;为工业质检、医疗影像…...

算法—栈系列

一&#xff1a;删除字符串中的所有相邻重复项 class Solution { public:string removeDuplicates(string s) {stack<char> st;for(int i 0; i < s.size(); i){char target s[i];if(!st.empty() && target st.top())st.pop();elsest.push(s[i]);}string ret…...