实验:贪心算法

server/2024/9/25 16:09:07/

实验二:贪心算法

【实验目的】

应用贪心算法求解活动安排问题。

【实验性质】

验证性实验。

【实验要求】

活动安排问题是可以用贪心算法有效求解的很好的例子。

问题:有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)。


http://www.ppmy.cn/server/49334.html

相关文章

IDEA2023中使用run Dashboard面板?实现批量运行微服务

1、直接点击Add service--->Run Configuration Type---->Spring Boot 2、这样就出现了run Dashboard面板&#xff0c;可同时运行多个工程模块&#xff0c;shift选中所有启动类组命名&#xff08;Group Configurations&#xff09; 3、启动所有的项目

基数排序详解

目录 一、桶排序思想 1.1 什么是桶排序 1.2 桶排序的步骤 二、基数排序思想 2.1 什么是基数排序 2.2 实现方式 2.3 图解 三、代码思路 3.1 前置工作 3.2 映射 3.3 排序 四、C语言源码 一、桶排序思想 1.1 什么是桶排序 桶排序(Bucket sort)是一种排序算法&#xff…

WPS for Linux 无法使用fcitx中文输入法

现象 只能输入英文&#xff0c;按下Shift尝试切换输入法没有反应 解决办法 编辑如下文件/usr/bin/wps/usr/bin/et/usr/bin/wpp 分别对应wps word、excel、powerpoint&#xff0c;修改每个文件&#xff0c;加入如下代码并保存 export XMODIFIERS"imfcitx" export …

【云原生| K8S系列】Kubernetes Daemonset,全面指南

Kubernetes中的DaemonSet是什么? Kubernetes是一个分布式系统&#xff0c;Kubernetes平台管理员应该有一些功能可以在所有节点上运行特定于平台的应用程序。例如&#xff0c;在所有Kubernetes节点上运行日志代理。 这就是Daemonset发挥作用的地方。 Daemonset是一个原生的K…

Java | Leetcode Java题解之第149题直线上最多的点数

题目&#xff1a; 题解&#xff1a; class Solution {public int maxPoints(int[][] points) {int n points.length;if (n < 2) {return n;}int ret 0;for (int i 0; i < n; i) {if (ret > n - i || ret > n / 2) {break;}Map<Integer, Integer> map ne…

Web的UI自动化基础知识

目录 1 Web自动化入门基础1.1 自动化知识以及工具1.2 主流web自动化测试工具1.3 入门案例 2 使用工具的API2.1 元素定位2.1.1 id选择器2.1.2 name2.1.3 class_name选择器2.1.4 tag_name选择器2.1.5 link_text选择器2.1.6 partial_link_text选择器2.1.7 xpath选择器2.1.8 CSS选择…

《天软股票特色因子定期报告》

最新《天软股票特色因子定期报告》&#xff08;2024-06&#xff09;&#xff0c;抢先发布 内容概要如下&#xff1a; 天软特色因子A08006&#xff08;近一月日度买卖压力2&#xff09;从行业角度分析&#xff0c;在电子设备、石油石化行业表现稳定&#xff0c;无论在有效性、区…

OpenCV之cv::undistort

在 OpenCV 中&#xff0c;cv::undistort 函数用于校正畸变的图像。它的基本形式如下&#xff1a; void undistort(InputArray src, OutputArray dst, InputArray cameraMatrix, InputArray distCoeffs, InputArray newCameraMatrix noArray());参数解释&#xff1a; src&…