C++贪心算法怎么应用

发布时间:2022-03-25 09:16:17 作者:iii
来源:亿速云 阅读:220

C++贪心算法怎么应用

目录

  1. 引言
  2. 贪心算法的基本概念
  3. 贪心算法的基本步骤
  4. 贪心算法的经典问题
  5. C++实现贪心算法
  6. 贪心算法的优缺点
  7. 贪心算法与其他算法的比较
  8. 实际应用中的贪心算法
  9. 总结

引言

贪心算法(Greedy Algorithm)是一种在每一步选择中都采取在当前状态下最好或最优(即最有利)的选择,从而希望导致结果是全局最好或最优的算法。贪心算法并不总是能得到全局最优解,但在某些情况下,贪心算法可以得到最优解。本文将详细介绍贪心算法的基本概念、经典问题、C++实现以及实际应用。

贪心算法的基本概念

2.1 贪心算法的定义

贪心算法是一种在每一步选择中都采取在当前状态下最好或最优的选择,从而希望导致结果是全局最好或最优的算法。贪心算法并不总是能得到全局最优解,但在某些情况下,贪心算法可以得到最优解。

2.2 贪心算法的特点

2.3 贪心算法的适用条件

贪心算法适用于满足以下条件的问题:

  1. 最优子结构:问题的最优解包含其子问题的最优解。
  2. 贪心选择性质:通过局部最优选择可以达到全局最优解。

贪心算法的基本步骤

贪心算法的基本步骤如下:

  1. 问题建模:将问题抽象为一个数学模型。
  2. 选择策略:确定每一步的局部最优选择策略。
  3. 求解:按照选择策略逐步求解问题。
  4. 验证:验证最终解是否为全局最优解。

贪心算法的经典问题

4.1 活动选择问题

问题描述:给定一组活动,每个活动都有一个开始时间和结束时间。选择最大的互不冲突的活动集合。

贪心策略:每次选择结束时间最早的活动。

4.2 背包问题

问题描述:给定一组物品,每个物品有一个重量和一个价值。在不超过背包容量的情况下,选择物品使得总价值最大。

贪心策略:每次选择单位重量价值最高的物品。

4.3 最小生成树问题

问题描述:给定一个带权的无向连通图,找到一棵生成树,使得树的所有边的权值之和最小。

贪心策略:Kruskal算法和Prim算法都是基于贪心策略的最小生成树算法。

4.4 哈夫曼编码

问题描述:给定一组字符及其出现频率,构造一种编码方式,使得编码后的字符串长度最短。

贪心策略:每次选择频率最低的两个节点合并。

C++实现贪心算法

5.1 活动选择问题的C++实现

#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;
}

5.2 背包问题的C++实现

#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;
}

5.3 最小生成树问题的C++实现

#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;
}

5.4 哈夫曼编码的C++实现

#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;
}

贪心算法的优缺点

6.1 优点

6.2 缺点

贪心算法与其他算法的比较

7.1 贪心算法与动态规划

7.2 贪心算法与分治法

实际应用中的贪心算法

8.1 网络路由

在网络路由中,贪心算法可以用于选择最短路径,以提高数据传输效率。

8.2 任务调度

在任务调度中,贪心算法可以用于选择最优的任务执行顺序,以提高系统资源利用率。

8.3 资源分配

在资源分配中,贪心算法可以用于选择最优的资源分配方案,以提高资源利用率。

总结

贪心算法是一种在每一步选择中都采取在当前状态下最好或最优的选择,从而希望导致结果是全局最好或最优的算法。贪心算法并不总是能得到全局最优解,但在某些情况下,贪心算法可以得到最优解。本文详细介绍了贪心算法的基本概念、经典问题、C++实现以及实际应用。希望本文能帮助读者更好地理解和应用贪心算法。

推荐阅读:
  1. c++中的贪心算法怎么实现
  2. C++贪心算法实现活动安排问题(实例代码)

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

c++

上一篇:如何使用Python实现字典合并

下一篇:JUC并发编程中进程与线程的示例分析

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》