贪心算法详解及C++实现

1. 什么是贪心算法

贪心算法(Greedy Algorithm)是一种在每一步选择中都采取在当前状态下最好或最优(即最有利)的选择,从而希望导致结果是全局最好或最优的算法策略。

贪心算法与动态规划不同在于它对每个子问题的解决方案都做出选择,不能回退。动态规划则会保存以前的运算结果,并根据以前的结果对当前进行选择,有回退功能。

2. 贪心算法的基本要素

贪心算法适用的问题通常具有以下两个性质:

  1. 贪心选择性质:所求问题的整体最优解可以通过一系列局部最优的选择来达到。
  2. 最优子结构:问题的最优解包含其子问题的最优解。

3. 贪心算法的基本步骤

  1. 建立数学模型来描述问题
  2. 把求解的问题分成若干个子问题
  3. 对每个子问题求解,得到子问题的局部最优解
  4. 把子问题的解合并成原问题的一个解

4. 经典贪心算法问题

4.1 找零钱问题

问题描述:假设有不同面额的硬币 coins = [1, 2, 5, 10, 20, 50, 100],我们需要用最少数量的硬币来找零 n 元。

#include <iostream>
#include <vector>
#include <algorithm>using namespace std;vector<int> coinChange(int amount, vector<int>& coins) {sort(coins.rbegin(), coins.rend()); // 从大到小排序vector<int> result;for (int coin : coins) {while (amount >= coin) {amount -= coin;result.push_back(coin);}}if (amount != 0) {cout << "无法正好找零" << endl;return {};}return result;
}int main() {vector<int> coins = {1, 2, 5, 10, 20, 50, 100};int amount = 93;vector<int> result = coinChange(amount, coins);cout << "找零" << amount << "元需要的硬币为:";for (int coin : result) {cout << coin << " ";}cout << endl;return 0;
}

4.2 活动选择问题

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

#include <iostream>
#include <vector>
#include <algorithm>using namespace std;struct Activity {int start;int end;
};bool compareActivity(Activity a, Activity b) {return a.end < b.end;
}vector<Activity> selectActivities(vector<Activity>& activities) {sort(activities.begin(), activities.end(), compareActivity);vector<Activity> selected;selected.push_back(activities[0]);int lastEnd = activities[0].end;for (int i = 1; i < activities.size(); i++) {if (activities[i].start >= lastEnd) {selected.push_back(activities[i]);lastEnd = activities[i].end;}}return selected;
}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}};vector<Activity> result = selectActivities(activities);cout << "选择的活动序列为:" << endl;for (Activity act : result) {cout << "[" << act.start << ", " << act.end << "] ";}cout << endl;return 0;
}

4.3 霍夫曼编码

问题描述:霍夫曼编码是一种用于无损数据压缩的贪心算法,通过给出现频率高的字符较短的编码,出现频率低的字符较长的编码,来达到压缩数据的目的。

#include <iostream>
#include <queue>
#include <unordered_map>
#include <string>using namespace std;struct HuffmanNode {char ch;int freq;HuffmanNode *left, *right;HuffmanNode(char c, int f) : ch(c), freq(f), left(nullptr), right(nullptr) {}
};struct compare {bool operator()(HuffmanNode* l, HuffmanNode* r) {return l->freq > r->freq;}
};void encode(HuffmanNode* root, string str, unordered_map<char, string> &huffmanCode) {if (root == nullptr) return;if (!root->left && !root->right) {huffmanCode[root->ch] = str;}encode(root->left, str + "0", huffmanCode);encode(root->right, str + "1", huffmanCode);
}void buildHuffmanTree(string text) {unordered_map<char, int> freq;for (char ch : text) {freq[ch]++;}priority_queue<HuffmanNode*, vector<HuffmanNode*>, compare> pq;for (auto pair : freq) {pq.push(new HuffmanNode(pair.first, pair.second));}while (pq.size() != 1) {HuffmanNode *left = pq.top(); pq.pop();HuffmanNode *right = pq.top(); pq.pop();int sum = left->freq + right->freq;HuffmanNode *node = new HuffmanNode('\0', sum);node->left = left;node->right = right;pq.push(node);}HuffmanNode* root = pq.top();unordered_map<char, string> huffmanCode;encode(root, "", huffmanCode);cout << "霍夫曼编码表:" << endl;for (auto pair : huffmanCode) {cout << pair.first << " : " << pair.second << endl;}string encodedStr;for (char ch : text) {encodedStr += huffmanCode[ch];}cout << "编码后的字符串:" << encodedStr << endl;
}int main() {string text = "hello world";cout << "原始字符串:" << text << endl;buildHuffmanTree(text);return 0;
}

5. 贪心算法的优缺点

优点:

  1. 简单易懂,容易实现
  2. 运行效率高,时间复杂度通常较低
  3. 可以作为其他算法的辅助算法

缺点:

  1. 不能保证得到全局最优解
  2. 适用范围有限,只有部分问题能用贪心算法解决
  3. 需要证明其正确性,有时证明较复杂

6. 贪心算法的应用场景

  1. 最小生成树(Prim和Kruskal算法)
  2. 最短路径问题(Dijkstra算法)
  3. 数据压缩(霍夫曼编码)
  4. 任务调度问题
  5. 集合覆盖问题

7. 总结

贪心算法是一种简单而有效的算法设计技术,适用于具有贪心选择性质和最优子结构的问题。虽然它不能解决所有优化问题,但在适用的情况下,它通常能提供高效且简单的解决方案。理解贪心算法的原理和应用场景,对于算法学习和问题解决能力的提升都有很大帮助。

在实际应用中,我们需要仔细分析问题是否适合使用贪心算法,并验证其正确性。当贪心算法不能得到全局最优解时,可能需要考虑动态规划等其他方法。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.pswp.cn/web/88128.shtml
繁体地址,请注明出处:http://hk.pswp.cn/web/88128.shtml
英文地址,请注明出处:http://en.pswp.cn/web/88128.shtml

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

相关文章

IDEA 中使用 <jsp:useBean>动作指令时,class属性引用无效

问题&#xff1a;在 IDEA 中创建 Java Web项目&#xff0c;在src/model包下存在一个Student类该类中包含&#xff1a;全参构造器、私有属性的get/set方法。然后在 jsp 页面中使用 <jsp:useBean>创建Student类的对象&#xff1a;访问页面时报错&#xff1a;原因&#xff1…

【网络】Linux 内核优化实战 - net.core.flow_limit_table_len

目录参数作用查看与修改调优建议相关警告net.core.flow_limit_table_len 是 Linux 内核中的一个网络参数&#xff0c;用于控制**流限制表&#xff08;Flow Limit Table&#xff09;**的大小。这个表主要用于限制网络流量中单个"流"&#xff08;通常指来自同一源IP、端…

前端开发常见问题技术文章大纲

前端开发常见问题技术文章大纲 常见性能优化问题 页面加载速度慢的原因及解决方案渲染阻塞资源的优化方法内存泄漏的检测与修复 跨浏览器兼容性问题 不同浏览器对CSS和JavaScript的支持差异Polyfill和Shim的使用场景如何利用工具检测兼容性问题 响应式设计挑战 媒体查询的最佳实…

Redis常见性能问题和解决方案有哪些?

Redis 作为高性能的内存数据库&#xff0c;在实际使用中可能会遇到性能问题。以下是常见的性能问题及其解决方案&#xff0c;用中文总结如下&#xff1a; 1. 高延迟问题 问题描述&#xff1a;客户端请求响应时间过长&#xff0c;可能由于网络、命令复杂度或服务器负载导致。 解…

闪测仪应用案例丨手机中框如何突破「尺寸检测」瓶颈?

越来越多的手机中框&#xff0c;正改为更复杂的镂空设计&#xff0c;这种设计不仅保持了手机中框的结构强度&#xff0c;还进一步减轻了机身重量&#xff0c;同时提升了散热性能。这让手机中框的自动化生产增加了很多难点&#xff0c;其中的尺寸检测就遇到了许多瓶颈。▪ 尺寸精…

【字节跳动】数据挖掘面试题0011:介绍下时间序列分析常用知识点

文章大纲时间序列分析全面解析一、时间序列分析的基本概念二、时间序列分析的主要方法1. 描述性分析2.统计分析方法3.预测模型&#xff08;1&#xff09;传统统计模型&#xff08;2&#xff09;现代机器学习模型三、时间序列分析的应用场景四、模型评估五、在字节跳动的应用场景…

ubuntu中交叉编译iperf3到目标平台xilinx

注&#xff1a;此文为ubuntu x86系统编译程序到xilinx aarch64系统中。 一、工具准备 x86上编译aarch64的编译器 sudo apt install gcc-aarch64-linux-gnu g-aarch64-linux-gnu #保证编译器在环境变量中&#xff0c;尝试执行aarch64-linux-gnu-gcc 目标平台的根文件系统rootf…

Java-数据结构-集合框架

什么是集合框架集合本质是java所实现的一组数据结构&#xff0c;提供了不同的增删改查方法。集合就是定义了接口&#xff0c;再通过不同的类去实现定义的接口&#xff0c;这些实现了接口的类就是集合类&#xff0c;例如list&#xff0c;stack&#xff0c;map。集合框架的重要性…

黑马点评系列问题之基础篇16jedis redis依赖引入后仍然还是报错

问题描述依赖已经导入进去了&#xff0c;在仓库里有***.jar和***.pom这两个文件&#xff0c;但是点开右面的maven还是有很多爆红。点击maven里的更新还是不行。解决点到配置文件pom.xml在lombok这个依赖的代码下面&#xff0c;添加上版本号&#xff0c;刷新一下右键单击pom.xml…

SQL 一键转 GORM 模型,支持字段注释、类型映射、tag 自定义!

SQL 一键转 GORM 模型&#xff0c;支持字段注释、类型映射、tag 自定义&#xff01; 在使用 Golang GORM 开发项目时&#xff0c;你是否也经历过这些「重复性痛苦」&#xff1a; ✅ 拿到建表 SQL&#xff0c;要手动写 struct✅ 字段多、类型复杂&#xff0c;还要写 json、go…

前端计算机视觉:使用 OpenCV.js 在浏览器中实现图像处理

一、OpenCV.js 简介与环境搭建OpenCV&#xff08;Open Source Computer Vision Library&#xff09;是一个强大的计算机视觉库&#xff0c;广泛应用于图像和视频处理领域。传统上&#xff0c;OpenCV 主要在后端使用 Python 或 C 等语言。但随着 WebAssembly (Wasm) 技术的发展&…

开发在线商店:基于Vue2+ElementUI的电商平台前端实践

Hi&#xff0c;我是布兰妮甜 &#xff01;在当今数字化时代&#xff0c;电子商务已成为商业领域的重要组成部分。开发一个功能完善、用户友好的在线商店应用对于企业拓展市场至关重要。本文将详细介绍如何使用Vue2框架配合ElementUI组件库开发一个完整的在线商店应用。 文章目录…

vue3 随手笔记9--组件通信方式9/2--自定义事件

一、什么是自定义事件&#xff1f; 自定义事件是 Vue 组件间通信的一种机制。子组件通过 this.$emit(事件名, 数据) 触发一个事件。父组件监听这个事件并执行相应的逻辑。 二、基本使用 准备工作 demo 继续使用笔记8中的 链接为demo 在views文件夹下 创建新的文件夹为cust…

深入理解Reactor调试模式:Hooks.onOperatorDebug() vs ReactorDebugAgent.init()

在现代Java开发中&#xff0c;调试Reactor流是确保应用程序性能和稳定性的关键步骤。Reactor调试模式提供了多种初始化方法&#xff0c;其中最常用的两种是Hooks.onOperatorDebug()和ReactorDebugAgent.init()。本文将深入探讨这两种方法的区别&#xff0c;帮助开发者选择最适合…

QT6 源(151)模型视图架构里的表格窗体视图 QTableWidget 篇一:先学习俩属性以及 public 权限的公共成员函数,

&#xff08;1&#xff09;本篇的内容因为是子类&#xff0c;内容较视图基类简单了一些。又因为时间紧迫&#xff0c;不再详细举例了。详细的测试可以满足好奇心&#xff0c;也可以增强写代码的自信心。奈何时间不够。不完美&#xff0c;就不完美了。以后有机会&#xff0c;再补…

ffmpeg 下载、安装、配置、基本语法、避坑指南(覆盖 Windows、macOS、Linux 平台)

ffmpeg 下载、安装、配置、基本语法、避坑指南&#xff08;覆盖 Windows、macOS、Linux 平台&#xff09; 本文是一篇面向初学者的超详细 FFmpeg 教程&#xff0c;包括 FFmpeg 下载、安装、配置、基本语法 与 避坑指南。覆盖 Windows、macOS、Linux 平台的安装方式与 环境变量…

Kotlin 安装使用教程

一、Kotlin 简介 Kotlin 是 JetBrains 开发的一种现代、静态类型的编程语言&#xff0c;完全兼容 Java&#xff0c;主要应用于 Android 开发、后端服务开发、前端 Web 开发&#xff08;Kotlin/JS&#xff09;和多平台开发&#xff08;Kotlin Multiplatform&#xff09;。 二、…

day08-Elasticsearch

黑马商城作为一个电商项目&#xff0c;商品的搜索肯定是访问频率最高的页面之一。目前搜索功能是基于数据库的模糊搜索来实现的&#xff0c;存在很多问题。 首先&#xff0c;查询效率较低。 由于数据库模糊查询不走索引&#xff0c;在数据量较大的时候&#xff0c;查询性能很…

transformers 笔记:自定义模型(配置+模型+注册为AutoCLass+本地保存加载)

Transformers 模型设计上是可定制的。每个模型的代码都包含在 Transformers 仓库的 model 子文件夹中&#xff08;transformers/src/transformers/models at main huggingface/transformers&#xff09;&#xff0c;每个模型文件夹通常包含&#xff1a; modeling.py&#xff1…

Java工具类,对象List提取某个属性为List,对象List转为对象Map其中某个属性作为Key值

Java工具类package org.common;import lombok.extern.slf4j.Slf4j;import java.util.*; import java.util.stream.Collectors;Slf4j public final class CollectorHelper {/*** param element* param propertyName* param <E>* return*/public static <E> List toL…