c++ 贪心算法

🕗 发布于 2024-11-04 13:26 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;
}

总结

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

原文地址：https://blog.csdn.net/www_dong/article/details/143470013

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：安娜的档案(Anna’s Archive) 镜像网站/国内最新可访问入口（持续更新）
下一篇：[LeetCode] 1137. 第N个泰波那契数

Flink学习连载文档第一篇--Flink集群的安装
Flink支持多种安装模式。local（本地）——本地模式standalone——独立模式，Flink自带集群，开发测试环境使用standaloneHA—独立集群高可用模式，Flink自带集群，开发测
阅读更多2024-11-22
小R的随机播放顺序
小R有一个特殊的随机播放规则。他首先播放歌单中的第一首歌，播放后将其从歌单中移除。如果歌单中还有歌曲，则会将当前第一首歌移到最后一首。这个过程会一直重复，直到歌单中没有任何歌曲。为了实现这个播放规则，
阅读更多2024-11-22
【无标题】
shell脚本判断服务是否安装及运行状态。
阅读更多2024-11-22
R语言debug01-安装bibliometrix出现错误
使用install.packages(“webshot2”)是可以打开成功的，但是仍然出现报错！在一台新电脑上安装bibliometrix，因为有经验，觉得不会出什么问题。更新重新安装都尝试了，仔细
阅读更多2024-11-22
单例模式与QT中的C++实现
单例模式在Qt中的实现
阅读更多2024-11-22
C语言菜鸟入门·关键字·void的用法
在 C 语言中，void 是一个关键字，用于表示“无类型”或“没有值”。
阅读更多2024-11-22
MySQL 的 Change Buffer 是什么？它有什么作用？
是 MySQL InnoDB 存储引擎中的一个缓存机制，它用于缓存对非主键索引（Secondary Indexes）页的更改。这个缓存区的主要目的是延迟对这些索引页的写操作，以减少磁盘 I/O，从而提
阅读更多2024-11-22
1.langchain中的prompt模板(Prompt Templates)
通过本教程，我们学习了如何使用 LangChain 的和来创建和处理文本提示。这些工具可以帮助我们灵活地生成和管理多轮对话和动态内容。希望这个教程对你有所帮助！如果有任何问题，欢迎随时提问。
阅读更多2024-11-22
经验笔记：git checkout 与 git switch
在使用 Git 进行版本控制时，和git switch是两个常用的命令，用于分支管理和文件恢复。虽然它们有一些相似之处，但各自的功能和使用场景有所不同。本文将详细介绍这两个命令的用法、区别和实际应用示
阅读更多2024-11-22
Git推送+拉去+uwsgi+Nginx服务器部署项目
本文介绍了一个项目从开发到部署的全过程，重点关注Git版本控制系统的使用，包括代码的推送、拉取操作，以及使用uwsgi与Nginx服务器进行项目部署的步骤。
阅读更多2024-11-22