贪心算法活动安排问题c语言实现以及数学模型的建立存储结构选择

下面是贪心算法活动安排问题的C语言实现：

#include <stdio.h>
#include <stdlib.h>

// 活动结构体
typedef struct Activity {
    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) {
    int count = 1;  // 计数器，记录已安排的活动数
    int end = activities[0].end;  // 记录上一个已安排活动的结束时间
    for (int i = 1; i < n; i++) {
        if (activities[i].start >= end) {
            count++;
            end = activities[i].end;
        }
    }
    return count;
}

int main() {
    int n;
    printf("请输入活动数：");
    scanf("%d", &n);

    Activity *activities = (Activity*)malloc(n * sizeof(Activity));
    printf("请按开始时间和结束时间的顺序依次输入每个活动的时间：\n");
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &activities[i].start, &activities[i].end);
    }

    qsort(activities, n, sizeof(Activity), cmp);  // 按结束时间升序排列

    printf("最多可以安排%d个活动\n", activitySelection(activities, n));
    free(activities);
    return 0;
}

该实现中，我们使用了结构体来存储活动的开始时间和结束时间，使用了qsort函数来按结束时间升序排列，使用了activitySelection函数来实现贪心算法的核心逻辑。

对于数学模型的建立，我们可以将活动安排问题看作是一个集合覆盖问题，其中每个活动代表一个集合，集合中包含的元素是活动的时间段，我们需要选择尽可能少的集合，使得它们的并集覆盖了所有的元素。因此，我们可以使用一个数组来存储活动的开始时间和结束时间，使用一个二维数组来表示集合与元素之间的关系，例如：

int sets[MAX_SETS][MAX_ELEMENTS];  // 集合与元素之间的关系

其中，MAX_SETS表示最大集合数，MAX_ELEMENTS表示每个集合中最多包含的元素数。对于每个活动i，我们可以将其时间段表示为一个集合Si，其中元素j表示时间段中的第j个时间点，例如：

for (int i = 0; i < n; i++) {
    for (int j = activities[i].start; j <= activities[i].end; j++) {
        sets[i][j] = 1;  // 时间点j属于集合Si
    }
}

然后，我们可以使用贪心算法来选择最少的集合，使得它们的并集覆盖了所有的元素，例如：

int selected[MAX_SETS] = {0};  // 记录已经选择的集合
int count = 0;  // 记录已经选择的集合数
for (int j = 0; j < MAX_ELEMENTS; j++) {
    int max_cover = 0;  // 记录当前元素被最多集合覆盖的次数
    int max_set = -1;   // 记录覆盖当前元素最多的集合
    for (int i = 0; i < MAX_SETS; i++) {
        if (!selected[i] && sets[i][j] && cover[i] > max_cover) {
            max_cover = cover[i];
            max_set = i;
        }
    }
    if (max_set != -1) {
        selected[max_set] = 1;
        count++;
        for (int k = 0; k < MAX_ELEMENTS; k++) {
            if (sets[max_set][k]) {
                cover[k]++;
            }
        }
    }
}

其中，selected数组记录已经选择的集合，cover数组记录每个元素被覆盖的次数。该算法的时间复杂度为O(MAX_SETS * MAX_ELEMENTS ^ 2)，其中MAX_SETS表示集合数，MAX_ELEMENTS表示每个集合中最多包含的元素数。