[数据结构与算法]贪心算法（原理+代码）

#include <iostream>
#include <climits>
using namespace std;
 
#define V 5  // 顶点数
 
int minKey(int key[], bool mstSet[]) {
    int min = INT_MAX, min_index;
 
    for (int v = 0; v < V; v++) {
        if (!mstSet[v] && key[v] < min) {
            min = key[v];
            min_index = v;
        }
    }
 
    return min_index;
}
 
void printMST(int parent[], int graph[V][V]) {
    cout << "Minimum Spanning Tree (Prim):" << endl;
    for (int i = 1; i < V; i++)
        cout << "Edge: " << parent[i] << " - " << i << " Weight: " << graph[i][parent[i]] << endl;
}
 
void primMST(int graph[V][V]) {
    int parent[V];
    int key[V];
    bool mstSet[V];
 
    // 初始化所有键值为无穷大，都未包含在生成树中
    for (int i = 0; i < V; i++) {
        key[i] = INT_MAX;
        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] && 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;
}

#include <iostream>
#include <algorithm>
#include <vector>
 
using namespace std;
 
// 首先声明一个活动结构体，包含活动开始时间和结束时间两个变量
struct Activity {
    int start, finish;
};
 
// 按照活动结束时间升序排序的比较函数
bool compare(Activity a, Activity b) {
    return (a.finish < b.finish);
}
 
// 贪心算法解决活动选择问题
void printMaxActivities(Activity activities[], int n) {
    // 按照结束时间升序排序
    sort(activities, activities + n, compare);
 
    cout << "Selected Activities:\n";
 
    // 第一个活动总是被选中
    int i = 0;
    cout << "(" << activities[i].start << ", " << activities[i].finish << "), ";
 
    // 遍历剩余活动
    for (int j = 1; j < n; j++) {
        // 如果当前活动的开始时间大于等于上一个选中活动的结束时间，选择当前活动
        if (activities[j].start >= activities[i].finish) {
            cout << "(" << activities[j].start << ", " << activities[j].finish << "), ";
            i = j;
        }
    }
}
 
int main() {
    // 示例活动数据（活动开始实践和结束时间）
    Activity activities[] = {{1, 2}, {3, 4}, {0, 6}, {5, 7}, {8, 9}, {5, 9}};
    int n = sizeof(activities) / sizeof(activities[0]);
 
    // 调用贪心算法解决活动选择问题
    printMaxActivities(activities, n);
 
    return 0;
}