贪心算法（Greedy Algorithm）核心原理与实现

贪心算法（Greedy Algorithm）核心原理与实现 | 极客日志

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

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

// 排序规则：按结束时间升序
bool compare(const Activity& a, const Activity& b) {
    return a.end < b.end;
}

// 选择最多不冲突活动
vector<Activity> selectMaxActivities(vector<Activity>& activities) {
    vector<Activity> result;
    if (activities.empty()) return result;

    // 1. 按结束时间排序
    sort(activities.begin(), activities.end(), compare);

    // 2. 选择第一个活动（最早结束）
    result.push_back(activities[0]);
    int lastEnd = activities[0].end;

    // 3. 遍历后续活动，选择不冲突的（开始时间>=上一个结束时间）
    for (int i = 1; i < activities.size(); i++) {
        if (activities[i].start >= lastEnd) {
            result.push_back(activities[i]);
            lastEnd = activities[i].end; // 更新最后一个活动的结束时间
        }
    }
    return result;
}

int main() {
    vector<Activity> activities = {{1,4},{3,5},{0,6},{5,7},{3,9},{5,9},{6,10},{8,11},{8,12},{2,14},{12,16}};
    vector<Activity> selected = selectMaxActivities(activities);

    // 输出结果
    cout << "选择的活动（开始时间，结束时间）：" << endl;
    for (auto& act : selected) {
        cout << "(" << act.start << ", " << act.end << ")" << endl;
    }
    cout << "最多可选择 " << selected.size() << " 个活动" << endl;
    return 0;
}

选择的活动（开始时间，结束时间）： (1, 4) (5, 7) (8, 11) (12, 16) 最多可选择 4 个活动

#include<iostream>
#include<queue>
#include<vector>
using namespace std;

// 计算哈夫曼编码的总长度
int huffmanCodeTotalLength(const vector<int>& frequencies) {
    // 最小堆：priority_queue<Type, Container, Compare>
    priority_queue<int, vector<int>, greater<int>> minHeap;

    // 1. 将所有频率入堆
    for (int freq : frequencies) {
        minHeap.push(freq);
    }

    int totalLength = 0; // 总编码长度

    // 2. 合并节点，直到堆中只剩 1 个节点
    while (minHeap.size() > 1) {
        // 取出两个最小频率
        int first = minHeap.top(); minHeap.pop();
        int second = minHeap.top(); minHeap.pop();

        // 合并后的新节点频率
        int merged = first + second;
        totalLength += merged; // 合并节点的频率即编码长度贡献

        // 新节点入堆
        minHeap.push(merged);
    }
    return totalLength;
}

int main() {
    // 字符频率：a:5, b:9, c:12, d:13, e:16, f:45
    vector<int> frequencies = {5,9,12,13,16,45};
    int total = huffmanCodeTotalLength(frequencies);
    cout << "哈夫曼编码的总长度：" << total << endl;
    // 输出：224
    return 0;
}

#include<iostream>
#include<vector>
#include<queue>
#include<climits>
#include<stdexcept>
using namespace std;

const int INF = INT_MAX;

vector<int> dijkstra(int n, int source, const vector<vector<pair<int,int>>>& adj) {
    // 边界校验：源点合法性
    if (source < 0 || source >= n) {
        throw invalid_argument("源点超出节点范围！");
    }

    vector<int> dist(n, INF);
    dist[source] = 0;

    // 最小堆：(当前距离，节点)
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> minHeap;
    minHeap.push({0, source});

    while (!minHeap.empty()) {
        auto [currentDist, u] = minHeap.top(); // C++17 结构化绑定
        minHeap.pop();

        if (currentDist > dist[u]) continue;

        // 遍历 u 的所有邻接节点
        for (auto [v, w] : adj[u]) {
            // 松弛操作：更新 dist[v]
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                minHeap.push({dist[v], v});
            }
        }
    }
    return dist;
}

int main() {
    int n = 6; // 节点数（0~5）
    vector<vector<pair<int,int>>> adj(n); // 局部邻接表，替代全局变量

    // 构建图（边：u->v，权 w）
    adj[0].emplace_back(1,2); emplace_back(2,4);
    adj[1].emplace_back(2,1); emplace_back(3,7);
    adj[2].emplace_back(4,3);
    adj[3].emplace_back(5,1);
    adj[4].emplace_back(3,2); emplace_back(5,5);

    int source = 0;
    try {
        vector<int> dist = dijkstra(n, source, adj);

        // 输出正确结果
        cout << "源点 " << source << " 到各节点的最短距离：" << endl;
        for (int i = 0; i < n; ++i) {
            if (dist[i] == INF) {
                cout << "到节点 " << i << "：不可达" << endl;
            } else {
                cout << "到节点 " << i << "：" << dist[i] << endl;
            }
        }
    } catch (const invalid_argument& e) {
        cerr << "错误：" << e.what() << endl;
        return 1;
    }
    return 0;
}

源点 0 到各节点的最短距离：
到节点 0：0
到节点 1：2
到节点 2：3（0→1→2）
到节点 3：8（0→1→2→4→3）
到节点 4：6（0→1→2→4）
到节点 5：9（0→1→2→4→3→5）

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

// 定义边结构体
struct Edge {
    int u;     // 起点
    int v;     // 终点
    int weight;// 边权
};

// 并查集（Union-Find）：维护连通分量
class UnionFind {
private:
    vector<int> parent; // 父节点
    vector<int> rank;   // 秩（用于路径压缩优化）
public:
    UnionFind(int n) {
        parent.resize(n);
        rank.resize(n, 0);
        for (int i = 0; i < n; i++) {
            parent[i] = i; // 初始父节点为自身
        }
    }

    // 查找根节点（路径压缩）
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // 递归压缩路径
        }
        return parent[x];
    }

    // 合并两个连通分量（按秩合并）
    bool unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX == rootY) return false; // 已在同一分量

        // 秩小的树合并到秩大的树
        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else {
            parent[rootY] = rootX;
            if (rank[rootX] == rank[rootY]) {
                rank[rootX]++;
            }
        }
        return true;
    }
};

// Kruskal 算法：返回 MST 的总边权
int kruskal(int n, vector<Edge>& edges) {
    // 1. 按边权升序排序
    sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {
        return a.weight < b.weight;
    });

    UnionFind uf(n);
    int mstTotal = 0; // MST 总边权
    int edgeCount = 0; // 已选边数

    // 2. 遍历边，选择不构成环的边
    for (auto& edge : edges) {
        if (uf.unite(edge.u, edge.v)) {
            mstTotal += edge.weight;
            edgeCount++; // MST 需 n-1 条边，提前退出
            if (edgeCount == n - 1) break;
        }
    }

    // 若边数不足 n-1，说明图不连通
    return (edgeCount == n - 1) ? mstTotal : -1;
}

int main() {
    int n = 5; // 节点数（0~4）
    vector<Edge> edges = {{0,1,2},{0,3,6},{1,2,3},{1,3,8},{1,4,5},{2,4,7},{3,4,9}};
    int mstTotal = kruskal(n, edges);

    if (mstTotal == -1) {
        cout << "图不连通，无法构建 MST" << endl;
    } else {
        cout << "最小生成树的总边权：" << mstTotal << endl; // 输出：16
    }
    return 0;
}

对比维度	贪心算法（Greedy）	动态规划（DP）
核心思想	局部最优→全局最优，不回溯	存储子问题最优解，回溯推导全局最优
子问题处理	不存储子问题解，每步直接选最优	存储子问题解（如 dp 数组），避免重复计算
适用场景	满足'贪心选择性质'的问题	不满足贪心选择性质，但有最优子结构
时间复杂度	低（通常 O(nlogn)，排序主导）	较高（通常 O(n²) 或 O(nm)）
典型问题	活动选择、哈夫曼编码、Dijkstra	0-1 背包、最长公共子序列、斐波那契
最优解保证	需证明策略正确性，否则不保证	只要状态转移正确，必为全局最优

贪心算法（Greedy Algorithm）核心原理与实现

一、贪心算法的核心定义与本质

二、贪心算法的适用条件

1. 贪心选择性质

2. 最优子结构性质

3. 经典反例：错误的贪心策略

三、贪心算法的解题步骤

四、经典问题与 C++ 实现

1. 活动选择问题（最多不冲突活动）

问题描述

贪心策略

C++ 实现

输出结果

2. 哈夫曼编码（最优前缀编码）

问题描述

贪心策略

C++ 实现

原理说明

3. Dijkstra 算法（单源最短路径）

问题描述

贪心策略

C++ 实现

输出结果

4. Kruskal 算法（最小生成树）

问题描述

贪心策略

C++ 实现

原理说明

五、贪心算法与动态规划的对比

六、贪心算法的优缺点与应用场景

1. 优点

2. 缺点

3. 实际应用

更多推荐文章

相关免费在线工具

贪心算法（Greedy Algorithm）核心原理与实现

一、贪心算法的核心定义与本质

二、贪心算法的适用条件

1. 贪心选择性质

2. 最优子结构性质

3. 经典反例：错误的贪心策略

三、贪心算法的解题步骤

四、经典问题与 C++ 实现

1. 活动选择问题（最多不冲突活动）

问题描述

贪心策略

C++ 实现

输出结果

2. 哈夫曼编码（最优前缀编码）

问题描述

贪心策略

C++ 实现

原理说明

3. Dijkstra 算法（单源最短路径）

问题描述

贪心策略

C++ 实现

输出结果

4. Kruskal 算法（最小生成树）

问题描述

贪心策略

C++ 实现

原理说明

五、贪心算法与动态规划的对比

六、贪心算法的优缺点与应用场景

1. 优点

2. 缺点

3. 实际应用

微信扫一扫，关注极客日志

更多推荐文章

相关免费在线工具