实验:贪心算法
实验二:贪心算法
【实验目的】
应用贪心算法求解活动安排问题。
【实验性质】
验证性实验。
【实验要求】
活动安排问题是可以用贪心算法有效求解的很好的例子。
问题:有n个活动的集合A={1,2,…,n},其中每个活动都要求使用同一资源,如演讲会场等,而在同一时间内只有一个活动能使用这一资源。
求解:安排尽量多项活动在该场地进行,即求A的最大相容子集。
设待安排的11个活动的开始时间和结束时间按结束时间的升序排列如下:
| i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
| s[i] | 1 | 3 | 0 | 5 | 3 | 5 | 6 | 8 | 8 | 2 | 12 |
| f[i] | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
将此表数据作为实现该算法的测试数据。
【算法思想及处理过程】
1.定义了活动结构体Activity,包含活动的名称name、开始时间start和结束时间end。
2.定义了比较函数compare,用于按照活动的结束时间升序排序。
3.定义了一个活动安排函数activityArrangement,接受一个活动数组和活动个数作为参数,并按照活动结束时间排序后进行活动安排。
4.在活动安排函数中,首先使用sort函数对活动数组进行排序,排序规则是使用之前定义的比较函数compare。
5.输出第一个活动的信息。
6.初始化一个变量lastEnd,用于记录最后一个加入最大相容子集的活动的结束时间。
7.遍历剩下的活动数组,如果当前活动的开始时间晚于等于lastEnd,即活动不与已加入的活动冲突,将该活动加入最大相容子集,并更新lastEnd为该活动的结束时间。
8.输出结果。
在主函数中,首先获取用户输入的活动个数,然后根据输入的活动个数循环获取活动的名称、开始时间和结束时间。最后调用活动安排函数(activityArrangement)进行活动安排。
【程序代码】
#include <iostream>
#include <algorithm>
using namespace std;
struct Activity {
int name;
int start;
int end;
};
bool compare(Activity a, Activity b) {
return a.end < b.end;
}
void activityArrangement(Activity activities[], int n) {
sort(activities, activities + n, compare);
cout << "结果为: "<<endl;
cout << "Activite " << activities[0].name << "=" << activities[0].start << ", " << activities[0].end <<endl;
int lastEnd = activities[0].end;
for (int i = 1; i < n; i++) {
if (activities[i].start >= lastEnd) {
cout << "Activite "<<activities[i].name <<"=" << activities[i].start << ", " << activities[i].end <<endl;
lastEnd = activities[i].end;
}
}
cout << endl;
}
int main() {
int n;
cout << "请输入活动个数: ";
cin >> n;
Activity activities[50];
for (int i = 0; i < n; i++) {
cout << "请输入第"<<i+1<<"次活动信息(名称 开始时间 结束时间) : ";
cin >> activities[i].name >> activities[i].start >> activities[i].end;
}
activityArrangement(activities, n);
return 0;
}
【运行结果】
自行运行截图
【算法分析】
排序算法的时间复杂度:使用了STL的sort函数对活动数组进行排序,该函数的时间复杂度为 O(nlogn),其中n为活动个数。
遍历活动数组的时间复杂度:在活动安排函数中,遍历了剩下的活动数组,时间复杂度为 O(n),其中n为活动个数。
综上,代码的时间复杂度为 O(nlogn + n),即 O(nlogn)。
相关文章:
实验:贪心算法
实验二:贪心算法 【实验目的】 应用贪心算法求解活动安排问题。 【实验性质】 验证性实验。 【实验要求】 活动安排问题是可以用贪心算法有效求解的很好的例子。 问题:有n个活动的集合A{1,2,…,n},其中每个活动都要求使用同一资源&…...
Python学习笔记12 -- 有关布尔值的详细说明
一、布尔表达式 最终值为true 或者false 二、常见形式: 1、常量:true false 2、比较运算: and ! 3、复合运算: and and or 4、其他 例:检测闰年: def specialYearMine(year):if (year%4 …...
SQL-窗口函数合集
目录 1.窗口函数简介2.窗口的定义3.相关题目示例3.1 PERCENT_RANK()2346 以百分比计算排名 3.2 FIRST_VALUE()/LAST_VALUE()/NTH_VALUE()2388 将表中的空值更改为前一个值 1.窗口函数简介 MySQL 开窗函数(Window Functions)是 MySQL 8.0 版本引入的一个…...
2024 全球软件研发技术大会官宣,50+专家共话软件智能新范式!
2024年的全球软件研发技术大会(SDCon)由CSDN和高端IT咨询与教育平台Boolan联合主办,将于7月4日至5日在北京威斯汀酒店举行。本次大会的主题为“大模型驱动软件智能化新范式”,旨在探讨大模型和开源技术的发展如何引领全球软件研发…...
opencv快速安装以及各种查看版本命令
安装opencv并查看其版本,直接通过一个可执行文件实现。 #!/bin/bashwget https://codeload.github.com/opencv/opencv/zip/3.4 -O opencv-3.4.zip && unzip opencv-3.4.zip && cd opencv-3.4 && \mkdir build && cd build &&a…...
免费学习通刷课(免费高分)Pro版
文章目录 概要整体架构流程小结 概要 关于上一版的免费高分的学习通刷课,有很多人觉得还得登录太复杂了,然后我又发现了个神脚本,操作简单,可以后台挂着,但是还是建议调整速度到2倍速,然后找到你该刷的课&…...
线性数据结构-队列
队列(Queue)是一种先进先出(First In First Out, FIFO)的数据结构,它按照元素进入的顺序来处理元素。队列的基本操作包括: enqueue:在队列的末尾添加一个元素。dequeue:移除队列的第…...
python脚本将视频抽帧为图像数据集
AI应用开发相关目录 本专栏包括AI应用开发相关内容分享,包括不限于AI算法部署实施细节、AI应用后端分析服务相关概念及开发技巧、AI应用后端应用服务相关概念及开发技巧、AI应用前端实现路径及开发技巧 适用于具备一定算法及Python使用基础的人群 AI应用开发流程概…...
Xmind导入纯文本TXT方法
最近有很多同事咨询我如何在xmind直接导入纯文本txt笔记或者思维导图呢? 解决办法如下: 1.先打开xmind随便打开一个思维导图-文件-导出-marldown 2.选中导出的markdown文件。右键-打开方式-苹果系统选择文本编辑,Win系统选择记事本 3.按照图示…...
深度学习在老年痴呆检测中的应用:数据集综述
深度学习在老年痴呆检测中的应用:数据集综述 引言 老年痴呆(Alzheimer’s Disease, AD)是一种神经退行性疾病,主要影响老年人,导致记忆力、认知能力和行为的逐步衰退。早期检测和诊断对于延缓疾病进展、提高患者生活质量至关重要。近年来,深度学习技术在医学影像分析和…...
【FreeRTOS】内存管理笔记
一、为什么要自己实现内存管理? 后续的章节涉及这些内核对象:task、queue、semaphores和event group等。为了让FreeRTOS更容 易使用,这些内核对象一般都是动态分配:用到时分配,不使用时释放。使用内存的动态管理功能&…...
【数据结构】二叉树:一场关于节点与遍历的艺术之旅
专栏引入 哈喽大家好,我是野生的编程萌新,首先感谢大家的观看。数据结构的学习者大多有这样的想法:数据结构很重要,一定要学好,但数据结构比较抽象,有些算法理解起来很困难,学的很累。我想让大家…...
arm系统中双网卡共存问题
文章目录 单网卡单独运行双网卡共存问题双网卡解决方案方案一方案二方案三验证双网卡通过网卡名获取IP通过TCP与服务端通信参考单网卡单独运行 双网卡共存问题 双网卡解决方案 方案一 https://blog.csdn.net/HowieXue/article/details/75937972 方案二 http://bbs.witech…...
IDEA创建Mybatis项目
IDEA创建Mybatis项目 第一步:创建库表 -- 创建数据库 create database mybatis_db;-- 使用数据库 use mybatis_db;-- 创建user表 CREATE TABLE user (id INT AUTO_INCREMENT PRIMARY KEY,username VARCHAR(50) NOT NULL,password VARCHAR(50) NOT NULL,email VARC…...
排序---快速排序
前言 个人小记 一、代码 #include <stdio.h> #include <stdlib.h> #include <string.h> #include <time.h> #define MAX_ARR 100000 #define swap(a,b)\ {\__typeof(a) __ca;\ab,b__c;\ } #define TEST(func ,arr,l,r)\ {\int nr-l;\printf("tes…...
#08【面试问题整理】嵌入式软件工程师
前言 本系列博客主要记录有关嵌入式方面的面试重点知识,本系列已经更新的篇目有如下: 1.1进程线程的基本概念 1.2 并发,同步,异步,互斥,阻塞,非阻塞的理解 1.3 孤儿进程、僵尸进程、守护进程的概念 3.1 TCP UDP 【本篇】3.2 三次握手、四次挥手...
统计绘图 | 一行代码教你绘制顶级期刊要求配图
在分享完即可统计又可可视化绘制的优秀可视化包后(具体内容可看 统计绘图 | 既能统计分析又能可视化绘制的技能 。就有小伙伴私信问我需要绘制出版级别的可视化图表有什么快速的方法?“。鉴于我是一个比较宠粉的小编,几天就给大家推荐一个技巧࿰…...
[ue5]建模场景学习笔记(6)——必修内容可交互的地形,交互沙(4)
1.需求分析: 现在我们已经有了可以在世界内近于无限的跑动痕迹,现在需要对痕迹进行细化,包括例如当人物跳起时便不再绘制痕迹,以及痕迹应该存在深浅,应该由两只脚分别绘制,同时也应该对地面材质进行进一步处…...
5.2 参照完整性
5.2.1 外键约束 语法格式:constraint < symbol > foreign key ( col_nam1[, col_nam2... ] ) references table_name (col_nam1[, col_nam2...]) [ on delete { restrict | cascade | set null | no action } ] [ on update { restrict | cascade | set nu…...
SpringCache 缓存 - @Cacheable、@CacheEvict、@CachePut、@Caching、CacheConfig 以及优劣分析
目录 SpringCache 缓存 环境配置 1)依赖如下 2)配置文件 3)设置缓存的 value 序列化为 JSON 格式 4)EnableCaching 实战开发 Cacheable CacheEvict CachePut Caching CacheConfig SpringCache 的优势和劣势 读操作…...
MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例
一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...
1688商品列表API与其他数据源的对接思路
将1688商品列表API与其他数据源对接时,需结合业务场景设计数据流转链路,重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点: 一、核心对接场景与目标 商品数据同步 场景:将1688商品信息…...
Java-41 深入浅出 Spring - 声明式事务的支持 事务配置 XML模式 XML+注解模式
点一下关注吧!!!非常感谢!!持续更新!!! 🚀 AI篇持续更新中!(长期更新) 目前2025年06月05日更新到: AI炼丹日志-28 - Aud…...
【git】把本地更改提交远程新分支feature_g
创建并切换新分支 git checkout -b feature_g 添加并提交更改 git add . git commit -m “实现图片上传功能” 推送到远程 git push -u origin feature_g...
使用Matplotlib创建炫酷的3D散点图:数据可视化的新维度
文章目录 基础实现代码代码解析进阶技巧1. 自定义点的大小和颜色2. 添加图例和样式美化3. 真实数据应用示例实用技巧与注意事项完整示例(带样式)应用场景在数据科学和可视化领域,三维图形能为我们提供更丰富的数据洞察。本文将手把手教你如何使用Python的Matplotlib库创建引…...
JavaScript基础-API 和 Web API
在学习JavaScript的过程中,理解API(应用程序接口)和Web API的概念及其应用是非常重要的。这些工具极大地扩展了JavaScript的功能,使得开发者能够创建出功能丰富、交互性强的Web应用程序。本文将深入探讨JavaScript中的API与Web AP…...
Mysql8 忘记密码重置,以及问题解决
1.使用免密登录 找到配置MySQL文件,我的文件路径是/etc/mysql/my.cnf,有的人的是/etc/mysql/mysql.cnf 在里最后加入 skip-grant-tables重启MySQL服务 service mysql restartShutting down MySQL… SUCCESS! Starting MySQL… SUCCESS! 重启成功 2.登…...
DeepSeek源码深度解析 × 华为仓颉语言编程精粹——从MoE架构到全场景开发生态
前言 在人工智能技术飞速发展的今天,深度学习与大模型技术已成为推动行业变革的核心驱动力,而高效、灵活的开发工具与编程语言则为技术创新提供了重要支撑。本书以两大前沿技术领域为核心,系统性地呈现了两部深度技术著作的精华:…...
阿里云Ubuntu 22.04 64位搭建Flask流程(亲测)
cd /home 进入home盘 安装虚拟环境: 1、安装virtualenv pip install virtualenv 2.创建新的虚拟环境: virtualenv myenv 3、激活虚拟环境(激活环境可以在当前环境下安装包) source myenv/bin/activate 此时,终端…...
前端高频面试题2:浏览器/计算机网络
本专栏相关链接 前端高频面试题1:HTML/CSS 前端高频面试题2:浏览器/计算机网络 前端高频面试题3:JavaScript 1.什么是强缓存、协商缓存? 强缓存: 当浏览器请求资源时,首先检查本地缓存是否命中。如果命…...
