活动安排问题 动态规划 C语言实现
时间: 2023-12-04 07:40:59 浏览: 56
活动安排问题是一个经典的动态规划问题,可以使用C语言实现。具体步骤如下:
1. 首先,将所有的活动按照结束时间从早到晚排序。
2. 定义一个数组dp,其中dp[i]表示前i个活动的最大兼容活动数。
3. 初始化dp为0。
4. 对于每个i,从i-1向前遍历所有的活动j,如果活动j的结束时间小于活动i的开始时间,则更新dp[i]为dp[j]+1和dp[i-1]中的较大值。
5. 遍历完所有的活动后,dp[n]即为最终的结果,其中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;
}
// 动态规划求解活动安排问题
int activitySelection(Activity activities[], int n) {
// 按照结束时间从早到晚排序
qsort(activities, n, sizeof(Activity), cmp);
// 定义dp数组
int dp[n+1];
dp[0] = 0;
// 动态规划求解
for (int i = 1; i <= n; i++) {
dp[i] = 1;
for (int j = i-1; j >= 1; j--) {
if (activities[j-1].end <= activities[i-1].start) {
dp[i] = dp[j] + 1 > dp[i] ? dp[j] + 1 : dp[i];
}
}
}
// 返回最大兼容活动数
return dp[n];
}
int main() {
// 测试数据
Activity activities[] = {{1, 4}, {3, 5}, {0, 6}, {5, 7}, {3, 8}, {5, 9}, {6, 10}, {8, 11}, {8, 12}, {2, 13}, {12, 14}};
// 活动总数
int n = sizeof(activities) / sizeof(Activity);
// 求解最大兼容活动数
int maxActivities = activitySelection(activities, n);
// 输出结果
printf("最大兼容活动数为:%d\n", maxActivities);
return 0;
}
```