高级算法设计与分析(四) -- 贪心算法
系列文章目录
高级算法设计与分析(一) -- 算法引论
高级算法设计与分析(二) -- 递归与分治策略
高级算法设计与分析(三) -- 动态规划
高级算法设计与分析(四) -- 贪心算法
高级算法设计与分析(五) -- 回溯法
高级算法设计与分析(六) -- 分支限界法
高级算法设计与分析(七) -- 概率算法和NP完全性理论
高级算法设计与分析(八) -- 总结
目录
系列文章目录
前言
一、贪心算法的基本思想
二、活动安排问题
三、贪心算法的基本要素
四、哈夫曼编码
五、单源最短路径-Dijkstra算法
六、最小生成树
1、基础概念与问题
2、prim算法(普里姆算法)
3、kruskai算法(克鲁斯卡尔算法)
习题
前言
tips:这里只是总结,不是教程哈。鉴于本人写字如画符,就不出视频教程了,如实在有需要,请在文章下方留言。当然,文章有任何问题,也请留言,谢谢!
这个系列用另一种形式,把习题放在最下面,看看好用不。
本系列文章最后一文会进行简要全部总结,以及思维导图放在最后一篇文章最下面,请自行获取。
一、贪心算法的基本思想

50,20,0.2,0.1
3*5

二、活动安排问题
1、问题描述
给定一组活动,每个活动都有一个开始时间和结束时间,目标是安排出一个最大数量的相互兼容的活动集合,即这些活动之间不会相互冲突。
2、例子

3、步骤:
因为是按照结束时间的非减排序的,选择第一个后(红1),把开始时间在这个活动结束时间之前的都排除(红叉),然后继续选择未排除的结束时间最早的一个(绿2),把开始时间在这个活动结束时间之前的都排除(绿叉),以此类推……

4、算法正确性证明:


另一种表述,看你们能接收那种


三、贪心算法的基本要素
1、贪心选择性质、最优子结构

***自顶向下和自底向上

2、证明方法



4、贪心算法的适用范围

5、背包问题和0-1背包问题


四、哈夫曼编码

复杂度


五、单源最短路径-Dijkstra算法
1、问题描述


有向图
2、算法的基本思想


3、将算法用程序描述







复杂度分析:时间复杂度:o(|V|^2)
4、算法正确性证明


六、最小生成树
1、基础概念与问题


2、prim算法(普里姆算法)

2.1、直接算法实现

2.2、prim算法实现









时间复杂度:o(|V|^2)
3、kruskai算法(克鲁斯卡尔算法)



习题
topic1:

topic2:

topic3:

topic4:

topic5:



topic5:

topic6:

相关文章:
高级算法设计与分析(四) -- 贪心算法
系列文章目录 高级算法设计与分析(一) -- 算法引论 高级算法设计与分析(二) -- 递归与分治策略 高级算法设计与分析(三) -- 动态规划 高级算法设计与分析(四) -- 贪心算法 高级…...
MATLAB - 机器人逆运动学设计器(Inverse Kinematics Designer APP)
系列文章目录 前言 一、简介 通过逆运动学设计器,您可以为 URDF 机器人模型设计逆运动学求解器。您可以调整逆运动学求解器并添加约束条件,以实现所需的行为。使用该程序,您可以 从 URDF 文件或 MATLAB 工作区导入 URDF 机器人模型。调整逆…...
使用OpenCV DNN模块进行人脸检测
内容的一部分来源于贾志刚的《opencv4应用开发、入门、进阶与工程化实践》。这本书我大概看了一下,也就后面几章比较感兴趣,但是内容很少,并没有想像的那种充实。不过学习还是要学习的。 在实际工程项目中,并不是说我们将神经网络…...
C#中使用OpenCV的常用函数
以下是一些C#中使用OpenCV的常用函数例子: 1. 加载图像: using OpenCvSharp;Mat image Cv2.ImRead("path_to_your_image.jpg", ImreadModes.Color); 2. 显示图像: Cv2.NamedWindow("Image Window", WindowFlags.Nor…...
使用Swift Package Manager (SPM)实现xcframework分发
Swift Package Manager (SPM) 是苹果官方提供的用于管理 Swift 项目的依赖关系和构建过程的工具。它是一个集成在 Swift 编程语言中的包管理器,用于解决在开发过程中管理和构建包依赖项的需求。 1、上传xcframework.zip到服务端 压缩xcframeworks成一个zip包&…...
非阻塞 IO(NIO)
文章目录 非阻塞 IO(NIO)模型驱动程序应用程序模块使用 非阻塞 IO(NIO) 上一节中 https://blog.csdn.net/tyustli/article/details/135140523,使用等待队列头实现了阻塞 IO 程序使用时,阻塞 IO 和非阻塞 IO 的区别在于文件打开的时候是否使用了 O_NONB…...
Android应用-flutter使用Positioned将控件定位到底部中间
文章目录 场景描述示例解释 场景描述 要将Positioned定位到屏幕底部中间的位置,你可以使用MediaQuery来获取屏幕的高度,然后设置Positioned的bottom属性和left或right属性,一般我们left和right都会设置一个值让控制置于合适的位置࿰…...
Django 简单图书管理系统
一、图书需求 1. 书籍book_index.html中有超链接:查看所有的书籍列表book_list.html页面 2. 书籍book_list.html中显示所有的书名,有超链接:查看本书籍详情book_detail.html(通过书籍ID)页面 3. 书籍book_detail.html中书的作者和出版社&…...
C++内存管理和模板初阶
C/C内存分布 请看代码: int globalVar 1; static int staticGlobalVar 1; void Test() {static int staticVar 1;int localVar 1;int num1[10] { 1, 2, 3, 4 };char char2[] "abcd";const char* pChar3 "abcd";int* ptr1 (int*)mallo…...
QtRO(Qt Remote Objects)分布式对象远程通信
一、什么是QtRO Qt Remote Objects(QRO)是Qt提供的一种用于实现远程对象通信的机制。 QtRO支持两种类型的通信:RPC(远程过程调用)和LPC(本地进程通信)。 RPC(远程过程调用…...
【K8s】1# 使用kuboard-spray安装K8s集群
文章目录 搭建k8s集群1.推荐配置1.1.服务器配置1.2.软件版本 2.使用Kuboard-Spray安装k8s集群2.1.配置要求2.2.操作系统兼容性2.3.安装 Kuboard-Spray2.4.加载离线资源包2.5.规划并安装集群2.6.安装成功2.7.访问集群 3.涉及的命令3.1.linux 4.问题汇总Q1:启动离线集…...
leetCode算法—12. 整数转罗马数字
12. 整数转罗马数字 难度:中等 ** 罗马数字包含以下七种字符: I, V, X, L,C,D 和 M。 字符 数值 I 1 V 5 X 10 L 50 C 100 D 500 M 1000 例如, 罗马数字 2 写做 II ,即…...
使用OpenCV4实现工业缺陷检测的六种方法
目录 1 机器视觉2 缺陷检测3 工业上常见缺陷检测方法 1 机器视觉 机器视觉是使用各种工业相机,结合传感器跟电气信号实现替代传统人工,完成对象识别、计数、测量、缺陷检测、引导定位与抓取等任务。其中工业品的缺陷检测极大的依赖人工完成,…...
Excel 获取当前行的行数
ROW() 获取当前行 ROW()1 获取当前行然后支持二次开发...
R语言【stringr】——str_detect 检测是否存在字符串的匹配项
Package stringr version 1.5.1 str_detect(string, pattern, negate FALSE) 参数【string】:输入向量。既可以是字符向量,也可以是强制作为一个字符向量。 参数【pattern】:要寻找的模式。默认解释为正则表达式,如 vignette(&…...
【SpringMVC】SpringMVC的请求与响应
文章目录 0. Tomcat环境的配置1. PostMan工具介绍创建WorkSpace建立新的请求 2. 请求映射路径案例结构与代码案例结构案例代码 案例存在问题解决方案方法方法升级版——配置请求路径前缀注解总结 3. Get请求与Post请求案例结构与案例代码案例结构案例代码 Get请求Post请求接收中…...
Spring Boot3通过GraalVM生成exe执行文件
一、安装GraalVM 1、官网:https://www.graalvm.org/downloads/ 2、配置环境变量 2.1、环境变量必须使用JAVA_HOME,否则会出现问题 2.2、在系统变量配置Path,%JAVA_HOME%\bin,注意必须放在顶部第一位 2.3、配置jdk的环境变量,在P…...
【Amazon 实验②】使用缓存策略及源请求策略,用于控制边缘缓存的行为及回源行为
文章目录 1. 了解缓存策略和源请求策略1.1 使用缓存键和缓存策略 实验:使用CloudFront缓存策略和缓存键控制缓存行为 接上一篇文章【Amazon 实验①】使用 Amazon CloudFront加速Web内容分发,我们现在了解和配置如何使用缓存策略及源请求策略,…...
达梦数据对比工具的部署与使用
1、拷贝达梦软件bin目录到Oracle服务器(root用户) 压缩Linux rh6 x86版本的达梦数据库bin目录,例如压缩文件为dmbin.tar.gz,将文件拷贝到Oracle服务器指定目录并解压(如:/home/oracle/dmbin)&a…...
TLC2543(12位A/D转换器)实现将输入的模拟电压显示到数码管上
代码: #include <reg51.h> #define uchar unsigned char #define uint unsigned int// 数码管0-9 unsigned char seg[] {0x3F, 0x06, 0x5B, 0x4F, 0x66, 0x6D, 0x7D, 0x07, 0x7F, 0x6F}; sbit SDO P1^0; sbit SDI P1^1; sbit CS P1^2; sbit CLK P1^3; s…...
客服服务时长难统计?RPA自动记时长,排班更合理
RPA在客服服务时长统计中的应用客服服务时长的准确统计是优化排班和提高效率的关键。传统手动统计方式存在误差大、效率低等问题。RPA(机器人流程自动化)技术可以自动记录客服工作时长,为排班提供数据支持。RPA自动记录客服工作时长的实现方式…...
如何让微信聊天记录真正属于你:完整备份与分析终极指南
如何让微信聊天记录真正属于你:完整备份与分析终极指南 【免费下载链接】WeChatMsg 提取微信聊天记录,将其导出成HTML、Word、CSV文档永久保存,对聊天记录进行分析生成年度聊天报告 项目地址: https://gitcode.com/GitHub_Trending/we/WeCh…...
VuePress/Hexo博客作者必看:VSCode Paste Image插件路径配置避坑指南
VuePress/Hexo博客作者必看:VSCode Paste Image插件路径配置避坑指南 当你沉浸在VSCode中撰写技术博客时,是否遇到过这样的场景:本地预览时图片显示完美,但一旦部署到线上,所有图片都变成了令人沮丧的404错误ÿ…...
PFC3D模拟含纤维混凝土材料单轴压缩破坏
PFC3D含纤维混凝土材料单轴压缩破坏模拟去年在实验室折腾PFC3D模拟含纤维混凝土压缩破坏的时候,发现这玩意儿真是让人又爱又恨。纤维像调皮的孩子,在混凝土基体里各种"搞事情",今天就跟大家唠唠这个"微观破坏现场"的观察…...
流程可视化引擎定制指南:从技术实现到业务价值转化
流程可视化引擎定制指南:从技术实现到业务价值转化 【免费下载链接】Drawflow Simple flow library 🖥️🖱️ 项目地址: https://gitcode.com/gh_mirrors/dr/Drawflow 在数字化转型过程中,企业面临着业务流程可视化与实际业…...
Burp Suite实战进阶:用LingJing内置的burp-labs靶机打通从入门到专家22关(含解题思路)
Burp Suite实战进阶:用LingJing内置的burp-labs靶机打通从入门到专家22关(含解题思路) 在网络安全领域,Burp Suite无疑是渗透测试工程师最得力的工具之一。然而,很多学习者在掌握了基础操作后,往往会陷入&q…...
AI赋能React开发:让快马智能助手帮你设计和优化复杂组件逻辑
AI赋能React开发:让快马智能助手帮你设计和优化复杂组件逻辑 最近在开发一个电商网站时,遇到了一个常见的需求:实现一个侧边栏商品筛选组件。这个组件需要包含价格区间滑块、多品牌复选框和分类下拉选择三个主要功能。刚开始觉得这个需求挺简…...
打造手游PC级操控:QtScrcpy键鼠映射完全指南
打造手游PC级操控:QtScrcpy键鼠映射完全指南 【免费下载链接】QtScrcpy Android实时投屏软件,此应用程序提供USB(或通过TCP/IP)连接的Android设备的显示和控制。它不需要任何root访问权限 项目地址: https://gitcode.com/barry-ran/QtScrcpy 手机…...
嵌入式通信协议SPI/I2C/UART原理与应用
嵌入式通信协议原理图解与技术解析1. 串行通信协议基础1.1 SPI通信协议SPI(Serial Peripheral Interface)是一种全双工、同步串行通信协议,采用主从架构设计。其核心特点包括:四线制结构:SCLK(时钟)、MOSI(主出从入)、MISO(主入从出)、SS(片选…...
大模型应用指南:小白程序员必收藏,轻松入门AI前沿技术!
2025年大模型技术已在IT、金融、制造等领域广泛应用,从智能客服到数据分析,助力企业转型。沙丘智库《大模型应用跟踪月报》收录504个案例,揭示行业分布、应用场景及发展趋势。大模型不仅是技术突破,更是时代标志,小白程…...
