当前位置: 首页 > 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;逐步引导…...

使用envoyfilter添加请求头

该envoyfilter实现了这样一个功能&#xff0c;如果请求头中含有Sw8&#xff0c;则添加请求头HasSw8: true。 1. 内嵌lua脚本 apiVersion: networking.istio.io/v1alpha3 kind: EnvoyFilter metadata:name: add-header-filternamespace: demo-bookinfo # 可根据实际情况调整命…...

【机器学习】回归

文章目录 1. 如何训练回归问题2. 泛化能力3. 误差来源4. 正则化5. 交叉验证 1. 如何训练回归问题 第一步&#xff1a;定义模型 线性模型&#xff1a; y ^ b ∑ j w j x j \hat{y} b \sum_{j} w_j x_j y^​b∑j​wj​xj​ 其中&#xff0c;( w ) 是权重&#xff0c;( b )…...

Elasticsearch名词解释

文章目录 1.什么是Elasticsearch?2.什么是elastic stack(ELK)?3.什么是Lucene?4.什么是文档(document)&#xff1f;5.什么是词条(term)&#xff1f;6.什么是正向索引&#xff1f;7.什么是倒排索引&#xff1f;8.ES中的索引(index)9.映射(Mapping)10.DSL11.elastcisearch与my…...

把Huggingface下载的arrow数据集转化为json格式

Arrow2json 使用默认的Huggingface路径 以allenai/tulu-3-sft-mixture数据集为例。 使用load_dataset即可&#xff1a; from datasets import load_dataset# 加载数据集 dataset load_dataset("allenai/tulu-3-sft-mixture")# 指定保存路径 output_dir "~/…...

手机联系人 查询 添加操作

Android——添加联系人_android 添加联系人-CSDN博客 上面连接添加联系人已测试 是可以 Android : 获取、添加、手机联系人-ContentResolver简单应用_contentresolver 添加联系人-CSDN博客...

kkFileView集成springboot:使用自定义预览接口(非minio预览接口),发现无法预览资源

目录 1、背景2、原因分析3、解决办法 1、背景 按照项目验收要求&#xff0c;需要对minio中存储的数据进行加密 之前提供给kkFileView的预览地址都是获取的minio预览地址 由于minio中的资源进行了加密处理&#xff0c;所以我们自定义预览接口&#xff08;进行解密操作&#xff…...

C++ 设计模式:观察者模式(Observer Pattern)

链接&#xff1a;C 设计模式 链接&#xff1a;C 设计模式 - 模板方法 链接&#xff1a;C 设计模式 - 策略模式 观察者模式&#xff08;Observer Pattern&#xff09;是一种行为设计模式&#xff0c;它定义了一种一对多的依赖关系&#xff0c;让多个观察者对象同时监听某一个主…...

Mono 和 IL2Cpp的区别

Mono特征: 标准项目中有Assembly-CSharp.dll , 但在更复杂的项目或特定配置中,可能会有其他.dll或结构变更 在游戏的数据目录下看到一系列的.dll文件,这些文件的语言一般为中间语言 CE附加 , 查看是否有Mono.dll相关模块 目录有MonoBleedingEdge文件夹 IL2Cpp 标准项目应该…...

Windows平台ROBOT安装

Windows环境下ROBOT的安装,按照下文进行部署ROBOT的前提是你的python已安装并且环境变量已设置好. 一、安装setuptools 1、下载后安装 https://pypi.python.org/pypi/setuptools/ 下载你需要的包 setuptools-75.6.0.tar.gz 解压下载的包在命令行中进入该包,敲击如下命令后…...

DevOps实战:用Kubernetes和Argo打造自动化CI/CD流程(2)

DevOps实战&#xff1a;用Kubernetes和Argo打造自动化CI/CD流程&#xff08;2&#xff09; 背景 Tips 翻遍国内外的文档&#xff0c;关于 Argo 作为 CI/CD 当前所有开源的文档&#xff0c;博客&#xff0c;argo官方文档。得出的结论是&#xff1a; argo官方给出的例子都相对…...

深入浅出 MyBatis | CRUD 操作、配置解析

3、CRUD 3.1 namespace namespace 中的包名要和 Dao/Mapper 接口的包名一致&#xff01; 比如将 UserDao 改名为 UserMapper 运行发现抱错&#xff0c;这是因为 UserMapper.xml 中没有同步更改 namespace 成功运行 给出 UserMapper 中的所有接口&#xff0c;接下来一一对…...

Hutool 发送 HTTP 请求的几种常见写法

最简单的 GET 请求&#xff1a; String result HttpUtil.get("https://www.baidu.com");带参数的 GET 请求&#xff1a; // 方法1: 直接拼接URL参数 String result HttpUtil.get("https://www.baidu.com?name张三&age18");// 方法2: 使用 HashMap…...

计算机网络|数据流向剖析与分层模型详解

文章目录 一、网络中的数据流向二、计算机网络通信模型1.OSI 模型2.TCP/IP 模型3.TCP/IP五层模型3.1 分层架构描述3.2各层地址结构3.3UDP数据包报头结构 三、总结 一、网络中的数据流向 在计算机网络中&#xff0c;数据的流向是指数据从发送端到接收端的传输路径。数据流向涉及…...

在Java技术栈中,常用的分布式一致性算法和框架

在Java技术栈中&#xff0c;常用的分布式一致性算法和框架包括&#xff1a; Raft算法&#xff1a; 常用框架&#xff1a; etcd&#xff1a;虽然主要用Go语言编写&#xff0c;但可以通过Java客户端进行访问和操作。Apache Kafka&#xff1a;在其控制器选举中使用类似Raft的机…...

2024.12.29(进程线程实现并发服务器)

作业 多进程多线程并发服务器实现一遍提交。 服务器 #include <myhead.h> #define PORT 12345 #define IP "192.168.124.123"void *fun(void *fd) {int newfd *(int *)fd;char buff[1024];while(1){int res recv(newfd,buff,sizeof(buff),0);if(res 0){p…...

Docker完整技术汇总

Docker 背景引入 在实际开发过程中有三个环境&#xff0c;分别是&#xff1a;开发环境、测试环境以及生产环境&#xff0c;假设开发环境中开发人员用的是jdk8&#xff0c;而在测试环境中测试人员用的时jdk7&#xff0c;这就导致程序员开发完系统后将其打成jar包发给测试人员后…...

区块链安全常见的攻击合约和简单复现,附带详细分析——不安全调用漏洞 (Unsafe Call Vulnerability)【6】

区块链安全常见的攻击分析——不安全调用漏洞 Unsafe Call Vulnerability 区块链安全常见的攻击合约和简单复现&#xff0c;附带详细分析——不安全调用漏洞 (Unsafe Call Vulnerability)【6】1.1 漏洞合约1.2 漏洞分析1.3 攻击步骤分析1.4 攻击合约 区块链安全常见的攻击合约和…...

Vue.js 高难度组件开发:从插件化到性能极限优化

Vue.js 高难度组件开发&#xff1a;从插件化到性能极限优化 引言一、插件化组件开发1. 什么是插件化组件2. 案例&#xff1a;构建一个插件化的图表组件 二、动态扩展与自定义组件行为1. 动态添加组件功能 三、复杂交互与细粒度状态管理1. 使用 Vuex 的模块化和动态模块注册 四、…...

一个通用的居于 OAuth2的API集成方案

在现代 web 应用程序中&#xff0c;OAuth 协议是授权和认证的主流选择。为了与多个授权提供商进行无缝对接&#xff0c;我们需要一个易于扩展和维护的 OAuth 解决方案。本文将介绍如何构建一个灵活的、支持多提供商的 OAuth 系统&#xff0c;包括动态 API 调用、路径参数替换、…...

折腾日记:如何让吃灰笔记本发挥余热——搭建一个相册服务

背景 之前写过&#xff0c;我在家里用了一台旧的工作站笔记本做了服务器&#xff0c;连上一个绿联的5位硬盘盒实现简单的网盘功能&#xff0c;然而&#xff0c;还是觉的不太理想&#xff0c;比如使用filebrowser虽然可以备份文件和图片&#xff0c;当使用手机使用网页&#xf…...

C# dynamic 类型详解

简介 C# 中的 dynamic 是一种特殊类型&#xff0c;它允许在运行时确定对象的类型和成员&#xff0c;而不是在编译时。 dynamic 的定义 dynamic 是一种类型&#xff0c;它告诉编译器对其进行“动态类型解析”。 dynamic 类型的变量会跳过编译时类型检查&#xff0c;所有的操作…...

postgresql ERROR: cannot drop the currently open database

postgresql ERROR: cannot drop the currently open database 解释&#xff1a; 这个错误表明你正在尝试删除或者切换当前正在使用的数据库。在PostgreSQL中&#xff0c;一个数据库对应着一个进程&#xff0c;当一个数据库处于打开状态时&#xff0c;你不能直接删除或者切换它…...

Excel基础知识

一&#xff1a;数组 一行或者一列数据称为一维数组&#xff0c;多行多列称为二维数组&#xff0c;数组支持算术运算&#xff08;如加减乘除等&#xff09;。 行&#xff1a;{1,2,3,4} 数组中的每个值用逗号分隔列&#xff1a;{1;2;3;4} 数组中的每个值用分号分隔行列&#xf…...

【pwnlab_init靶场渗透】

文章目录 一、基础信息 二、信息收集 三、漏洞利用 四、反弹shell 五、提权 一、基础信息 Kali IP &#xff1a;192.168.20.146 靶机IP&#xff1a;192.168.20.157 二、信息收集 nmap -sS -sV -p- -A 192.168.20.157 开放了80、111、3306、50749等端口 访问一下80端口…...

【泰克生物】酶突变文库筛选技术:通过酵母展示实现酶的精准进化

酶工程是生物技术中的一个重要领域&#xff0c;涵盖了酶的改造、优化和应用。通过对酶分子进行定向进化&#xff0c;可以获得具有更高催化效率、更广泛底物特异性或更强稳定性的酶。酶突变文库筛选技术&#xff0c;尤其是酵母展示平台&#xff0c;提供了一种高效且可操作的方法…...

C++Primer 类简介

欢迎阅读我的 【CPrimer】专栏 专栏简介&#xff1a;本专栏主要面向C初学者&#xff0c;解释C的一些基本概念和基础语言特性&#xff0c;涉及C标准库的用法&#xff0c;面向对象特性&#xff0c;泛型特性高级用法。通过使用标准库中定义的抽象设施&#xff0c;使你更加适应高级…...

人工智能知识分享第三天-机器学习中交叉验证和网格搜索

交叉验证和网格搜索 交叉验证解释: 概述: 它是一种更加完善的, 可信度更高的模型预估方式, 思路是: 把数据集分成n份, 每次都取1份当做测试集, 其它的当做训练集, 然后计算模型的: 评分. 然后再用下1份当做测试集, 其它当做训练集, 计算模型评分, 分成几份, 就进行几次计算, 最…...

00序言:我为什么会选择AI?

序言&#xff1a;我为什么会选择AI&#xff1f; 2023年&#xff0c;对我来说是一个转折点。那一年&#xff0c;我在人工智能领域已经积累了几年的经验&#xff0c;深刻感受到了这场技术变革的巨大冲击。曾经&#xff0c;我也像许多人一样&#xff0c;怀疑自己是否能跟上这个快…...

【AIGC-ChatGPT副业提示词指令 - 动图】魔法咖啡馆:一个融合创意与治愈的互动体验设计

引言 在当今快节奏的生活中&#xff0c;咖啡早已不仅仅是提神醒脑的饮品&#xff0c;更成为了一种情感寄托和生活态度的表达。本文将介绍一个独特的"魔法咖啡馆"互动体验设计&#xff0c;通过将咖啡与情感、魔法元素相结合&#xff0c;创造出一个充满想象力和治愈感…...

VSCode outline显示异常的解决方法——清除VSCode的配置和用户文件

1. 删除所有配置文件 sudo apt remove --purge code2. 删除所有用户文件 rm -rf ~/.config/Code rm -rf ~/.vscode rm -rf ~/.local/share/code rm -rf ~/.cache/Code3. 重装Code sudo dpkg -i code_1.96.2-1734607745_amd64.deb如此&#xff0c;可修复异常导致的outline无…...

Maple软件的安装和使用

文章目录 1.前言说明2.我为什么要学习Maple3.软件的安装4.如何使用4.1基本的赋值语句4.2函数的定义4.3三个类型的书写介质 5.指数运算5.1使用面板5.2自己输入 6.对数的使用 1.前言说明 众所周知&#xff0c;我虽然是一名这个计算机专业的学生&#xff0c;但是我对于数学&#…...

elasticsearch-java客户端jar包中各模块的应用梳理

最近使用elasticsearch-java客户端实现对elasticsearch服务的Api请求&#xff0c;现对elasticsearch-java客户端jar包中各模块的应用做个梳理。主要是对co.elastic.clients.elasticsearch路径下的各子包的简单说明。使用的版本为&#xff1a;co.elastic.clients:elasticsearch-…...

android13 系统文字大小和显示大小的修改

没啥可解释&#xff0c;如题所示&#xff0c;修改系统默认文字大小和显示大小 一修改系统文字大小&#xff1a; 系统文字太小&#xff0c;需要修改文字大小修改如下 commit 82675b7d8ac278e80d94e6b2b1417b266065d2ec Author: admin <bianjbflyscale.cn> Date: Sat …...

【华为OD-E卷 - 任务总执行时长 100分(python、java、c++、js、c)】

【华为OD-E卷 - 任务总执行时长 100分&#xff08;python、java、c、js、c&#xff09;】 题目 任务编排服务负责对任务进行组合调度。 参与编排的任务有两种类型&#xff0c;其中一种执行时长为taskA&#xff0c;另一种执行时长为taskB。 任务一旦开始执行不能被打断&#x…...

vue中子组件给父组件传值

在 Vue.js 中&#xff0c;子组件向父组件传递数据或事件通常是通过 $emit 方法来实现的。这个方法允许子组件触发一个自定义事件&#xff0c;父组件可以通过监听这些事件来接收信息。以下是实现这一过程的基本步骤&#xff1a; 1. 子组件触发事件 在子组件中&#xff0c;使用…...

【js】记录预览pdf文件

接口调用拿到pdf的文件流&#xff0c;用blob处理这个文件流拿到url&#xff0c;使用window.open跳转新的窗口进行预览 api({dataType: blob, }).then(res >{if(res.code 0){this.previewPDF(res,application/pdf;charsetutf-8,pdf文件名)} })previewPDF (res, type, fname…...

【Spring MVC 异常处理机制】应对意外情况

在 Web 应用中&#xff0c;异常是不可避免的。用户的输入不合法&#xff0c;服务的某部分出错&#xff0c;或者数据库连接失败&#xff0c;这些情况都可能触发异常。那么问题来了&#xff1a;如何优雅地捕获并处理这些异常&#xff0c;让用户体验不至于因为一时的错误而受损&am…...

《计算机组成及汇编语言原理》阅读笔记:p128-p132

《计算机组成及汇编语言原理》学习第 10 天&#xff0c;p128-p132 总结&#xff0c;总计 5 页。 一、技术总结 1.8088 organization and architecture 8088处理器是16位电脑&#xff0c;寄存器是16位&#xff0c;数据总线(data bus)是8位&#xff0c;地址总线是20位。 (1)g…...

留学生交流互动系统|Java|SSM|VUE| 前后端分离

【技术栈】 1⃣️&#xff1a;架构: B/S、MVC 2⃣️&#xff1a;系统环境&#xff1a;Windowsh/Mac 3⃣️&#xff1a;开发环境&#xff1a;IDEA、JDK1.8、Maven、Mysql5.7 4⃣️&#xff1a;技术栈&#xff1a;Java、Mysql、SSM、Mybatis-Plus、VUE、jquery,html 5⃣️数据库可…...

Windows IPC

进程间通信 (IPC&#xff0c;Inter-Process Communication) 进程间通信 (IPC) 是一种在进程之间建立连接的机制&#xff0c;在两台计算机或一台多任务计算机上运行&#xff0c;以允许数据在这些进程之间流动。进程间通信 (IPC) 机制通常用于客户端/服务器环境&#xff0c;并在…...

BMS存储模块的设计

目的 电池管理系统中存在着数据本地存储的要求&#xff0c;保证控制器重新上电后能够根据存储器中的一些参数恢复控制状态&#xff0c;和信息的下电存储1.继电器故障信息的存储。2. 系统性故障的存储。3.SOC、SOH相关信息的存储。4.均衡参数的存储。5.系统时间信息。6.出厂信息…...

2024-12-29-sklearn学习(25)无监督学习-神经网络模型(无监督) 烟笼寒水月笼沙,夜泊秦淮近酒家。

文章目录 sklearn学习(25) 无监督学习-神经网络模型&#xff08;无监督&#xff09;25.1 限制波尔兹曼机25.1.1 图形模型和参数化25.1.2 伯努利限制玻尔兹曼机25.1.3 随机最大似然学习 sklearn学习(25) 无监督学习-神经网络模型&#xff08;无监督&#xff09; 文章参考网站&a…...

【动态规划篇】穿越算法迷雾:约瑟夫环问题的奇幻密码

欢迎拜访&#xff1a;羑悻的小杀马特.-CSDN博客 本篇主题&#xff1a;带你众人皆知的约瑟夫环问题 制作日期&#xff1a;2024.12.29 隶属专栏&#xff1a;C/C题海汇总 目录 引言&#xff1a; 一约瑟夫环问题介绍&#xff1a; 11问题介绍&#xff1a; 1.2起源与历史背景&…...

【Elasticsearch】DSL查询文档

目录 1.DSL查询文档 1.1.DSL查询分类 1.2.全文检索查询 1.2.1.使用场景 1.2.2.基本语法 1.2.3.示例 1.2.4.总结 1.3.精准查询 1.3.1.term查询 1.3.2.range查询 1.3.3.总结 1.4.地理坐标查询 1.4.1.矩形范围查询 1.4.2.附近查询 1.5.复合查询 1.5.1.相关性算分 …...

MySQL第三弹----函数

笔上得来终觉浅,绝知此事要躬行 &#x1f525; 个人主页&#xff1a;星云爱编程 &#x1f525; 所属专栏&#xff1a;MySQL &#x1f337;追光的人&#xff0c;终会万丈光芒 &#x1f389;欢迎大家点赞&#x1f44d;评论&#x1f4dd;收藏⭐文章 一、合计/统计函数 1.1count…...

路由器刷机TP-Link tp-link-WDR5660 路由器升级宽带速度

何在路由器上设置代理服务器&#xff1f; 如何在路由器上设置代理服务器&#xff1f; 让所有连接到该路由器的设备都能够享受代理服务器的好处是一个不错的选择&#xff0c;特别是当需要访问特定的网站或加速网络连接的时候。下面是一些您可以跟随的步骤&#xff0c;使用路由器…...

Qml 中实现水印工具

【写在前面】 在 Qt 的 Quick 模块中&#xff0c;QQuickPaintedItem 是一个非常有用的类&#xff0c;它允许我们在 Qml 中自定义绘制逻辑。 我们可以通过这种方式实现水印工具&#xff0c;包括在文本、图片或整个窗口上添加水印。 本文将介绍如何在 Qml 中实现一个简单但功能…...

2024年数字政府服务能力优秀创新案例汇编(附下载)

12月19日&#xff0c;由中国电子信息产业发展研究院指导、中国软件评测中心主办的“2024数字政府评估大会”在北京召开&#xff0c;大会主题是&#xff1a;为公众带来更好服务体验。 会上&#xff0c;中国软件评测中心副主任吴志刚发布了2024年数字政府服务能力评估结果&#…...

数据链路层知识要点

这里写目录标题 数据链路层的功能1.封装成帧2.差错控制2.1循环冗余校验&#xff08;CRC&#xff09;2.2奇偶校验法 3.可靠传输3.1停止等待协议(SW)3.2后退N帧协议(GBN)3.3选择重传协议(SR) 4.使用广播信道的数据链路层5.以太网(局域网)5.1以太网与网卡5.2以太网的MAC地址 6.VLA…...