当前位置: 首页 > news >正文

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

总结

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

相关文章:

c++ 贪心算法

概念 贪心算法是一种在每一步选择中都选择当前最优解的算法策略。这种方法适用于某些特定问题&#xff0c;可以通过局部最优选择构建全局最优解。 特点 局部最优选择&#xff1a;每一步选择都选择当前看起来最优的解。无后效性&#xff1a;当前选择不会影响未来选择的可能性…...

15分钟学 Go 第 35 天:Go的性能调优 (7000字详细教程)

第35天&#xff1a;Go的性能调优 目标&#xff1a;理解Go语言中基本的性能优化&#xff0c;学习如何分析和提高Go程序的执行效率。 一、性能调优概述 性能调优是软件开发中的一个重要环节&#xff0c;它可以确保程序在资源有限的环境下高效运行。Go语言天生具备高效的性能表现…...

6、显卡品牌分类介绍:技嘉 - 计算机硬件品牌系列文章

技嘉科技是一家以主板、‌显卡在业界缔造无以撼动的地位的科技公司&#xff0c;‌其核心理念是「‌技术创新、‌质量稳定」‌的高标准。‌技嘉专注于关键技术研发&#xff0c;‌其经营范围涵盖家用、‌商用、‌电竞等多元科技领域。‌通过应用突破性的专利技术&#xff0c;‌技…...

Redis数据类型——针对实习面试

目录 Redis数据类型Redis常用的数据类型有哪些&#xff1f;String类型可以用于哪些场景&#xff1f;Set类型可以用于哪些场景&#xff1f;Bitmaps类型可以用于哪些场景&#xff1f;HyperLogLog类型可以用于哪些场景&#xff1f;Hash类型与Set类型有什么区别&#xff1f;Hash类型…...

roberta融合模型创新中文新闻文本标题分类

项目源码获取方式见文章末尾&#xff01; 600多个深度学习项目资料&#xff0c;快来加入社群一起学习吧。 《------往期经典推荐------》 项目名称 1.【基于CNN-RNN的影像报告生成】 2.【卫星图像道路检测DeepLabV3Plus模型】 3.【GAN模型实现二次元头像生成】 4.【CNN模型实现…...

《密码系统设计》实验二 4-6学时

文章目录 《密码系统设计》实验实验项目实验二 密码算法实现4-6 学时实践要求&#xff08;30 分&#xff09;1. 定义宏2. 使用特定的源文件3. 编译MIRACL库4. 配置KCM和Comba方法5. 编译和运行MEX工具6. 使用config.c工具总结1. 准备环境2. 下载和解压MIRACL库3. 定义宏4. 使用…...

Zypher Network:全栈式 Web3 游戏引擎,服务器抽象叙事的引领者

近期&#xff0c;《黑神话&#xff1a;悟空》的爆火不仅让 AAA 游戏重回焦点&#xff0c;也引发了玩家与开发者的热议。Web2 游戏的持续成功导致部分 Web3 玩家们的倒戈&#xff0c;对比之下 Web3 游戏存在生命周期短且商业模式难以明确的问题&#xff0c;尤其在当前加密市场环…...

2025生物发酵展(济南)为生物制造产业注入新活力共谱行业新篇章

2025第十四届国际生物发酵展将于3月3-5日济南盛大举办&#xff01;产业链逐步完整&#xff0c;展会面积再创历史新高&#xff0c;展览面积较上届增涨至60000平方米&#xff0c;专业观众40000&#xff0c;品牌展商800&#xff0c;同期活动会议增加至50场&#xff0c;展会同期将举…...

git入门教程14:Git与其他工具的集成

一、Git与代码托管平台的集成 GitHub 集成方式&#xff1a; 在GitHub上创建或克隆仓库。在本地使用Git命令进行代码提交和推送&#xff08;如git push&#xff09;。GitHub提供Web界面进行代码浏览、协作和持续集成配置。 特点&#xff1a; 支持Pull Request&#xff0c;便于代…...

在Zetero中调用腾讯云API的输入密钥的问题

也是使用了Translate插件了&#xff0c;但是需要调用腾讯云翻译&#xff0c;一直没成功。 第一步就是&#xff0c;按照这上面方法做&#xff1a;百度、阿里、腾讯、有道各平台翻译API申请教程 之后就是&#xff1a;Zotero PDF translat翻译&#xff1a;申请腾讯翻译接口 主要是…...

【AD】1-8 AD24软件工程创建

1.点击文件&#xff0c;新建项目 2.如图进行设置工程名称和文件路径 3.创建原理图库及原理图&#xff0c;并保存 4.新建PCB库及PCB&#xff0c;并保存 5.单击右键工程保存 注意&#xff1a;先新建工程&#xff0c;在新建文件...

RT-Thread学习

文章目录 前言一、rtt的启动流程二、移植工作总结 前言 RT-Thread学习&#xff0c;这里记录对bsp的移植 一、rtt的启动流程 RT-Thread 支持多种平台和多种编译器&#xff0c;而 rtthread_startup() 函数是 RT-Thread 规定的统一启动入口。一般执行顺序是&#xff1a;系统先从…...

20241102在荣品PRO-RK3566开发板使用荣品预编译的buildroot通过iperf2测试AP6256的WIFI网速

20241102在荣品PRO-RK3566开发板使用荣品预编译的buildroot通过iperf2测试AP6256的WIFI网速 2024/11/2 14:18 客户端&#xff1a;荣耀手机HONOR 70【iPerf2 for Android】 服务器端&#xff1a;荣品PRO-RK3566开发板 预编译固件&#xff1a;update-pro-rk3566-buildroot-hdmi-2…...

网络模型——二层转发原理

网课地址&#xff1a;网络模型_二层转发原理&#xff08;三&#xff09;_哔哩哔哩_bilibili 一、路由交换 网络&#xff1a;用来信息通信&#xff0c;信息共享的平台。 网络节点&#xff08;交换机&#xff0c;路由器&#xff0c;防火墙&#xff0c;AP&#xff09;介质&#…...

【编程技巧】C++如何使用std::map管理std::function函数指针

一、问题背景 开发过程中遇到了需要根据const字符串调用不同函数的要求。在开发过程中为了快速实现功能&#xff0c;实际使用了if else等判断实现了不同函数的调用&#xff0c;徒增了不少代码行数。 明知道可以采用map管理函数指针&#xff0c;但是没有具体实现过&#xff0c…...

导航栏小案例

实现类似于这样的效果 <!DOCTYPE html> <html><head><meta charset"utf-8"><title>导航栏</title><style>*{margin: 0;padding: 0;}.div1{width: 100%;height: 60px;/* border: 1px solid blue; */background-color:rgb(…...

MyBatis一文入门精通,面试题(含答案)

一、MyBatis详细介绍 MyBatis 是一个流行的 Java 持久层框架&#xff0c;主要用于简化 SQL 数据库操作。它的设计初衷是通过 XML 或注解的方式配置和执行 SQL 语句&#xff0c;使得数据库操作更加灵活、方便和高效。相比于传统的 JDBC&#xff0c;MyBatis 提供了一些关键优势&…...

Ubuntu18.04服务器非root用户在虚拟环境下的python版本设定

最近需要跑一个python3.9.16版本的代码&#xff0c;Ubuntu18.04服务器上是上次博客中已经定死的python3.8.0版本 需要创建一个虚拟环境&#xff0c;并且在虚拟环境中配置python3.9.16版本 只需要创建一个虚拟环境 conda create -n yyy python3.9.16yyy是你的虚拟环境名字 创建…...

CodeS:构建用于文本到 SQL 的开源语言模型

发布于&#xff1a;2024 年 10 月 29 日 #RAG #Text2 SQL #NL2 SQL 语言模型在将自然语言问题转换为 SQL 查询&#xff08;文本到 SQL &#xff09;的任务中显示出良好的性能。然而&#xff0c;大多数最先进的 &#xff08;SOTA&#xff09; 方法都依赖于强大但闭源的大型语言…...

HTML 基础概念:什么是 HTML ? HTML 的构成 与 HTML 基本文档结构

文章目录 什么是 HTML &#xff1f;HTML 的构成 &#xff1f;什么是 HTML 元素&#xff1f;HTML 元素的组成部分HTML 元素的特点 HTML 基本文档结构如何打开新建的 HTML 文件代码查看 什么是 HTML &#xff1f; HTML&#xff08;超文本标记语言&#xff0c;HyperText Markup L…...

KubeSphere 容器平台高可用:环境搭建与可视化操作指南

Linux_k8s篇 欢迎来到Linux的世界&#xff0c;看笔记好好学多敲多打&#xff0c;每个人都是大神&#xff01; 题目&#xff1a;KubeSphere 容器平台高可用&#xff1a;环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...

测试微信模版消息推送

进入“开发接口管理”--“公众平台测试账号”&#xff0c;无需申请公众账号、可在测试账号中体验并测试微信公众平台所有高级接口。 获取access_token: 自定义模版消息&#xff1a; 关注测试号&#xff1a;扫二维码关注测试号。 发送模版消息&#xff1a; import requests da…...

应用升级/灾备测试时使用guarantee 闪回点迅速回退

1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间&#xff0c; 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点&#xff0c;不需要开启数据库闪回。…...

MFC内存泄露

1、泄露代码示例 void X::SetApplicationBtn() {CMFCRibbonApplicationButton* pBtn GetApplicationButton();// 获取 Ribbon Bar 指针// 创建自定义按钮CCustomRibbonAppButton* pCustomButton new CCustomRibbonAppButton();pCustomButton->SetImage(IDB_BITMAP_Jdp26)…...

Debian系统简介

目录 Debian系统介绍 Debian版本介绍 Debian软件源介绍 软件包管理工具dpkg dpkg核心指令详解 安装软件包 卸载软件包 查询软件包状态 验证软件包完整性 手动处理依赖关系 dpkg vs apt Debian系统介绍 Debian 和 Ubuntu 都是基于 Debian内核 的 Linux 发行版&#xff…...

无法与IP建立连接,未能下载VSCode服务器

如题&#xff0c;在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈&#xff0c;发现是VSCode版本自动更新惹的祸&#xff01;&#xff01;&#xff01; 在VSCode的帮助->关于这里发现前几天VSCode自动更新了&#xff0c;我的版本号变成了1.100.3 才导致了远程连接出…...

关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案

问题描述&#xff1a;iview使用table 中type: "index",分页之后 &#xff0c;索引还是从1开始&#xff0c;试过绑定后台返回数据的id, 这种方法可行&#xff0c;就是后台返回数据的每个页面id都不完全是按照从1开始的升序&#xff0c;因此百度了下&#xff0c;找到了…...

vue3+vite项目中使用.env文件环境变量方法

vue3vite项目中使用.env文件环境变量方法 .env文件作用命名规则常用的配置项示例使用方法注意事项在vite.config.js文件中读取环境变量方法 .env文件作用 .env 文件用于定义环境变量&#xff0c;这些变量可以在项目中通过 import.meta.env 进行访问。Vite 会自动加载这些环境变…...

【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统

目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索&#xff08;基于物理空间 广播范围&#xff09;2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...

Linux离线(zip方式)安装docker

目录 基础信息操作系统信息docker信息 安装实例安装步骤示例 遇到的问题问题1&#xff1a;修改默认工作路径启动失败问题2 找不到对应组 基础信息 操作系统信息 OS版本&#xff1a;CentOS 7 64位 内核版本&#xff1a;3.10.0 相关命令&#xff1a; uname -rcat /etc/os-rele…...