c++ 贪心算法

概念

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

特点

  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.rhkb.cn/news/464012.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

面试题:JVM(二)

1. 面试题 简述 Java 类加载机制?&#xff08;百度&#xff09; JVM类加载机制 &#xff08;滴滴&#xff09; JVM中类加载机制&#xff0c;类加载过程&#xff0c;什么是双亲委派模型&#xff1f; &#xff08;腾讯&#xff09; JVM的类加载机制是什么&#xff1f; &#x…

【c++日常刷题】两个数字的交集、点击消除、最小花费爬楼梯

两个数字的交集⭐ 两个数组的交集_牛客题霸_牛客网 (nowcoder.com) 题目描述&#xff1a; 解题思路&#xff1a; 通过遍历num1&#xff0c;如果遍历到的元素如果在num2中能找到&#xff0c;则这是num1和num2的公告元素&#xff1b; 这里需要借助两个数组来实现&#xff1a;…

energy 发布 v2.4.5

更新内容 修复 energy cli install 命令安装开发环境 修复 动态库加载error未暴露 增加 JS ipc.on 监听模式&#xff0c;异步返回结果 修复 energy cli 不能强制退出问题 修复 MacOS 开发模式 debug 时不更新 helper 进程 优化 energy cli 在 MacOS 开发模式和安装包制作 link…

LeetCode 19. 删除链表的倒数第 N 个结点(java)

目录 题目描述: 代码: 第一种: 第二种: 题目描述: 给你一个链表&#xff0c;删除链表的倒数第 n 个结点&#xff0c;并且返回链表的头结点。 示例 1&#xff1a; 输入&#xff1a;head [1,2,3,4,5], n 2 输出&#xff1a;[1,2,3,5]示例 2&#xff1a; 输入&#xff1a;h…

IMU应用于监测进食

最近&#xff0c;日本研究团队成功研发了一种创新的进食速度监测系统&#xff0c;巧妙融合IMU技术&#xff0c;旨在深入研究并有效评估个体在自由生活环境下的进食习惯。 实验中&#xff0c;科研团队把IMU传感器固定在受试者佩戴的腕带中&#xff0c;以监测并记录进食手腕时的运…

WSL开发--利用Git连接远程仓库(详细步骤)

这篇文章主要介绍了如何将本地项目推送到 GitLab 上&#xff0c;并且避免每次提交都需要输入用户名和密码。文中分步讲解了配置 GitLab SSH 密钥以及配置 Git 远程仓库地址的方法。以下是文章的优化和简洁版&#xff1a; 将本地项目推送到 GitLab 并配置 SSH 免密登录 为了方便…

LeetCode100之盛最多水的容器(11)--Java

1.问题描述 给定一个长度为 n 的整数数组 height 。有 n 条垂线&#xff0c;第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。找出其中的两条线&#xff0c;使得它们与 x 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量 注意 你不能倾斜容器 示例1 输入&…

算法实现 - 快速排序(Quick Sort) - 理解版

文章目录 算法介绍算法分析核心思想三个版本运行过程挖坑法Hoare 原版前后指针法 算法稳定性和复杂度稳定性时间复杂度平均情况O(nlogn)最差情况O( n 2 n^2 n2) 空间复杂度 算法介绍 快速排序是一种高效的排序算法&#xff0c;由英国计算机科学家C. A. R. Hoare在1960年提出&a…

设备搜索相关协议使用

一、实现原理 首先&#xff0c;Client -> Gateway : 发送 UDP 广播包&#xff08;含厂商自定义协议)这一步表示客户端开始向网络中发送一个包含厂商自定义协议的 UDP 广播包&#xff0c;目的是寻找本厂商的设备&#xff08;网关&#xff09;。客户端此时处于活动状态activa…

视频去水印怎么办?两种方法教会你

视频有水印的话确实很恼火&#xff0c;想要干净的去除视频水印&#xff0c;这里分享两种简单又实用的方法。 方法一&#xff1a;美图秀秀 大家都熟悉的修图神器&#xff0c;功能超全。不仅能把照片P得美美哒&#xff0c;还能去掉照片和视频上的水印呢&#xff01;用起来挺顺手…

【案例】旗帜飘动

开发平台&#xff1a;Unity 6.0 开发工具&#xff1a;Shader Graph 参考视频&#xff1a;Unity Shader Graph 旗帜飘动特效   一、效果图 二、Shader Graph 路线图 三、案例分析 核心思路&#xff1a;顶点偏移计算 与 顶点偏移忽略 3.1 纹理偏移 视觉上让旗帜保持动态飘动&a…

PHP合成图片,生成海报图,poster-editor使用说明

之前写过一篇使用Grafika插件生成海报图的文章&#xff0c;但是当我再次使用时&#xff0c;却发生了错误&#xff0c;回看Grafika文档&#xff0c;发现很久没更新了&#xff0c;不兼容新版的GD&#xff0c;所以改用了intervention/image插件来生成海报图。 但是后来需要对海报…

智慧汇聚:十款企业培训工具打造学习型企业

在当今快速变化的商业环境中&#xff0c;企业要想保持竞争力&#xff0c;就必须不断适应新技术、新市场和新的工作方式。构建一个学习型企业&#xff0c;不仅能够促进员工的个人成长&#xff0c;还能增强团队的整体能力和企业的创新能力。为了实现这一目标&#xff0c;借助先进…

「C/C++」C/C++标准库 之 #include<cstdlib> 通用工具函数库

✨博客主页何曾参静谧的博客&#x1f4cc;文章专栏「C/C」C/C程序设计&#x1f4da;全部专栏「VS」Visual Studio「C/C」C/C程序设计「UG/NX」BlockUI集合「Win」Windows程序设计「DSA」数据结构与算法「UG/NX」NX二次开发「QT」QT5程序设计「File」数据文件格式「PK」Parasoli…

pycharm调用方法时显示为灰色

不用担心&#xff0c;亮的证明是被用过得&#xff0c;灰色的没有被用&#xff0c;引用一下就会变正常了

机器学习:我们能用机器学习来建立投资模型吗

机器学习模型能解决什么投资问题&#xff1f; 利用机器学习解决投资问题的思路&#xff0c;其实和在互联网领域解决推荐、广告问题的思路是一样的&#xff0c;只不过利用的特征完全变了。推荐、广告模型利用的是用户的年龄、性别&#xff0c;物品的类别、价格等特征&#xff0c…

ClkLog企业版(CDP)预售开启,更有鸿蒙SDK前来助力

新版本发布 ClkLog在上线近1年后&#xff0c;获得了客户的一致肯定与好评&#xff0c;并收到了不少客户对功能需求的反馈。根据客户的反馈&#xff0c;我们在今年三季度对ClkLog的版本进行了重新的规划与调整&#xff0c;简化了原有的版本类型&#xff0c;方便客户进行选择。 与…

【Java设计模式】16-26章

行为型模式&#xff1a; 第16章 12模板方法模式(Template) 16.1 豆浆制作问题 16.2 模板方法模式基本介绍 16.3 模板方法模式原理类图 16.4 模板方法模式解决豆浆制作问题 package com.atguigu.template;//抽象类&#xff0c;表示豆浆 public abstract class SoyaMilk {//模板…

上市公司环境信息披露质量评分数据王婉菁版(2008-2023年)噪声光污染辐射废水减排等治理

数据来源基础数据来源于上市公司年报、社会责任报告、环境报告以及证监会和统计局。时间跨度2008-2023区域跨度企业及行业层面 核心解释变量&#xff1a;环境信息披露质量&#xff0c;是由上市公司环境管理、负债、业绩于治理、披露载体等各项信息披露质量评分加总。 被解释变…

Llama 3.2 Vision Molmo:多模态开源生态系统基础

编者按&#xff1a; 视觉功能的融入对模型能力和推理方式的影响如何&#xff1f;当我们需要一个既能看懂图像、又能生成文本的 AI 助手时&#xff0c;是否只能依赖于 GPT-4V 这样的闭源解决方案&#xff1f; 我们今天为大家分享的这篇文章&#xff0c;作者的核心观点是&#xf…