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

贪心算法实战用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; vectorActivity scheduleActivities(vectorActivity activities) { sort(activities.begin(), activities.end(), compareEndTime); vectorActivity 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() { vectorActivity 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; vectorint optimalLoading(int capacity, vectorint weights) { sort(weights.begin(), weights.end()); vectorint 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; vectorint 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 性能优化技巧对于大规模数据如n1e6可以考虑以下优化提前终止当累计重量达到capacity时立即退出循环并行排序使用C17的并行算法库加速排序内存预分配为result向量预留足够空间3. Dijkstra最短路径导航系统核心算法现代地图应用的路线规划核心就是Dijkstra算法。我们实现一个带路径记忆功能的版本3.1 邻接表实现适合稀疏图#include iostream #include vector #include queue #include climits using namespace std; vectorint dijkstra(const vectorvectorpairint, int graph, int start) { int n graph.size(); vectorint dist(n, INT_MAX); vectorint prev(n, -1); dist[start] 0; priority_queuepairint, int, vectorpairint, int, greaterpairint, 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 vectorint prev, int end) { if (end -1) return; printPath(prev, prev[end]); cout end ; } int main() { // 构建图的邻接表表示 vectorvectorpairint, 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; }3.2 复杂度对比表实现方式时间复杂度适用场景邻接矩阵O(V²)稠密图邻接表优先队列O(E VlogV)稀疏图斐波那契堆O(E VlogV)超大规模图4. 贪心算法的适用边界虽然贪心算法简洁高效但并非万能。下表对比三个案例的适用条件问题类型能否得到最优解关键前提条件活动安排能按结束时间排序最优装载能按重量排序单源最短路径能边权非负背包问题不能需要动态规划在LeetCode等算法平台中典型的贪心算法题目包括买卖股票的最佳时机II122题分发饼干455题跳跃游戏55题掌握贪心算法的核心在于培养对局部最优能否导致全局最优的直觉判断。这需要大量的实践积累——建议读者将本文代码手动实现一遍修改参数观察不同输入下的输出变化。