c++ 贪心算法
概念
贪心算法是一种在每一步选择中都选择当前最优解的算法策略。这种方法适用于某些特定问题，可以通过局部最优选择构建全局最优解。
特点
- 局部最优选择：每一步选择都选择当前看起来最优的解。
- 无后效性：当前选择不会影响未来选择的可能性。
- 可行性：必须确保每一步的选择是可行的。
优缺点
优点
- 简单易懂：贪心算法通常比其他算法（如动态规划）更简单，逻辑清晰，易于实现和理解。
- 高效：在适合的场景下，贪心算法通常具有较低的时间复杂度，能在较短时间内找到解。
- 节省空间：由于贪心算法在求解过程中不需要存储大量的中间结果，相对节省内存空间。
- 适用性广：对于一些特定类型的问题，贪心算法能够有效地找到全局最优解。
缺点
- 不适用于所有问题：贪心算法并不适用于所有问题，有些问题不能通过局部最优解得到全局最优解。
- 缺乏最优性保证：在某些情况下，贪心策略可能导致错误的结果，即找到的解不是最优解。例如，在 0-1 背包问题中，简单的贪心算法可能无法得到最优解。
- 难以分析：对于一些复杂的问题，判断贪心选择是否能导致全局最优解需要进行深入分析和证明。
- 局部最优陷阱：有时，贪心选择看似合理，但最终结果却不理想，导致程序错误或效率低下。
应用场景
-
活动选择问题
-
最小生成树
-
单源最短路径
-
背包问题
-
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;
}
总结
贪心算法虽然简单易懂，但并不是所有问题都适用。在实现贪心算法时，需要确保每一步的局部选择能够导向全局最优解。