贪心算法举办活动c语言

这是一个使用贪心算法解决活动安排问题的C语言实现。该算法的思想是优先选择结束时间早的活动，以便为后续活动留出更多的时间。具体实现过程是先将所有活动按照结束时间从小到大排序，然后从第一个活动开始，依次判断每个活动是否与前面已经安排的活动时间冲突，如果不冲突，则将该活动加入安排中。最终输出可以安排的活动数。

代码中使用了结构体来存储每个活动的开始时间、结束时间和标志位，标志位用于表示该活动是否被选择。该算法的时间复杂度为O(nlogn)，其中n为活动数。

相关问题

贪心算法实现活动安排 C语言

以下是使用贪心算法实现活动安排的C语言代码示例：

#include <stdio.h>

// 定义活动结构体
struct Activity {
    int start; // 开始时间
    int end; // 结束时间
};

// 比较函数，用于排序
int cmp(const void *a, const void *b) {
    return ((struct Activity *)a)->end - ((struct Activity *)b)->end;
}

// 贪心算法实现活动安排
void activitySelection(struct Activity activities[], int n) {
    // 按照结束时间递增排序
    qsort(activities, n, sizeof(struct Activity), cmp);

    // 选取第一个活动
    int i = 0;
    printf("(%d, %d) ", activities[i].start, activities[i].end);

    // 选取其余活动
    for (int j = 1; j < n; j++) {
        if (activities[j].start >= activities[i].end) {
            printf("(%d, %d) ", activities[j].start, activities[j].end);
            i = j;
        }
    }
}

int main() {
    // 定义活动数组
    struct 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(activities[0]);

    // 输出最大兼容活动集合
    printf("最大兼容活动集合为：");
    activitySelection(activities, n);

    return 0;
}

贪心算法prim算法c语言

以下是使用C语言实现Prim算法的示例代码：

#include <stdio.h>
#include <stdbool.h>

#define INF 9999
#define V 5

int minKey(int key[], bool mstSet[])
{
    int min = INF, min_index;
    for (int v = 0; v < V; v++)
    {
        if (mstSet[v] == false && key[v] < min)
        {
            min = key[v];
            min_index = v;
        }
    }
    return min_index;
}

void printMST(int parent[], int graph[V][V])
{
    printf("Edge \tWeight\n");
    for (int i = 1; i < V; i++)
    {
        printf("%d - %d \t%d \n", parent[i], i, graph[i][parent[i]]);
    }
}

void primMST(int graph[V][V])
{
    int parent[V];
    int key[V];
    bool mstSet[V];

    for (int i = 0; i < V; i++)
    {
        key[i] = INF;
        mstSet[i] = false;
    }

    key[0] = 0;
    parent[0] = -1;

    for (int count = 0; count < V - 1; count++)
    {
        int u = minKey(key, mstSet);
        mstSet[u] = true;

        for (int v = 0; v < V; v++)
        {
            if (graph[u][v] && mstSet[v] == false && graph[u][v] < key[v])
            {
                parent[v] = u;
                key[v] = graph[u][v];
            }
        }
    }

    printMST(parent, graph);
}

int main()
{
    int graph[V][V] = {{0, 2, 0, 6, 0},
                       {2, 0, 3, 8, 5},
                       {0, 3, 0, 0, 7},
                       {6, 8, 0, 0, 9},
                       {0, 5, 7, 9, 0}};

    primMST(graph);

    return 0;
}