贪心算法实战：用C++搞定活动安排、最优装载和Dijkstra最短路径（附完整可运行代码）

贪心算法就像一位精明的商人，每次交易都选择当下最有利的方案。这种"眼前最优"的策略虽然不能保证全局最优，但在许多实际问题中展现出惊人的效率。本文将带你用C++实现三个经典贪心算法案例，每个案例都配有可直接运行的代码和实战技巧。

1. 活动安排问题：最大化你的时间价值

假设你是个忙碌的自由职业者，手头有10个项目邀约，每个项目都有固定的时间窗口。如何选择最多数量的项目而不发生时间冲突？这就是典型的活动安排问题。

核心贪心策略 ：优先选择最早结束的活动，为后续安排留出更多时间。

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

struct Activity {
    int id;
    int start;
    int end;
};

bool compareEndTime(const Activity &a, const Activity &b) {
    return a.end < b.end;
}

void scheduleActivities(vector<Activity> &activities) {
    sort(activities.begin(), activities.end(), compareEndTime);
    
    vector<Activity> selected;
    selected.push_back(activities[0]);
    int lastEnd = activities[0].end;
    
    for(int i = 1; i < activities.size(); i++) {
        if(activities[i].start >= lastEnd) {
            selected.push_back(activities[i]);
            lastEnd = activities[i].end;
        }
    }
    
    cout << "最多可安排活动数量: " << selected.size() << endl;
    cout << "活动ID\t开始\t结束" << endl;
    for(auto &act : selected) {
        cout << act.id << "\t" << act.start << "\t" << act.end << endl;
    }
}

int main() {
    vector<Activity> activities = {
        {1, 1, 4}, {2, 3, 5}, {3, 2, 6},
        {4, 5, 7}, {5, 3, 8}, {6, 5, 9},
        {7, 6, 10}, {8, 8, 11}, {9, 8, 12},
        {10, 2, 13}
    };
    
    scheduleActivities(activities);
    return 0;
}

调试提示：如果遇到段错误，检查输入数据是否为空。在实际应用中，建议添加输入验证。

时间复杂度分析 ：

• 排序：O(n log n)
• 选择活动：O(n)
• 总复杂度：O(n log n)

2. 最优装载问题：集装箱装船的智慧

假设你负责港口货运，需要将一批集装箱装上货轮。轮船载重有限，如何装载最多数量的集装箱？这就是最优装载问题。

贪心选择 ：优先装重量最轻的集装箱。

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

struct Container {
    int id;
    int weight;
};

bool compareWeight(const Container &a, const Container &b) {
    return a.weight < b.weight;
}

void loadContainers(vector<Container> &containers, int capacity) {
    sort(containers.begin(), containers.end(), compareWeight);
    
    vector<int> loaded;
    int totalWeight = 0;
    
    for(auto &cont : containers) {
        if(totalWeight + cont.weight <= capacity) {
            loaded.push_back(cont.id);
            totalWeight += cont.weight;
        } else {
            break;
        }
    }
    
    cout << "可装载集装箱数量: " << loaded.size() << endl;
    cout << "集装箱ID: ";
    for(auto id : loaded) cout << id << " ";
    cout << endl;
}

int main() {
    vector<Container> containers = {
        {1, 8}, {2, 4}, {3, 2}, 
        {4, 5}, {5, 7}
    };
    int capacity = 12;
    
    loadContainers(containers, capacity);
    return 0;
}

常见错误及修复 ：

1. 忘记排序：导致无法优先选择轻量集装箱
2. 边界条件：当第一个集装箱就超重时，应返回0
3. 浮点数比较：如果重量是浮点数，应使用容差比较

3. Dijkstra算法：寻找最短路径的导航专家

当你使用地图APP寻找最短路线时，背后很可能就是Dijkstra算法在工作。它从起点开始，逐步扩展到距离最近的节点，直到覆盖所有目的地。

算法核心 ：

• 维护两个集合：已确定最短路径的节点集合S和未确定的集合V-S
• 每次从V-S中选择距离起点最近的节点加入S
• 更新该节点邻居的最短距离估计

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

const int INF = INT_MAX;

void dijkstra(vector<vector<pair<int, int>>> &graph, int start) {
    int n = graph.size();
    vector<int> dist(n, INF);
    vector<bool> visited(n, false);
    
    dist[start] = 0;
    
    for(int i = 0; i < n-1; i++) {
        int u = -1;
        for(int v = 0; v < n; v++) {
            if(!visited[v] && (u == -1 || dist[v] < dist[u])) {
                u = v;
            }
        }
        
        if(dist[u] == INF) break;
        visited[u] = true;
        
        for(auto &edge : graph[u]) {
            int v = edge.first;
            int weight = edge.second;
            if(dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
            }
        }
    }
    
    cout << "顶点\t距离" << endl;
    for(int i = 0; i < n; i++) {
        cout << i << "\t" << dist[i] << endl;
    }
}

int main() {
    int nodes = 8;
    vector<vector<pair<int, int>>> graph(nodes);
    
    // 构建图
    graph[0].push_back({1, 2});
    graph[0].push_back({3, 1});
    graph[0].push_back({5, 3});
    graph[1].push_back({4, 5});
    graph[1].push_back({2, 6});
    graph[2].push_back({7, 6});
    graph[3].push_back({1, 10});
    graph[3].push_back({6, 2});
    graph[4].push_back({2, 9});
    graph[4].push_back({7, 4});
    graph[5].push_back({3, 5});
    graph[5].push_back({6, 4});
    graph[6].push_back({4, 3});
    graph[6].push_back({1, 7});
    graph[6].push_back({7, 8});
    
    dijkstra(graph, 0);
    return 0;
}

性能优化技巧 ：

1. 使用优先队列可将时间复杂度从O(V²)降到O(E + V log V)
2. 对于稀疏图，邻接表比邻接矩阵更节省空间
3. 提前终止：如果只需要到特定节点的最短路径，找到后即可终止

4. 贪心算法的适用场景与陷阱

虽然贪心算法简洁高效，但并非万能。理解其适用条件至关重要。

适用条件 ：

• 贪心选择性质：局部最优能导致全局最优
• 最优子结构：问题的最优解包含子问题的最优解

典型适用场景 ：

1. 霍夫曼编码
2. 最小生成树（Prim和Kruskal算法）
3. 找零钱问题（特定面额）

常见陷阱 ：

1. 0-1背包问题：贪心法不能保证最优
2. 旅行商问题：贪心策略可能得到很差的结果
3. 需要全局考量的复杂约束问题

对比表格：三种算法的关键特征

算法	时间复杂度	空间复杂度	适用场景
活动安排	O(n log n)	O(n)	时间区间调度
最优装载	O(n log n)	O(n)	资源有限装载
Dijkstra	O(V²)	O(V+E)	非负权图最短路径

在实际面试中，经常会被要求手写这些算法的变种。例如，活动安排问题可能变为"每个活动有不同价值，求最大总价值"，这时贪心法就不再适用，需要动态规划。