用c语言完成,设有n个活动的集合E={1,2,……,n},其中每个活动都要求使用同一资源,如演讲会场等,而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si<fi。如果选择了活动i,则它在时间区间[si,fi]内占用资源。若区间[si,fi]与区间[sj,fj]不相交,则称活动i与活动j是相容的。也就是说,当si>=fj或者sj>=fi时,活动i与活动j相容。活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合。 利用贪心算法的性质,通过选择适当的贪心策略的贪心算法解决活动安排问题,且能求得活动安排的最优解,并将相容活动的子集合中的时间列出来
时间: 2024-03-27 16:39:05 浏览: 63
好的,这是一个经典的贪心算法问题,也被称为活动选择问题。下面是使用C语言实现的代码,其中使用了贪心算法来求解最优解,并输出相容活动的子集合中的起始时间和结束时间:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义活动结构体
typedef struct activity {
int id; // 活动编号
int start; // 活动开始时间
int finish; // 活动结束时间
} activity;
// 按照结束时间从小到大排序
int cmp(const void* a, const void* b) {
return ((activity*)a)->finish - ((activity*)b)->finish;
}
// 贪心算法求解最大相容活动子集合
void activity_selection(activity arr[], int n) {
qsort(arr, n, sizeof(activity), cmp); // 按照结束时间排序
int i, j;
printf("最大相容活动子集合:\n");
printf("编号\t起始时间\t结束时间\n");
printf("%d\t%d\t%d\n", arr[0].id, arr[0].start, arr[0].finish); // 输出第一个活动
j = 0;
for (i = 1; i < n; i++) {
if (arr[i].start >= arr[j].finish) { // 如果当前活动与前一个活动不冲突
printf("%d\t%d\t%d\n", arr[i].id, arr[i].start, arr[i].finish); // 输出当前活动
j = i; // 更新前一个活动
}
}
}
int main() {
int n, i;
printf("请输入活动个数:\n");
scanf("%d", &n);
activity arr[n];
printf("请输入每个活动的起始时间和结束时间:\n");
for (i = 0; i < n; i++) {
arr[i].id = i + 1;
scanf("%d%d", &arr[i].start, &arr[i].finish);
}
activity_selection(arr, n);
return 0;
}
```
使用示例:
输入:
```
请输入活动个数:
5
请输入每个活动的起始时间和结束时间:
1 4
3 5
0 6
5 7
3 8
```
输出:
```
最大相容活动子集合:
编号 起始时间 结束时间
1 1 4
2 3 5
4 5 7
```
阅读全文