您好,登录后才能下订单哦!
贪心算法(Greedy Algorithm)是一种在每一步选择中都采取在当前状态下最好或最优(即最有利)的选择,从而希望导致结果是全局最好或最优的算法。贪心算法并不总是能得到全局最优解,但在某些情况下,贪心算法可以得到最优解。本文将详细介绍贪心算法的基本概念、经典问题、C++实现以及实际应用。
贪心算法是一种在每一步选择中都采取在当前状态下最好或最优的选择,从而希望导致结果是全局最好或最优的算法。贪心算法并不总是能得到全局最优解,但在某些情况下,贪心算法可以得到最优解。
贪心算法适用于满足以下条件的问题:
贪心算法的基本步骤如下:
问题描述:给定一组活动,每个活动都有一个开始时间和结束时间。选择最大的互不冲突的活动集合。
贪心策略:每次选择结束时间最早的活动。
问题描述:给定一组物品,每个物品有一个重量和一个价值。在不超过背包容量的情况下,选择物品使得总价值最大。
贪心策略:每次选择单位重量价值最高的物品。
问题描述:给定一个带权的无向连通图,找到一棵生成树,使得树的所有边的权值之和最小。
贪心策略:Kruskal算法和Prim算法都是基于贪心策略的最小生成树算法。
问题描述:给定一组字符及其出现频率,构造一种编码方式,使得编码后的字符串长度最短。
贪心策略:每次选择频率最低的两个节点合并。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Activity {
int start, finish;
};
bool compare(Activity a1, Activity a2) {
return a1.finish < a2.finish;
}
void selectActivities(vector<Activity> activities) {
sort(activities.begin(), activities.end(), compare);
int i = 0;
cout << "Selected Activities: " << activities[i].start << " " << activities[i].finish << endl;
for (int j = 1; j < activities.size(); j++) {
if (activities[j].start >= activities[i].finish) {
cout << activities[j].start << " " << activities[j].finish << endl;
i = j;
}
}
}
int main() {
vector<Activity> activities = {{1, 4}, {3, 5}, {0, 6}, {5, 7}, {3, 8}, {5, 9}, {6, 10}, {8, 11}, {8, 12}, {2, 13}, {12, 14}};
selectActivities(activities);
return 0;
}
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Item {
int weight, value;
};
bool compare(Item a, Item b) {
double r1 = (double)a.value / a.weight;
double r2 = (double)b.value / b.weight;
return r1 > r2;
}
double fractionalKnapsack(int capacity, vector<Item> items) {
sort(items.begin(), items.end(), compare);
double totalValue = 0.0;
for (int i = 0; i < items.size(); i++) {
if (capacity - items[i].weight >= 0) {
capacity -= items[i].weight;
totalValue += items[i].value;
} else {
totalValue += items[i].value * ((double)capacity / items[i].weight);
break;
}
}
return totalValue;
}
int main() {
int capacity = 50;
vector<Item> items = {{10, 60}, {20, 100}, {30, 120}};
cout << "Maximum value: " << fractionalKnapsack(capacity, items) << endl;
return 0;
}
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Edge {
int src, dest, weight;
};
bool compare(Edge a, Edge b) {
return a.weight < b.weight;
}
int findParent(int parent[], int i) {
if (parent[i] == -1)
return i;
return findParent(parent, parent[i]);
}
void unionSets(int parent[], int x, int y) {
int xset = findParent(parent, x);
int yset = findParent(parent, y);
parent[xset] = yset;
}
void kruskalMST(vector<Edge> edges, int V) {
sort(edges.begin(), edges.end(), compare);
int *parent = new int[V];
fill(parent, parent + V, -1);
vector<Edge> result;
for (int i = 0; i < edges.size(); i++) {
int x = findParent(parent, edges[i].src);
int y = findParent(parent, edges[i].dest);
if (x != y) {
result.push_back(edges[i]);
unionSets(parent, x, y);
}
}
for (int i = 0; i < result.size(); i++)
cout << result[i].src << " - " << result[i].dest << " : " << result[i].weight << endl;
}
int main() {
int V = 4;
vector<Edge> edges = {{0, 1, 10}, {0, 2, 6}, {0, 3, 5}, {1, 3, 15}, {2, 3, 4}};
kruskalMST(edges, V);
return 0;
}
#include <iostream>
#include <queue>
#include <vector>
#include <string>
using namespace std;
struct Node {
char data;
int freq;
Node *left, *right;
Node(char data, int freq) {
left = right = nullptr;
this->data = data;
this->freq = freq;
}
};
struct compare {
bool operator()(Node* l, Node* r) {
return l->freq > r->freq;
}
};
void printCodes(Node* root, string str) {
if (!root)
return;
if (root->data != '$')
cout << root->data << ": " << str << endl;
printCodes(root->left, str + "0");
printCodes(root->right, str + "1");
}
void HuffmanCodes(char data[], int freq[], int size) {
Node *left, *right, *top;
priority_queue<Node*, vector<Node*>, compare> minHeap;
for (int i = 0; i < size; ++i)
minHeap.push(new Node(data[i], freq[i]));
while (minHeap.size() != 1) {
left = minHeap.top();
minHeap.pop();
right = minHeap.top();
minHeap.pop();
top = new Node('$', left->freq + right->freq);
top->left = left;
top->right = right;
minHeap.push(top);
}
printCodes(minHeap.top(), "");
}
int main() {
char arr[] = {'a', 'b', 'c', 'd', 'e', 'f'};
int freq[] = {5, 9, 12, 13, 16, 45};
int size = sizeof(arr) / sizeof(arr[0]);
HuffmanCodes(arr, freq, size);
return 0;
}
在网络路由中,贪心算法可以用于选择最短路径,以提高数据传输效率。
在任务调度中,贪心算法可以用于选择最优的任务执行顺序,以提高系统资源利用率。
在资源分配中,贪心算法可以用于选择最优的资源分配方案,以提高资源利用率。
贪心算法是一种在每一步选择中都采取在当前状态下最好或最优的选择,从而希望导致结果是全局最好或最优的算法。贪心算法并不总是能得到全局最优解,但在某些情况下,贪心算法可以得到最优解。本文详细介绍了贪心算法的基本概念、经典问题、C++实现以及实际应用。希望本文能帮助读者更好地理解和应用贪心算法。
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。