用c++写一个贪心算法的例子

以下是一个使用贪心算法解决集合覆盖问题的 C 语言代码示例：

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

// 集合覆盖问题：选择最少的广播台，覆盖全州各地
int main(void)
{
    // 各个广播台覆盖的地区
    const char *states_needed[] = {"mt", "wa", "or", "id", "nv", "ut", "ca", "az"};
    const int num_states_needed = 8;

    const char *stations[][5] = {
        {"id", "nv", "ut"},                         // k1
        {"wa", "id", "mt"},                         // k2
        {"or", "nv", "ca"},                         // k3
        {"nv", "ut"},                               // k4
        {"ca", "az"}                                // k5
    };
    const int num_stations = 5;

    bool states_covered[num_states_needed];
    for (int i = 0; i < num_states_needed; ++i)
        states_covered[i] = false;

    // 选择的广播台
    int stations_selected[num_stations];
    int num_stations_selected = 0;

    while (true) {
        // 选择覆盖最多未覆盖地区的广播台
        int max_covered = 0;
        int max_station = -1;
        for (int i = 0; i < num_stations; ++i) {
            int num_covered = 0;
            for (int j = 0; j < 5; ++j) {
                for (int k = 0; k < num_states_needed; ++k) {
                    if (strcmp(stations[i][j], states_needed[k]) == 0 && !states_covered[k]) {
                        ++num_covered;
                        break;
                    }
                }
            }
            if (num_covered > max_covered) {
                max_covered = num_covered;
                max_station = i;
            }
        }

        if (max_station == -1)
            break;

        // 将该广播台覆盖的地区标记为已覆盖
        for (int i = 0; i < 5; ++i) {
            for (int j = 0; j < num_states_needed; ++j) {
                if (strcmp(stations[max_station][i], states_needed[j]) == 0) {
                    states_covered[j] = true;
                    break;
                }
            }
        }

        // 记录选择的广播台
        stations_selected[num_stations_selected++] = max_station;
    }

    // 输出选择的广播台
    printf("Selected stations: ");
    for (int i = 0; i < num_stations_selected; ++i)
        printf("k%d ", stations_selected[i] + 1);
    printf("\n");

    return 0;
}

该代码实现了一个简单的集合覆盖问题解决方案，其中：

- `states_needed` 数组存储了需要覆盖的各地区，`num_states_needed` 记录了需要覆盖的地区数量。
- `stations` 数组存储了各个广播台覆盖的地区，`num_stations` 记录了广播台的数量。
- `states_covered` 数组记录了各个地区是否已经被覆盖。
- `stations_selected` 数组记录了选择的广播台的编号，`num_stations_selected` 记录了选择的广播台数量。
- 在 `while` 循环中，通过遍历广播台，找到能够覆盖最多未覆盖地区的广播台，并将其覆盖的地区标记为已覆盖，同时记录选择的广播台编号，直到所有地区都被覆盖，或者找不到能够覆盖任何未覆盖地区的广播台为止。