c++ 贪心算法

news/2024/11/6 13:24:18/

概念

贪心算法是一种在每一步选择中都选择当前最优解的算法策略。这种方法适用于某些特定问题,可以通过局部最优选择构建全局最优解。

特点

  1. 局部最优选择:每一步选择都选择当前看起来最优的解。
  2. 无后效性:当前选择不会影响未来选择的可能性。
  3. 可行性:必须确保每一步的选择是可行的。

优缺点

优点

  1. 简单易懂贪心算法通常比其他算法(如动态规划)更简单,逻辑清晰,易于实现和理解。
  2. 高效:在适合的场景下,贪心算法通常具有较低的时间复杂度,能在较短时间内找到解。
  3. 节省空间:由于贪心算法在求解过程中不需要存储大量的中间结果,相对节省内存空间。
  4. 适用性广:对于一些特定类型的问题,贪心算法能够有效地找到全局最优解。

缺点

  1. 不适用于所有问题贪心算法并不适用于所有问题,有些问题不能通过局部最优解得到全局最优解。
  2. 缺乏最优性保证:在某些情况下,贪心策略可能导致错误的结果,即找到的解不是最优解。例如,在 0-1 背包问题中,简单的贪心算法可能无法得到最优解。
  3. 难以分析:对于一些复杂的问题,判断贪心选择是否能导致全局最优解需要进行深入分析和证明。
  4. 局部最优陷阱:有时,贪心选择看似合理,但最终结果却不理想,导致程序错误或效率低下。

应用场景

  • 活动选择问题

  • 最小生成树

  • 单源最短路径

  • 背包问题

  • Huffman 编码

活动选择问题

问题描述:给定一组活动,选择不重叠的活动以最大化活动数量。

#include <iostream>
#include <vector>
#include <algorithm>struct Activity {int start;int end;
};bool compare(Activity a1, Activity a2) {return a1.end < a2.end;
}void activitySelection(std::vector<Activity>& activities) {std::sort(activities.begin(), activities.end(), compare);std::cout << "选择的活动: \n";int lastEndTime = -1;for (const auto& activity : activities) {if (activity.start >= lastEndTime) {std::cout << "活动(" << activity.start << ", " << activity.end << ")\n";lastEndTime = activity.end;}}
}int main() {std::vector<Activity> activities = {{1, 3}, {2, 5}, {4, 6}, {6, 7}, {5, 8}, {8, 9}};activitySelection(activities);return 0;
}

最小生成树(Kruskal 算法)

问题描述:给定一个带权无向图,找到最小生成树。

#include <iostream>
#include <vector>
#include <algorithm>struct Edge {int src, dest, weight;
};bool compare(Edge e1, Edge e2) {return e1.weight < e2.weight;
}class DisjointSet {
public:DisjointSet(int n) : parent(n), rank(n, 0) {for (int i = 0; i < n; ++i) parent[i] = i;}int find(int u) {if (u != parent[u])parent[u] = find(parent[u]);return parent[u];}void unionSets(int u, int v) {int rootU = find(u);int rootV = find(v);if (rootU != rootV) {if (rank[rootU] < rank[rootV]) {parent[rootU] = rootV;} else if (rank[rootU] > rank[rootV]) {parent[rootV] = rootU;} else {parent[rootV] = rootU;rank[rootU]++;}}}
private:std::vector<int> parent;std::vector<int> rank;
};void kruskal(int n, std::vector<Edge>& edges) {std::sort(edges.begin(), edges.end(), compare);DisjointSet ds(n);std::cout << "最小生成树的边:\n";for (const auto& edge : edges) {if (ds.find(edge.src) != ds.find(edge.dest)) {ds.unionSets(edge.src, edge.dest);std::cout << edge.src << " - " << edge.dest << " (权重: " << edge.weight << ")\n";}}
}int main() {int n = 4; // 顶点数std::vector<Edge> edges = {{0, 1, 10}, {0, 2, 6}, {0, 3, 5},{1, 3, 15}, {2, 3, 4}};kruskal(n, edges);return 0;
}

单源最短路径(Dijkstra 算法)

问题描述:在带权图中,找到从源节点到其他所有节点的最短路径。

#include <iostream>
#include <vector>
#include <queue>
#include <climits>typedef std::pair<int, int> Pair; // (距离, 节点)void dijkstra(int src, const std::vector<std::vector<Pair>>& graph) {int n = graph.size();std::vector<int> dist(n, INT_MAX);dist[src] = 0;std::priority_queue<Pair, std::vector<Pair>, std::greater<Pair>> pq;pq.push({0, src}); // (距离, 节点)while (!pq.empty()) {int u = pq.top().second;pq.pop();for (const auto& edge : graph[u]) {int v = edge.first;int weight = edge.second;if (dist[u] + weight < dist[v]) {dist[v] = dist[u] + weight;pq.push({dist[v], v});}}}std::cout << "从源节点 " << src << " 到其他节点的最短路径:\n";for (int i = 0; i < n; ++i) {std::cout << "到节点 " << i << " 的距离: " << dist[i] << "\n";}
}int main() {std::vector<std::vector<Pair>> graph = {{{1, 1}, {2, 4}},{{2, 2}, {3, 6}},{{3, 3}},{}};dijkstra(0, graph);return 0;
}

0-1 背包问题(动态规划与贪心结合)

问题描述:给定一组物品,每个物品有重量和价值,目标是最大化背包内物品的总价值。

#include <iostream>
#include <vector>
#include <algorithm>struct Item {int value;int weight;
};bool compare(Item a, Item b) {return (double)a.value / a.weight > (double)b.value / b.weight;
}double fractionalKnapsack(std::vector<Item>& items, int capacity) {std::sort(items.begin(), items.end(), compare);double totalValue = 0.0;for (const auto& item : items) {if (capacity == 0) break;if (item.weight <= capacity) {capacity -= item.weight;totalValue += item.value;} else {totalValue += item.value * ((double)capacity / item.weight);capacity = 0;}}return totalValue;
}int main() {std::vector<Item> items = {{60, 10}, {100, 20}, {120, 30}};int capacity = 50;double maxValue = fractionalKnapsack(items, capacity);std::cout << "最大价值: " << maxValue << "\n";return 0;
}

Huffman 编码

问题描述:给定一组字符及其频率,构建最优的前缀编码。

#include <iostream>
#include <queue>
#include <unordered_map>
#include <vector>struct Node {char ch;int freq;Node* left;Node* right;Node(char character, int frequency) : ch(character), freq(frequency), left(nullptr), right(nullptr) {}
};struct Compare {bool operator()(Node* l, Node* r) {return l->freq > r->freq;}
};void printCodes(Node* root, std::string str) {if (!root) return;if (!root->left && !root->right) {std::cout << root->ch << ": " << str << "\n";}printCodes(root->left, str + "0");printCodes(root->right, str + "1");
}void huffmanCoding(const std::unordered_map<char, int>& freqMap) {std::priority_queue<Node*, std::vector<Node*>, Compare> minHeap;for (const auto& pair : freqMap) {minHeap.push(new Node(pair.first, pair.second));}while (minHeap.size() > 1) {Node* left = minHeap.top(); minHeap.pop();Node* right = minHeap.top(); minHeap.pop();Node* newNode = new Node('$', left->freq + right->freq);newNode->left = left;newNode->right = right;minHeap.push(newNode);}Node* root = minHeap.top();std::cout << "Huffman 编码:\n";printCodes(root, "");
}int main() {std::unordered_map<char, int> freqMap = {{'a', 5}, {'b', 9}, {'c', 12}, {'d', 13}, {'e', 16}, {'f', 45}};huffmanCoding(freqMap);return 0;
}

总结

贪心算法虽然简单易懂,但并不是所有问题都适用。在实现贪心算法时,需要确保每一步的局部选择能够导向全局最优解。


http://www.ppmy.cn/news/1544822.html

相关文章

商品满减、限时活动、折扣活动的计算最划算 golang

可以对商品的不同活动&#xff08;如满减、限时价和折扣&#xff09;进行分组&#xff0c;并在购物车中显示各个活动标签下的最优价格组合。以下代码将商品按活动类别进行分组计算&#xff0c;并输出在购物车中的显示信息。 package mainimport ("fmt""math&qu…

c语言简单编程练习10

1、typedef和#define的区别 在用作数据类型替换时的区别&#xff1a; #include <stdio.h> #include <unistd.h>typedef char * A; //typedef需要&#xff1b; #define B char *int main(int argc, char *argv[]) {A a,b;B c,d;printf("a_size%ld\n"…

浅析Android Handler机制实现原理

0. 背景描述 Android系统出于对简单、高效的考虑&#xff0c;在设计UI体系时采用了单线程模型&#xff0c;即不会在多个线程中对同一个UI界面执行操作。简单是指单线程模型可以不用考虑和处理在多线程环境下操作UI带来的线程安全问题&#xff0c;高效是指单线程模型下无需通过…

视频一键转换3D:Autodesk 发布 Video to 3D Scene

Video 3D Scene 最近 Autodesk 旗下公司 Wonder Dynamics 推出了 Wonder Animation 的测试版&#xff0c;它使用突破性的视频到 3D 场景技术&#xff0c;通过将任何视频序列转换为 3D 动画场景来加速动画电影的制作。 Video 3D Scene Video 3D Scene 生成效果 作为 Wonder Stud…

了解分布式数据库系统中的CAP定理

在分布式数据库系统的设计和实现中&#xff0c;CAP定理是一个至关重要的概念。CAP定理&#xff0c;全称为一致性&#xff08;Consistency&#xff09;、可用性&#xff08;Availability&#xff09;和分区容忍性&#xff08;Partition tolerance&#xff09;定理&#xff0c;由…

求职经验分享

更多详情&#xff1a;爱米的前端小笔记&#xff0c;更多前端内容&#xff0c;等你来看&#xff01;这些都是利用下班时间整理的&#xff0c;整理不易&#xff0c;大家多多&#x1f44d;&#x1f49b;➕&#x1f914;哦&#xff01;你们的支持才是我不断更新的动力&#xff01;找…

爬虫技术——小白入狱案例

知孤云出岫 目录 1. 案例概述2. 案例需求分析3. 实现步骤Step 1: 环境准备Step 2: 分析百度图片URL请求规律Step 3: 编写爬虫代码代码解析 4. 运行代码5. 注意事项6. 案例总结 要实现大批量爬取百度图片&#xff0c;可以使用Python编写一个网络爬虫&#xff0c;通过发送HTTP请求…

如何使用Puppeteer和Node.js爬取大学招生数据:入门指南

1. 引言 在数据驱动的时代&#xff0c;招生数据为学生和教育机构提供了许多宝贵的信息。通过分析和挖掘各大学的招生数据&#xff08;如录取率、标准化考试分数、班级排名和高中平均绩点&#xff09;&#xff0c;不仅能帮助学生做出合理的选择&#xff0c;还能为教育政策的制定…