高级算法设计与分析(四) -- 贪心算法
系列文章目录
高级算法设计与分析(一) -- 算法引论
高级算法设计与分析(二) -- 递归与分治策略
高级算法设计与分析(三) -- 动态规划
高级算法设计与分析(四) -- 贪心算法
高级算法设计与分析(五) -- 回溯法
高级算法设计与分析(六) -- 分支限界法
高级算法设计与分析(七) -- 概率算法和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…...
(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)
题目:3442. 奇偶频次间的最大差值 I 思路 :哈希,时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况,哈希表这里用数组即可实现。 C版本: class Solution { public:int maxDifference(string s) {int a[26]…...
Vue记事本应用实现教程
文章目录 1. 项目介绍2. 开发环境准备3. 设计应用界面4. 创建Vue实例和数据模型5. 实现记事本功能5.1 添加新记事项5.2 删除记事项5.3 清空所有记事 6. 添加样式7. 功能扩展:显示创建时间8. 功能扩展:记事项搜索9. 完整代码10. Vue知识点解析10.1 数据绑…...
汽车生产虚拟实训中的技能提升与生产优化
在制造业蓬勃发展的大背景下,虚拟教学实训宛如一颗璀璨的新星,正发挥着不可或缺且日益凸显的关键作用,源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例,汽车生产线上各类…...
STM32标准库-DMA直接存储器存取
文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA(Direct Memory Access)直接存储器存取 DMA可以提供外设…...
基础测试工具使用经验
背景 vtune,perf, nsight system等基础测试工具,都是用过的,但是没有记录,都逐渐忘了。所以写这篇博客总结记录一下,只要以后发现新的用法,就记得来编辑补充一下 perf 比较基础的用法: 先改这…...
MODBUS TCP转CANopen 技术赋能高效协同作业
在现代工业自动化领域,MODBUS TCP和CANopen两种通讯协议因其稳定性和高效性被广泛应用于各种设备和系统中。而随着科技的不断进步,这两种通讯协议也正在被逐步融合,形成了一种新型的通讯方式——开疆智能MODBUS TCP转CANopen网关KJ-TCPC-CANP…...
论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)
笔记整理:刘治强,浙江大学硕士生,研究方向为知识图谱表示学习,大语言模型 论文链接:http://arxiv.org/abs/2407.16127 发表会议:ISWC 2024 1. 动机 传统的知识图谱补全(KGC)模型通过…...
深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南
🚀 C extern 关键字深度解析:跨文件编程的终极指南 📅 更新时间:2025年6月5日 🏷️ 标签:C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言🔥一、extern 是什么?&…...
JVM暂停(Stop-The-World,STW)的原因分类及对应排查方案
JVM暂停(Stop-The-World,STW)的完整原因分类及对应排查方案,结合JVM运行机制和常见故障场景整理而成: 一、GC相关暂停 1. 安全点(Safepoint)阻塞 现象:JVM暂停但无GC日志,日志显示No GCs detected。原因:JVM等待所有线程进入安全点(如…...
laravel8+vue3.0+element-plus搭建方法
创建 laravel8 项目 composer create-project --prefer-dist laravel/laravel laravel8 8.* 安装 laravel/ui composer require laravel/ui 修改 package.json 文件 "devDependencies": {"vue/compiler-sfc": "^3.0.7","axios": …...
