当前位置：首页 > news >正文

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

news 2026/6/11 4:18:53

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

在算法学习的道路上，贪心算法总是让人又爱又恨——它思路简洁却暗藏玄机，代码精炼但边界条件极易出错。本文将带你用C++手撕三个经典贪心问题：活动安排、最优装载和Dijkstra最短路径。不同于教科书式的理论讲解，我们直接从工程视角出发，每个案例都提供：

可直接编译的完整代码（含标准输入输出处理）
典型测试数据集（避免自己构造数据的麻烦）
常见编译/运行时错误解决方案
关键代码段的逐行解析

1. 活动安排问题：会议室争夺战

假设你是一家创业公司的技术主管，需要为10个团队安排会议室使用时段。每个团队提交的时间段可能有重叠，如何最大化会议室利用率？这就是典型的活动安排问题。

1.1 问题建模与核心思路

贪心策略：优先选择结束时间最早的活动，为后续安排留出更多时间。这就像在自助餐厅取餐——先拿最快吃完的菜品，才能品尝更多种类。

struct Activity { int id; int start; int end; }; bool compareEndTime(const Activity &a, const Activity &b) { return a.end < b.end; // 按结束时间升序排序 }

1.2 完整实现与陷阱规避

以下代码包含三个新手常踩的坑：

#include <iostream> #include <vector> #include <algorithm> using namespace std; vector<Activity> scheduleActivities(vector<Activity>& activities) { sort(activities.begin(), activities.end(), compareEndTime); vector<Activity> selected; int lastEnd = -1; for (const auto& act : activities) { if (act.start >= lastEnd) { selected.push_back(act); lastEnd = act.end; // 特别注意：这里必须更新为当前活动的结束时间 // 常见错误：错误更新为act.start } } return selected; } 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} }; auto result = scheduleActivities(activities); cout << "最多可安排活动数: " << result.size() << endl; for (const auto& act : result) { cout << "活动" << act.id << ": [" << act.start << ", " << act.end << "]" << endl; } return 0; }

注意：当存在多个活动同时满足条件时，上述代码会选择最先遇到的一个。如果需要最优解，应确保输入数据已按结束时间严格排序。

1.3 复杂度对比

操作	时间复杂度	空间复杂度
排序	O(nlogn)	O(1)
贪心选择	O(n)	O(n)
总复杂度	O(nlogn)	O(n)

2. 最优装载问题：货轮配载优化

假设你负责港口货运调度，一艘货轮载重为C，现有N个集装箱重量分别为[w1,w2,...,wn]。如何在不超过承重前提下装载最多集装箱？

2.1 算法实现与工程细节

#include <iostream> #include <vector> #include <algorithm> using namespace std; vector<int> optimalLoading(int capacity, vector<int>& weights) { sort(weights.begin(), weights.end()); vector<int> loaded; int currentLoad = 0; for (int i = 0; i < weights.size(); ++i) { if (currentLoad + weights[i] <= capacity) { loaded.push_back(weights[i]); currentLoad += weights[i]; } else { break; // 后续货物更重，无需继续检查 } } return loaded; } int main() { int capacity = 12; vector<int> weights = {8, 4, 2, 5, 7}; auto result = optimalLoading(capacity, weights); cout << "可装载集装箱数: " << result.size() << endl; cout << "具体重量: "; for (int w : result) cout << w << " "; cout << endl; return 0; }

常见调试场景：

当所有集装箱总重不超过capacity时，应全部装载
当最轻集装箱已超重时，应返回空集
存在多个相同重量集装箱时的处理

2.2 性能优化技巧

对于大规模数据（如n>1e6），可以考虑以下优化：

提前终止：当累计重量达到capacity时立即退出循环
并行排序：使用C++17的并行算法库加速排序
内存预分配：为result向量预留足够空间

3. Dijkstra最短路径：导航系统核心算法

现代地图应用的路线规划核心就是Dijkstra算法。我们实现一个带路径记忆功能的版本：

3.1 邻接表实现（适合稀疏图）

#include <iostream> #include <vector> #include <queue> #include <climits> using namespace std; vector<int> dijkstra(const vector<vector<pair<int, int>>>& graph, int start) { int n = graph.size(); vector<int> dist(n, INT_MAX); vector<int> prev(n, -1); dist[start] = 0; priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; pq.push({0, start}); while (!pq.empty()) { auto [currentDist, u] = pq.top(); pq.pop(); if (currentDist > dist[u]) continue; for (const auto& [v, weight] : graph[u]) { if (dist[v] > dist[u] + weight) { dist[v] = dist[u] + weight; prev[v] = u; pq.push({dist[v], v}); } } } return dist; } void printPath(const vector<int>& prev, int end) { if (end == -1) return; printPath(prev, prev[end]); cout << end << " "; } int main() { // 构建图的邻接表表示 vector<vector<pair<int, int>>> graph = { {{1, 2}, {3, 1}, {5, 3}}, // 节点0 {{4, 5}, {2, 6}}, // 节点1 {{7, 6}}, // 节点2 {{1, 10}, {6, 2}}, // 节点3 {{2, 9}, {7, 4}}, // 节点4 {{3, 5}, {6, 4}}, // 节点5 {{4, 3}, {1, 7}, {7, 8}}, // 节点6 {} // 节点7 }; auto distances = dijkstra(graph, 0); cout << "从节点0出发的最短距离:" << endl; for (int i = 0; i < distances.size(); ++i) { cout << "到节点" << i << ": " << distances[i] << endl; } return 0; }