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

计算机算法贪心算法

贪心算法(Greedy Algorithm)是一种常见的算法思想,它在每一步选择当前状态下最优的解决方案,从而希望最终能够达到全局最优解。

贪心算法的基本思路是每一步都选择当前状态下的局部最优解,而忽略了当前选择所带来的影响,因此并不一定能够得到全局最优解。然而,在某些问题上,贪心算法确实能够得到最优解,而且贪心算法通常具有较高的执行效率。

经典的贪心算法问题包括:

  1. 钱币找零:给定若干面额不同的硬币,找零时使用最少的硬币数目。
  2. 区间调度:给定若干活动的开始时间和结束时间,安排活动使得参与的活动数最大。
  3. 最小生成树:在一个连通加权图中找到一棵包含全部顶点且边的权值之和最小的生成树。

贪心算法在解决一些最优化问题时特别有用,但是并不适用于所有类型的问题。因此,在使用贪心算法时,需要仔细分析问题的特性,以确定是否适合采用贪心策略。

如您有关于贪心算法的具体问题或需求,欢迎随时与我交流讨论。

#include <stdio.h>
#include <limits.h>#define V 5  // 图中顶点的数量int minKey(int key[], bool mstSet[]) {int min = INT_MAX, min_index;for (int v = 0; v < V; v++)if (mstSet[v] == false && key[v] < min)min = key[v], min_index = v;return min_index;
}void printMST(int parent[], int n, int graph[V][V]) {printf("Edge \tWeight\n");for (int i = 1; i < V; i++)printf("%d - %d \t%d \n", parent[i], i, graph[i][parent[i]]);
}void primMST(int graph[V][V]) {int parent[V]; // 存储构造MST的结果int key[V];   // 存储键值用于选择在MST中包含的点bool mstSet[V];  // 用于表示MST中的顶点集合for (int i = 0; i < V; i++)key[i] = INT_MAX, mstSet[i] = false;key[0] = 0;   parent[0] = -1;  // 第一个顶点总是MST的根节点for (int count = 0; count < V-1; count++) {int u = minKey(key, mstSet);mstSet[u] = true;for (int v = 0; v < V; v++)if (graph[u][v] && mstSet[v] == false && graph[u][v] < key[v])parent[v] = u, key[v] = graph[u][v];}printMST(parent, V, graph);
}int main() {int graph[V][V] = {{0, 2, 0, 6, 0},{2, 0, 3, 8, 5},{0, 3, 0, 0, 7},{6, 8, 0, 0, 9},{0, 5, 7, 9, 0}};primMST(graph);return 0;
}

相关文章:

计算机算法贪心算法

贪心算法&#xff08;Greedy Algorithm&#xff09;是一种常见的算法思想&#xff0c;它在每一步选择当前状态下最优的解决方案&#xff0c;从而希望最终能够达到全局最优解。 贪心算法的基本思路是每一步都选择当前状态下的局部最优解&#xff0c;而忽略了当前选择所带来的影…...

基于css实现动画效果

介绍 本文将会基于css&#xff0c;实现各种动画效果&#xff0c;接下来会从简单几个例子入手。 案例 三颗球 <!DOCTYPE html> <html lang"en"><head><meta charset"utf-8" /><title>React App</title><style>…...

18.将文件上传至云服务器 + 优化网站的性能

目录 1.将文件上传至云服务器 1.1 处理上传头像逻辑 1.1.1 客户端上传 1.1.2 服务器直传 2.优化网站的性能 2.1 本地缓存优化查询方法 2.2 压力测试 1.将文件上传至云服务器 客户端上传&#xff1a;客户端将数据提交给云服务器&#xff0c;并等待其响应&#xff1b;用户…...

Linux: module: kheaders;CONFIG_IKHEADERS

文章目录 参考错误开一个玩笑。configcommit参考 https://github.com/iovisor/bcc/pull/2312 https://github.com/iovisor/bcc/pull/3588 https://bugs.gentoo.org/809347 https://lore.kernel.org/lkml/20190408212855.233198-1-joel@joelfernandes.org/ 错误 <built-in…...

Page 251~254 Win32 GUI项目

win32_gui 源代码&#xff1a; #if defined(UNICODE) && !defined(_UNICODE)#define _UNICODE #elif defined(_UNICODE) && !defined(UNICODE)#define UNICODE #endif#include <tchar.h> #include <windows.h>/* Declare Windows procedure */…...

Kafka(七)可靠性

目录 1 可靠的数据传递1.1 Kafka的可靠性保证1.2 复制1.3 Broker配置1.3.1 复制系数1.3.2 broker的位置分布1.3.3 不彻底的首领选举1.3.4 最少同步副本1.3.5 保持副本同步1.3.6 持久化到磁盘flush.messages9223372036854775807flush.ms9223372036854775807 1.2 在可靠的系统中使…...

Spring Data JPA入门到放弃

参考文档&#xff1a;SpringData JPA&#xff1a;一文带你搞懂 - 知乎 (zhihu.com) 一、 前言 1.1 概述 Java持久化技术是Java开发中的重要组成部分&#xff0c;它主要用于将对象数据持久化到数据库中&#xff0c;以及从数据库中查询和恢复对象数据。在Java持久化技术领域&a…...

MES系统数据采集的几种方式

生产制造执行MES系统具有能够帮助企业实现生产数据收集与分析、生产计划管理、生产过程监控等的功能板块&#xff0c;在这里小编就不一一介绍了&#xff0c;主要讲讲它的数据采集功能板块&#xff0c;可以说&#xff0c;数据采集是该系统进行数据统计与生产管理等后续工作的基础…...

铭文 LaunchPad 平台 Solmash 推出早鸟激励计划

为感谢用户对Solmash的支持&#xff0c;Solmash 特别推出“Solmash早鸟激励计划”&#xff0c;以回馈社区的早期参与者&#xff0c;这是专为已经参与Staking Pool或Honest Pool的用户推出的激励。 Solmash NFT激励 被列入早鸟计划的用户&#xff0c;可通过点击&#xff1a;sol…...

【前端规范】

1 前言 HTML 作为描述网页结构的超文本标记语言&#xff0c;一直有着广泛的应用。本文档的目标是使 HTML 代码风格保持一致&#xff0c;容易被理解和被维护。 2 代码风格 2.1 缩进与换行 [强制] 使用 4 个空格做为一个缩进层级&#xff0c;不允许使用 2 个空格 或 tab 字符…...

12、JVM高频面试题

1、JVM的主要组成部分有哪些 JVM主要分为下面几部分 类加载器&#xff1a;负责将字节码文件加载到内存中 运行时数据区&#xff1a;用于保存java程序运行过程中需要用到的数据和相关信息 执行引擎&#xff1a;字节码文件并不能直接交给底层操作系统去执行&#xff0c;因此需要…...

【Docker】Docker安装入门教程及基本使用

&#x1f389;&#x1f389;欢迎来到我的CSDN主页&#xff01;&#x1f389;&#x1f389; &#x1f3c5;我是Java方文山&#xff0c;一个在CSDN分享笔记的博主。&#x1f4da;&#x1f4da; &#x1f31f;推荐给大家我的专栏《Docker实战》。&#x1f3af;&#x1f3af; &…...

语义解析:如何基于SQL去实现自然语言与机器智能连接的桥梁

&#x1f308;个人主页: Aileen_0v0 &#x1f525;热门专栏: 华为鸿蒙系统学习|计算机网络|数据结构与算法 &#x1f4ab;个人格言:"没有罗马,那就自己创造罗马~" 目录 语义解析 定义 作用 语义解析的应用场景 场景一&#xff1a; 场景二&#xff1a; 总结语…...

Java项目:117SpringBoot动漫论坛网站

博主主页&#xff1a;Java旅途 简介&#xff1a;分享计算机知识、学习路线、系统源码及教程 文末获取源码 117SpringBoot动漫论坛网站 一、项目介绍 动漫论坛网站是由SpringBootMybatis开发的&#xff0c;旅游网站分为前台和后台&#xff0c;前台为用户浏览&#xff0c;后台进…...

Jenkins基础篇--添加节点

节点介绍 Jenkins 拥有分布式构建(在 Jenkins 的配置中叫做节点)&#xff0c;分布式构建能够让同一套代码在不同的环境(如&#xff1a;Windows 和 Linux 系统)中编译、测试等。 Jenkins 运行的主机在逻辑上是 master 节点&#xff0c;下图是主节点和从节点的关系。 添加节点 …...

【C++】手撕 list类(包含迭代器)

目录 1&#xff0c;list的介绍及使用 2&#xff0c;list_node 3&#xff0c;list_node() 3&#xff0c;list 4&#xff0c;list() 5&#xff0c;push_back(const T& x) 6&#xff0c;print() 7&#xff0c;_list_iterator 8&#xff0c;operator*() 9&#xff0c…...

@Autowired 和 @Resource 的区别是什么?

Java面试题目录 Autowired 和 Resource 的区别是什么&#xff1f; Autowired 是 Spring 提供的注解。默认的注入方式为byType&#xff08;根据类型进行匹配&#xff09;。 Resource 是 JDK 提供的注解。默认注入方式为 byName&#xff08;根据名称进行匹配&#xff09;。 当一…...

栈和排序.

给你一个1->n的排列和一个栈&#xff0c;入栈顺序给定 你要在不打乱入栈顺序的情况下&#xff0c;对数组进行从大到小排序 当无法完全排序时&#xff0c;请输出字典序最大的出栈序列 输入 第一行一个数n 第二行n个数&#xff0c;表示入栈的顺序&#xff0c;用空格隔开&…...

springboot 多数据源怎么配置在控制台的sql打印日志

程序员的公众号&#xff1a;源1024&#xff0c;获取更多资料&#xff0c;无加密无套路&#xff01; 最近整理了一波电子书籍资料&#xff0c;包含《Effective Java中文版 第2版》《深入JAVA虚拟机》&#xff0c;《重构改善既有代码设计》&#xff0c;《MySQL高性能-第3版》&…...

【WinForms 窗体】常见的“陷阱”

当涉及到 WinForms 窗体编程时&#xff0c;我们可能会遇到一些常见的问题。在本篇博客中&#xff0c;我将为你提供一些常见问题的解决方案。 跨线程访问控件 在 WinForms 中&#xff0c;当在非UI线程上执行操作并尝试访问 UI 控件时&#xff0c;会引发跨线程访问异常。为了解决…...

在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module

1、为什么要修改 CONNECT 报文&#xff1f; 多租户隔离&#xff1a;自动为接入设备追加租户前缀&#xff0c;后端按 ClientID 拆分队列。零代码鉴权&#xff1a;将入站用户名替换为 OAuth Access-Token&#xff0c;后端 Broker 统一校验。灰度发布&#xff1a;根据 IP/地理位写…...

GC1808高性能24位立体声音频ADC芯片解析

1. 芯片概述 GC1808是一款24位立体声音频模数转换器&#xff08;ADC&#xff09;&#xff0c;支持8kHz~96kHz采样率&#xff0c;集成Δ-Σ调制器、数字抗混叠滤波器和高通滤波器&#xff0c;适用于高保真音频采集场景。 2. 核心特性 高精度&#xff1a;24位分辨率&#xff0c…...

USB Over IP专用硬件的5个特点

USB over IP技术通过将USB协议数据封装在标准TCP/IP网络数据包中&#xff0c;从根本上改变了USB连接。这允许客户端通过局域网或广域网远程访问和控制物理连接到服务器的USB设备&#xff08;如专用硬件设备&#xff09;&#xff0c;从而消除了直接物理连接的需要。USB over IP的…...

免费PDF转图片工具

免费PDF转图片工具 一款简单易用的PDF转图片工具&#xff0c;可以将PDF文件快速转换为高质量PNG图片。无需安装复杂的软件&#xff0c;也不需要在线上传文件&#xff0c;保护您的隐私。 工具截图 主要特点 &#x1f680; 快速转换&#xff1a;本地转换&#xff0c;无需等待上…...

Leetcode33( 搜索旋转排序数组)

题目表述 整数数组 nums 按升序排列&#xff0c;数组中的值 互不相同 。 在传递给函数之前&#xff0c;nums 在预先未知的某个下标 k&#xff08;0 < k < nums.length&#xff09;上进行了 旋转&#xff0c;使数组变为 [nums[k], nums[k1], …, nums[n-1], nums[0], nu…...

LCTF液晶可调谐滤波器在多光谱相机捕捉无人机目标检测中的作用

中达瑞和自2005年成立以来&#xff0c;一直在光谱成像领域深度钻研和发展&#xff0c;始终致力于研发高性能、高可靠性的光谱成像相机&#xff0c;为科研院校提供更优的产品和服务。在《低空背景下无人机目标的光谱特征研究及目标检测应用》这篇论文中提到中达瑞和 LCTF 作为多…...

HTML前端开发:JavaScript 获取元素方法详解

作为前端开发者&#xff0c;高效获取 DOM 元素是必备技能。以下是 JS 中核心的获取元素方法&#xff0c;分为两大系列&#xff1a; 一、getElementBy... 系列 传统方法&#xff0c;直接通过 DOM 接口访问&#xff0c;返回动态集合&#xff08;元素变化会实时更新&#xff09;。…...

SQL Server 触发器调用存储过程实现发送 HTTP 请求

文章目录 需求分析解决第 1 步:前置条件,启用 OLE 自动化方式 1:使用 SQL 实现启用 OLE 自动化方式 2:Sql Server 2005启动OLE自动化方式 3:Sql Server 2008启动OLE自动化第 2 步:创建存储过程第 3 步:创建触发器扩展 - 如何调试?第 1 步:登录 SQL Server 2008第 2 步…...

vue3 daterange正则踩坑

<el-form-item label"空置时间" prop"vacantTime"> <el-date-picker v-model"form.vacantTime" type"daterange" start-placeholder"开始日期" end-placeholder"结束日期" clearable :editable"fal…...

Modbus RTU与Modbus TCP详解指南

目录 1. Modbus协议基础 1.1 什么是Modbus? 1.2 Modbus协议历史 1.3 Modbus协议族 1.4 Modbus通信模型 🎭 主从架构 🔄 请求响应模式 2. Modbus RTU详解 2.1 RTU是什么? 2.2 RTU物理层 🔌 连接方式 ⚡ 通信参数 2.3 RTU数据帧格式 📦 帧结构详解 🔍…...