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.xdnf.cn/news/6924.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

Linux下的WatchDog

看门狗&#x1f415; 看门狗简介 看门狗定时器&#xff08;Watchdog Timer&#xff09;是一种定时器&#xff0c;用于检测系统是否正常运行。如果系统在规定时间内没有向看门狗定时器发送复位信号&#xff0c;看门狗定时器就会产生复位信号&#xff0c;使系统复位。看门狗定时…

vue3+vite搭建脚手架项目本地运行electron桌面应用

1.搭建脚手架项目 搭建Vue3ViteTs脚手架-CSDN博客 2.创建完项目后&#xff0c;安装所需依赖包 npm i vite-plugin-electron electron26.1.0 3.根目录下创建electron/main.ts electron/main.ts /** electron/main.ts */import { app, BrowserWindow } from "electron&qu…

推荐一款基于Flash的交互式园林设计工具:Garden Planner

Garden Planner是一款由Artifact Interactive开发的基于Flash的交互式园林设计工具。它允许用户以拖放的方式安排植物、树木、建筑物和各种对象&#xff0c;使园林规划变得简单直观。此外&#xff0c;Garden Planner提供工具来快速创建铺路、路径和围栏&#xff0c;帮助用户设计…

H7-TOOL的LUA小程序教程第17期:扩展驱动AD7606, ADS1256,MCP3421, 8路继电器和5路DS18B20(2024-11-01)

LUA脚本的好处是用户可以根据自己注册的一批API&#xff08;当前TOOL已经提供了几百个函数供大家使用&#xff09;&#xff0c;实现各种小程序&#xff0c;不再限制Flash里面已经下载的程序&#xff0c;就跟手机安装APP差不多&#xff0c;所以在H7-TOOL里面被广泛使用&#xff…

JAVA基础:数组 (习题笔记)

一&#xff0c;编码题 1&#xff0c;数组查找操作&#xff1a;定义一个长度为10 的一维字符串数组&#xff0c;在每一个元素存放一个单词&#xff1b;然后运行时从命令行输入一个单词&#xff0c;程序判断数组是否包含有这个单词&#xff0c;包含这个单词就打印出“Yes”&…

为开源 AI 模型引入激励机制?解读加密 AI 协议 Sentient 的大模型代币化解决方案

撰文&#xff1a;Shlok Khemani 编译&#xff1a;Glendon&#xff0c;Techub News 古时候&#xff0c;中国人深信「阴阳」的概念——宇宙的每一个方面都蕴含着内在的二元性&#xff0c;这两种相反的力量不断地相互联系&#xff0c;形成一个统一的整体。就好比女性代表「阴」&a…

ONES 功能上新|ONES Project 甘特图全面升级

ONES Project 甘特图全面升级&#xff0c;提供更加专业、灵活的工具。 项目经理往往面临项目进度难以直观把控、关键任务容易遗漏、里程碑节点缺乏明确标记、进度偏差无法及时发现等挑战。 针对这些痛点&#xff0c;ONES 新增了关键路径、基线对比、里程碑视图、交付物视图等 1…

windows 进程降权和提权代码示例(2) c++

强制完整性控制 - Win32 应用程序 |Microsoft 学习 一、强制完整性控制 品03/26/20217 个参与者 反馈 本文内容 诚信标签进程创建强制性政策 强制完整性控制 &#xff08;MIC&#xff09; 提供了一种用于控制对安全对象的访问的机制。此机制是对自主访问控制的补充&#xff…

基于Python的旅游景点推荐系统

作者&#xff1a;计算机学姐 开发技术&#xff1a;SpringBoot、SSM、Vue、MySQL、JSP、ElementUI、Python、小程序等&#xff0c;“文末源码”。 专栏推荐&#xff1a;前后端分离项目源码、SpringBoot项目源码、Vue项目源码、SSM项目源码、微信小程序源码 精品专栏&#xff1a;…

【C++】vector 类深度解析:探索动态数组的奥秘

&#x1f31f;快来参与讨论&#x1f4ac;&#xff0c;点赞&#x1f44d;、收藏⭐、分享&#x1f4e4;&#xff0c;共创活力社区。 &#x1f31f; 如果你对string类还存在疑惑&#xff0c;欢迎阅读我之前的作品 &#xff1a; &#x1f449;【C】string 类深度解析&#xff1a;…

Hugging Face 平台轻松上手 | 书生大模型

文章目录 HF 的 Transformers 库GitHub CodeSpace 使用终端安装依赖下载 internlm2_5-7b-chat 的配置文件 参考文献 HF 的 Transformers 库 直接使用预训练模型进行推理提供了大量预训练模型可供使用使用预训练模型进行迁移学习 因此在使用 HF 前&#xff0c;我们需要下载 Tra…

项目升级到.Net8.0 Autofac引发诡异的问题

前两天把项目升级到.Net8.0了&#xff0c;把.Net框架升级了&#xff0c;其他一些第三方库升级了一部分&#xff0c;升级完以后项目跑不起来了&#xff0c;报如下错误&#xff1a; An unhandled exception occurred while processing the request. DependencyResolutionExcepti…

如何开发查找附近地点的微信小程序

我开发的是找附近卫生间的小程序。 在现代城市生活中&#xff0c;找到一个干净、方便的公共卫生间有时可能是一个挑战。为了解决这个问题&#xff0c;我们可以开发一款微信小程序&#xff0c;帮助用户快速找到附近的卫生间。本文将介绍如何开发这样一款小程序&#xff0c;包…

canfestival主站多电机对象字典配置

不要使用数组进行命名&#xff1a;无法运行PDO 使用各自命名的方式&#xff1a;

楼宇智慧公厕为用户提供清晰厕位引导,提高用厕效率

如今楼宇管理者越来越重视公共设施的优化&#xff0c;尤其是公厕的管理。楼宇智慧公厕系统通过先进的技术&#xff0c;为用户提供清晰的厕位引导&#xff0c;显著提高了用厕效率。本文将从两个方面介绍楼宇智慧公厕系统的功能及其带来的好处。 一、清晰厕位引导 楼宇智慧公厕系…

Ubuntu 20.04 安装 QGC v4.3 开发环境

Ubuntu 20.04 安装 QGC开发环境 1. 准备安装 Qt 5.15.2安装依赖获取源码 2. 编译参考 前言 QGC ( QGroundControl) 是一个开源地面站&#xff0c;基于QT开发的&#xff0c;有跨平台的功能。可以在Windows&#xff0c;Android&#xff0c;MacOS或Linux上运行。它可以将PX4固件加…

使用匿名管道时出现程序一直运行问题

父进程创建两个子进程&#xff0c;父子进程之间利用管道进行通信。要求能显示父进程、子进程各自的信息&#xff0c;体现通信效果。(源程序pipe_1.c) 一开始&#xff0c;我忘了初始化pipe,很傻*的直接把fd当管道使&#xff0c;出现了儿子喊爸爸"i am your father."的…

uniapp实现H5和微信小程序获取当前位置(腾讯地图)

之前的一个老项目&#xff0c;使用 uniapp 的 uni.getLocation 发现H5端定位不准确&#xff0c;比如余杭区会定位到临平区&#xff0c;根据官方文档初步判断是项目的uniapp的版本太低。 我选择的方式不是区更新uniapp的版本&#xff0c;是直接使用高德地图的api获取定位。 1.首…

小菜家教平台(四):基于SpringBoot+Vue打造一站式学习管理系统

前言 昨天配置完了过滤器&#xff0c;权限检验&#xff0c;基本的SpringSecurity功能已经配置的差不多了&#xff0c;今天继续开发&#xff0c;明天可能会暂停一天整理一下需求&#xff0c;然后就进行CRUD了。 今日进度 补充SpringSecurity异常处理和全局异常处理器 详细操作…

MES管理系统的生产绩效分析与资源可追踪性

在探讨MES管理系统的核心功能时&#xff0c;生产绩效分析与资源可追踪性是两个不可或缺的关键要素。它们共同构成了MES管理系统中对于生产效率、成本控制以及产品质量进行精细管理的基石。以下是对这两个关键领域的深入剖析与重新阐述。 MES管理系统中的生产绩效分析&#xff0…