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

C语言中的贪心算法

贪心算法(Greedy Algorithm)是一种在每一步选择中都采取当前最优解的算法,希望通过局部最优解的选择,最终得到全局最优解。它常用于解决最优化问题,如最小生成树、最短路径等。本文将从理论到实践,逐步引导初学者掌握贪心算法在 C 语言中的实现。


什么是贪心算法?

贪心算法的核心是 贪心选择性质最优子结构

  1. 贪心选择性质:每次选择当前看起来最优的解。
  2. 最优子结构:问题的最优解可以通过子问题的最优解合并得到。

举个例子:假如你需要用最少的硬币找零,每次选择最大面值的硬币就是贪心的思路。


贪心算法的适用场景

贪心算法并不总是能找到全局最优解,适用场景包括:

  • 最小生成树问题(如 Prim、Kruskal 算法)
  • 活动选择问题
  • 最短路径问题(如 Dijkstra 算法,虽然不是纯贪心,但核心思想类似)

贪心算法的实现步骤

以下是实现贪心算法的通用步骤:

  1. 分析问题是否满足贪心选择性质和最优子结构
  2. 排序:根据特定规则对问题的元素进行排序(通常需要一个比较函数)。
  3. 逐步选择:从头开始,选择符合条件的元素,直到满足目标。
  4. 验证结果:确保结果满足问题的要求。

示例:活动选择问题

问题描述

给定一组活动,每个活动有一个开始时间和结束时间。你需要选择尽可能多的活动,且这些活动之间不能重叠。

贪心思路
  1. 按活动的结束时间升序排序(结束得越早,留给后续活动的时间越多)。
  2. 依次选择每个活动,如果它的开始时间不早于上一个已选活动的结束时间,则选择它。

C语言实现

以下是活动选择问题的 C 语言实现代码:

#include <stdio.h>
#include <stdlib.h>// 定义活动结构体
typedef struct {int start;int end;
} Activity;// 比较函数,用于按结束时间排序
int compare(const void *a, const void *b) {Activity *activity1 = (Activity *)a;Activity *activity2 = (Activity *)b;return activity1->end - activity2->end;
}// 贪心算法选择活动
void selectActivities(Activity activities[], int n) {// 按结束时间排序qsort(activities, n, sizeof(Activity), compare);printf("选择的活动如下:\n");int lastEndTime = 0;for (int i = 0; i < n; i++) {if (activities[i].start >= lastEndTime) {printf("活动[%d]: 开始时间 = %d, 结束时间 = %d\n", i + 1, activities[i].start, activities[i].end);lastEndTime = activities[i].end;}}
}int main() {Activity activities[] = {{1, 3},{2, 5},{4, 6},{6, 7},{5, 9},{8, 9}};int n = sizeof(activities) / sizeof(activities[0]);selectActivities(activities, n);return 0;
}

代码分析

  1. 数据结构:用 struct 定义活动的开始和结束时间。
  2. 排序:用 qsort 对活动按结束时间升序排列。
  3. 贪心选择:逐一遍历排序后的活动,如果活动的开始时间不与上一次选择的活动冲突,就将其加入结果。

输入输出示例

输入活动:

  • 活动1:开始时间=1,结束时间=3
  • 活动2:开始时间=2,结束时间=5
  • 活动3:开始时间=4,结束时间=6
  • 活动4:开始时间=6,结束时间=7
  • 活动5:开始时间=5,结束时间=9
  • 活动6:开始时间=8,结束时间=9

输出活动:

选择的活动如下:
活动[1]: 开始时间 = 1, 结束时间 = 3
活动[3]: 开始时间 = 4, 结束时间 = 6
活动[4]: 开始时间 = 6, 结束时间 = 7
活动[6]: 开始时间 = 8, 结束时间 = 9

总结

  1. 贪心算法的核心是找到局部最优解,逐步逼近全局最优解。
  2. 关键在于分析问题是否适合贪心策略,排序规则是实现的基础。
  3. 通过活动选择问题,初学者可以掌握贪心算法的基本思想。

尝试多练习一些经典的贪心问题,如背包问题、最短路径问题等,你会发现贪心算法是一种高效且优雅的解决问题方法!

相关文章:

C语言中的贪心算法

贪心算法&#xff08;Greedy Algorithm&#xff09;是一种在每一步选择中都采取当前最优解的算法&#xff0c;希望通过局部最优解的选择&#xff0c;最终得到全局最优解。它常用于解决最优化问题&#xff0c;如最小生成树、最短路径等。本文将从理论到实践&#xff0c;逐步引导…...

虚幻引擎结构之UWorld

Uworld -> Ulevel ->Actors -> AActor 在虚幻引擎中&#xff0c;UWorld 类扮演着至关重要的角色&#xff0c;它就像是游戏世界的总指挥。作为游戏世界的核心容器&#xff0c;UWorld 包含了构成游戏体验的众多元素&#xff0c;从游戏实体到关卡设计&#xff0c;再到物…...

太通透了,Android 流程分析 蓝牙enable流程(stack/hidl)

零. 前言 由于Bluedroid的介绍文档有限,以及对Android的一些基本的知识需要了(Android 四大组件/AIDL/Framework/Binder机制/JNI/HIDL等),加上需要掌握的语言包括Java/C/C++等,加上网络上其实没有一个完整的介绍Bluedroid系列的文档,所以不管是蓝牙初学者还是蓝牙从业人员…...

2.微服务灰度发布落地实践(agent实现)

前言 据上一篇&#xff0c;设计方案的分析&#xff0c;综合考虑&#xff0c;最终决定,客户端采用agent方案实现&#xff0c;具本原因不再赘述&#xff0c; 感觉兴趣的小伙伴可以回头了解一下.该篇主要讲java agent的实现,灰度agent客户端的基础框架实现 java agent的介绍 ja…...

搭建医疗客服知识库:智慧医疗的基石

在医疗行业&#xff0c;客服知识库不仅是提供患者咨询和支持的平台&#xff0c;更是提升医疗服务效率和质量的关键工具。 1. 明确知识库的目标和价值 构建医疗行业客服知识库的首要任务是明确其目标和价值。这包括提供患者教育、辅助临床决策、优化患者服务流程等。明确目标后…...

CES Asia 2025的低空经济展区有哪些亮点?

CES Asia 2025&#xff08;赛逸展&#xff09;的低空经济展区有以下亮点&#xff1a; • 前沿科技产品展示&#xff1a; 多款新型无人机将亮相&#xff0c;如固定翼无人机和系留无人机的最新型号&#xff0c;其在监测、救援和货物运输等方面功能强大。此外&#xff0c;还有可能…...

Java/Spring项目包名为何以“com”开头?

文章目录 包名的基本概念域名反转规则历史背景包名的结构实际应用总结 在Java和Spring项目中&#xff0c;我们常常看到包名以“com”开头&#xff0c;比如com.example.project。这种命名方式看似简单&#xff0c;其实背后蕴含着不少学问。今天&#xff0c;我们就来聊聊这个话题…...

影刀进阶应用 | 知乎发布想法

文章目录 影刀进阶应用 | 知乎发布想法一、流程流程解释&#xff1a; 二、单条想法发布2.1 素材生产2.2 **进入发布流程**2.3 **输入文本**2.4 插入图片2.5 发布查看 三、批量发布 影刀进阶应用 | 知乎发布想法 一、流程 流程解释&#xff1a; 素材生产 &#xff1a;用AI生成待…...

v-if 和 v-for 优先级

一、优先级规则 在 Vue.js 中&#xff0c;v-for的优先级比v-if高。这意味着当它们同时出现在一个元素上时&#xff0c;v-for会首先被解析和执行。 <div v-for"item in items" v-if"shouldShow(item)">{{ item }}</div> 二、可能导致的问题 …...

【数据结构与算法】单向链表

一、什么是链表 链表由一系列节点组成&#xff0c;每个节点都包含一个 data 域&#xff08;存放数据&#xff09;和一个 next 域&#xff08;指向下一节点&#xff09;。链表中的节点可以按照任意顺序存放在内存中&#xff0c;它们之间并不连续。每个节点都记录了下一个节点的地…...

网络编程UDP—socket实现(C++)

网络编程UDP—socket实现 前言UDP客户端和服务端UDP使用场景UDP socket C代码示例服务端接收数据示例&#xff08;bindrecvfrom 阻塞式接收信息&#xff09;&#xff1a;bind 绑定-监听 函数为什么一般都是监听所有网络接口呢&#xff1f;为什么需要用inet_addr进行转换&#x…...

系统思考—冰山模型

“卓越不是因机遇而生&#xff0c;而是智慧的选择与用心的承诺。”—— 亚里士多德 卓越&#xff0c;从来不是一次性行为&#xff0c;而是一种习惯。正如我们在日常辅导中常提醒自己&#xff1a;行为的背后&#xff0c;隐藏着选择的逻辑&#xff0c;而选择的根源&#xff0c;源…...

MySQL 中存储金额数据一般使用什么数据类型

在 MySQL 中存储金额数据时&#xff0c;应该谨慎选择数据类型&#xff0c;以确保数据的精度和安全性。以下是几种常用的数据类型及其适用性&#xff1a; DECIMAL 类型&#xff1a; 描述&#xff1a;DECIMAL 类型是专门为存储精确的小数而设计的。它可以指定小数点前后的数字位数…...

Excel中一次查询返回多列

使用Excel或wps的时候&#xff0c;有时候需要一次查询返回多列内容&#xff0c;这种情况可以选择多次vlookup或者多次xlookup&#xff0c;但是这种做法费时费力不说&#xff0c;效率还有些低下&#xff0c;特别是要查询的列数过多时。我放了3种查询方法&#xff0c;效果图&…...

Java中各种数组复制方式的效率对比

在 Java 中&#xff0c;数组复制是一个常见的操作&#xff0c;尤其是在处理动态数组&#xff08;如 ArrayList&#xff09;时。Java 提供了多种数组复制的方式&#xff0c;每种方式在性能和使用场景上都有所不同。以下是对几种主要数组复制方式的比较&#xff0c;包括 System.a…...

STM32 FLASHdb

FlashDB是一款超轻量级的嵌入式数据库&#xff0c;专注于为嵌入式产品提供数据存储方案。以下是对STM32 FlashDB的详细介绍&#xff1a; 一、主要特性 资源占用极低&#xff1a;FlashDB的内存占用几乎为0&#xff0c;非常适合资源有限的嵌入式系统。支持多分区、多实例&#…...

【漏洞复现】Struts2(CVE-2024-53677)任意文件上传逻辑绕过漏洞

文章目录 前言一、漏洞描述二、漏洞详情三、影响版本四、危害描述五、漏洞分析六、漏洞复现七、修复建议前言 Struts2框架是一个用于开发Java EE网络应用程序的开放源代码网页应用程序架构。它利用并延伸了Java Servlet API,鼓励开发者采用MVC架构。Struts2以WebWork优秀的设…...

图的最短路径(C++实现图【4】)

目录 1. 最短路径 1.1单源最短路径--Dijkstra算法 代码实现 1.2 单源最短路径--Bellman-Ford算法 代码实现 1.3 多源最短路径--Floyd-Warshall算法 代码实现 1. 最短路径 最短路径问题&#xff1a;从在带权有向图G中的某一顶点出发&#xff0c;找出一条通往另一顶点的最短路径&…...

Pandas01

文章目录 内容简介1 常用数据分析三方库2 Jupyter notebook3 Series的创建3.1 通过Numpy的Ndarray 创建一个Series3.2 通过列表创建Series 4 Series的属性和方法4.1 常用属性4.2 常用方法4.3 布尔值列表筛选部分数据4.4 Series 的运算 5 DataFrame的创建通过字典创建通过列表[元…...

opencl 封装简单api

这是cl代码 kernel.c __kernel void add_one(__global float *output,__global float* pnum) {int xget_global_id(0);output[x]pnum[0]; } c代码 #include <CL/cl.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include<st…...

元素偏析系数计算:从概念到实际应用

元素偏析系数计算(Pandat代算或自己操作) 实例32: 偏析系数k是指在熔体凝固过程中&#xff0c;溶质元素在固相和液相中浓度的比值。 通过计算偏析系数&#xff0c;可以预测在凝固过程中某一溶质元素的分布情况&#xff0c;从而帮助设计合金的微观组织结构。 偏析系数 k1 则倾向…...

全学科适用AI写作辅助网站排行榜(2026 实测推荐)

基于功能完整性、学术适配性、用户反馈及操作便捷性&#xff0c;以下是当前主流AI论文写作工具的实测排名&#xff0c;按综合使用价值从高到低依次呈现&#xff0c;并附上各平台的核心优势与适用人群。&#x1f3c6; 第一梯队&#xff1a;全流程学术解决方案&#xff08;★★★…...

手把手教你用Llama-3.2V-11B-cot:像聊天一样轻松实现图片智能分析

手把手教你用Llama-3.2V-11B-cot&#xff1a;像聊天一样轻松实现图片智能分析 1. 引言&#xff1a;当视觉大模型遇上聊天式交互 想象一下&#xff0c;你正面对一张复杂的医学影像或工程图纸&#xff0c;需要快速理解其中的关键信息。传统方法可能需要专业培训或反复查阅资料&…...

保姆级教程:用BERT微调一个智能家居语音助手的意图识别模型(含完整代码)

智能家居场景下的BERT意图识别实战&#xff1a;从数据标注到模型部署 想象一下&#xff0c;当你对家里的智能音箱说"把客厅灯调暗一点"时&#xff0c;设备能准确理解你的意图并执行操作。这种自然交互的背后&#xff0c;是意图识别技术在发挥作用。不同于通用对话系…...

告别“瞎测”:如何用Tessent ATPG生成高效测试向量(Pattern)提升芯片良率

芯片测试效率革命&#xff1a;Tessent ATPG实战指南与良率提升策略 在半导体行业&#xff0c;每一纳秒的测试时间缩减都可能转化为数百万美元的成本节约。当芯片设计进入7nm以下工艺节点时&#xff0c;制造缺陷导致的良率问题愈发突出&#xff0c;传统测试方法已无法满足现代芯…...

YOLOv12镜像实战:工业质检场景下的高精度缺陷识别方案

YOLOv12镜像实战&#xff1a;工业质检场景下的高精度缺陷识别方案 1. 工业质检的挑战与YOLOv12的机遇 在制造业数字化转型浪潮中&#xff0c;工业质检一直是自动化程度较低的环节。传统人工检测面临三大痛点&#xff1a; 效率瓶颈&#xff1a;熟练质检员每分钟最多检测20-30…...

Android设备性能优化:Universal Android Debloater的技术实现与应用指南

Android设备性能优化&#xff1a;Universal Android Debloater的技术实现与应用指南 【免费下载链接】universal-android-debloater Cross-platform GUI written in Rust using ADB to debloat non-rooted android devices. Improve your privacy, the security and battery li…...

SenseVoiceSmall实战案例:如何用AI分析会议录音中的情绪变化

SenseVoiceSmall实战案例&#xff1a;如何用AI分析会议录音中的情绪变化 1. 会议录音分析的痛点与解决方案 在日常工作中&#xff0c;会议录音分析一直是个耗时费力的任务。传统方法需要人工反复听取录音&#xff0c;不仅效率低下&#xff0c;还容易遗漏关键信息。特别是会议…...

告别驱动芯片!手把手教你用FPGA直接驱动RGB888/565屏幕(附Verilog代码)

FPGA直接驱动RGB屏幕&#xff1a;摆脱专用芯片的高效设计指南 在嵌入式系统开发中&#xff0c;显示模块往往是不可或缺的部分。传统方案通常依赖专用驱动芯片如SSD1963或RA8875来连接处理器与RGB屏幕&#xff0c;但这种架构正面临FPGA技术带来的革新。本文将揭示如何利用FPGA的…...

C#实战:5分钟搞定Modbus RTU通讯(基于NModbus4库)

C#实战&#xff1a;5分钟搞定Modbus RTU通讯&#xff08;基于NModbus4库&#xff09; 工业自动化领域的数据采集离不开设备通讯协议的支持&#xff0c;而Modbus RTU作为最广泛应用的串行通信协议之一&#xff0c;几乎成为工控开发者的必修课。今天我们就用C#和NModbus4库&#…...