实验：贪心算法

实验二：贪心算法

【实验目的】

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

【实验性质】

验证性实验。

【实验要求】

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

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