高级算法设计与分析(四) -- 贪心算法
系列文章目录
高级算法设计与分析(一) -- 算法引论
高级算法设计与分析(二) -- 递归与分治策略
高级算法设计与分析(三) -- 动态规划
高级算法设计与分析(四) -- 贪心算法
高级算法设计与分析(五) -- 回溯法
高级算法设计与分析(六) -- 分支限界法
高级算法设计与分析(七) -- 概率算法和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…...
深度学习驱动的图像去雾:2023年最新算法与应用实践
1. 图像去雾技术的现状与挑战 清晨打开窗户,如果外面雾气弥漫,我们往往会等雾散了再拍照。但计算机视觉系统可没这个耐心——自动驾驶汽车必须实时看清路况,无人机巡检得在雾天正常工作。这就是图像去雾技术存在的意义。2023年,随…...
财务效率革命:printPDF免费电子发票批量打印工具深度解析
在当今数字化办公的时代背景下,财务、报销、税务等岗位的日常工作中,电子发票处理已成为不可忽视的重要环节。每月数百甚至上千张的电子发票,一张张手动打开、设置、打印的传统操作模式,不仅耗时耗力,效率低下…...
2026年上海网站建设市场分析:企业官网从展示到增长的演进路径
2026年,上海企业数字化服务市场迎来结构性变革。据2026年上半年上海企业数字化服务市场调研数据显示,上海地区企业官网新建与升级需求同比增长45%,中大型企业对官网的核心诉求已从基础信息展示转向AI智能赋能、全球化跨境适配、全链路营销转化…...
OpenClaw 超级 AI 实战专栏【补充内容】AI开发实操:减少Token用量、提升模型效率的8个核心技巧(附代码)
目录 一、核心前提:理解Token消耗的关键场景 二、6种优化方案(附案例+代码) 方案1:精简Prompt(最易落地,立竿见影) 核心思路 应用案例 代码实现 方案2:上下文窗口裁剪(避免历史信息冗余) 核心思路 应用案例 代码实现 方案3:输入文本摘要压缩(批量处理场景…...
突破性SLAM实战:如何用SLAM Toolbox彻底改变机器人定位与建图工作流
突破性SLAM实战:如何用SLAM Toolbox彻底改变机器人定位与建图工作流 【免费下载链接】slam_toolbox Slam Toolbox for lifelong mapping and localization in potentially massive maps with ROS 项目地址: https://gitcode.com/gh_mirrors/sl/slam_toolbox …...
Qwen3-TTS-VoiceDesign实战案例:用‘撒娇稚嫩萝莉声’描述生成高拟真TTS音频
Qwen3-TTS-VoiceDesign实战案例:用‘撒娇稚嫩萝莉声’描述生成高拟真TTS音频 1. 项目概述与核心价值 Qwen3-TTS-VoiceDesign是一个让人惊艳的语音合成模型,它最大的特点就是能用简单的文字描述,生成你想要的任何声音风格。想象一下…...
避免Java Stream重复消费:高效过滤Map的策略
本文旨在解决Java Stream在多过滤场景中常见的IllegalStatexception,即流被重复消耗的问题。我们将深入讨论Java Stream的单次使用特性,通过将外部过滤条件转换为集合,优化Map的过滤操作,提供高效、符合最佳实践的解决方案&#x…...
Pixel Fashion Atelier实战教程:从零构建像素时装生成API服务
Pixel Fashion Atelier实战教程:从零构建像素时装生成API服务 1. 项目介绍与核心价值 Pixel Fashion Atelier(像素时装锻造坊)是一款专为时尚设计师和像素艺术爱好者打造的AI图像生成工具。它基于Stable Diffusion和Anything-v5模型&#x…...
Vision-Agents插件开发完全指南:构建你的第一个AI集成
Vision-Agents插件开发完全指南:构建你的第一个AI集成 【免费下载链接】Vision-Agents Open Vision Agents by Stream. Build Vision Agents quickly with any model or video provider. Uses Streams edge network for ultra-low latency. 项目地址: https://git…...
35:L构建数据泄露检测:蓝队的数据保护
作者: HOS(安全风信子) 日期: 2026-03-11 主要来源平台: GitHub 摘要: 当基拉开始针对数据进行攻击时,数据泄露成为蓝队防御的关键挑战。L构建了数据泄露检测系统,通过AI算法分析数据流动、访问模式和异常行…...
