用C语言实现贪心活动选择、带权活动选择问题
时间: 2024-01-02 18:53:52 浏览: 96
贪心活动选择问题:
给定 n 个活动的起始时间和结束时间,选择尽可能多的活动,使得它们互不冲突。
贪心算法的思路是每次选择结束时间最早的活动,这样能够腾出更多的时间来安排其他活动。
C 语言代码如下:
```c
#include <stdio.h>
#include <stdlib.h>
// 活动结构体
typedef struct {
int start;
int end;
} Activity;
// 比较函数
int cmp(const void *a, const void *b) {
return ((Activity *)a)->end - ((Activity *)b)->end;
}
// 贪心算法
void greedy_activity_selection(Activity *activities, int n) {
int i, j;
int count = 1; // 记录选中的活动数量
int last_end_time = activities[0].end;
for (i = 1; i < n; i++) {
if (activities[i].start >= last_end_time) {
count++;
last_end_time = activities[i].end;
}
}
printf("最多可以选中 %d 个活动\n", count);
}
int main() {
int n, i;
Activity *activities;
printf("请输入活动总数:");
scanf("%d", &n);
activities = (Activity *)malloc(n * sizeof(Activity));
printf("请按开始时间和结束时间的顺序输入每个活动的起始时间和结束时间:\n");
for (i = 0; i < n; i++) {
scanf("%d %d", &activities[i].start, &activities[i].end);
}
// 按结束时间排序
qsort(activities, n, sizeof(Activity), cmp);
greedy_activity_selection(activities, n);
free(activities);
return 0;
}
```
带权活动选择问题:
在贪心活动选择问题的基础上,每个活动还有一个权重,选择的活动权重之和最大。
贪心算法的思路是每次选择权重最大的活动。
C 语言代码如下:
```c
#include <stdio.h>
#include <stdlib.h>
// 活动结构体
typedef struct {
int start;
int end;
int weight;
} Activity;
// 比较函数
int cmp(const void *a, const void *b) {
return ((Activity *)b)->weight - ((Activity *)a)->weight;
}
// 贪心算法
void greedy_weighted_activity_selection(Activity *activities, int n) {
int i, j;
int count = 0; // 记录选中的活动数量
int last_end_time = 0;
int max_weight = 0;
for (i = 0; i < n; i++) {
if (activities[i].start >= last_end_time) {
count++;
last_end_time = activities[i].end;
max_weight += activities[i].weight;
}
}
printf("最多可以选中 %d 个活动,权重之和为 %d\n", count, max_weight);
}
int main() {
int n, i;
Activity *activities;
printf("请输入活动总数:");
scanf("%d", &n);
activities = (Activity *)malloc(n * sizeof(Activity));
printf("请按开始时间、结束时间和权重的顺序输入每个活动的起始时间、结束时间和权重:\n");
for (i = 0; i < n; i++) {
scanf("%d %d %d", &activities[i].start, &activities[i].end, &activities[i].weight);
}
// 按权重排序
qsort(activities, n, sizeof(Activity), cmp);
greedy_weighted_activity_selection(activities, n);
free(activities);
return 0;
}
```