37 _ 贪心算法:如何用贪心算法实现Huffman压缩编码?

基础的数据结构和算法我们基本上学完了,接下来几节,我会讲几种更加基本的算法。它们分别是贪心算法、分治算法、回溯算法、动态规划。更加确切地说,它们应该是算法思想,并不是具体的算法,常用来指导我们设计具体的算法和编码等。

贪心、分治、回溯、动态规划这4个算法思想,原理解释起来都很简单,但是要真正掌握且灵活应用,并不是件容易的事情。所以,接下来的这4个算法思想的讲解,我依旧不会长篇大论地去讲理论,而是结合具体的问题,让你自己感受这些算法是怎么工作的,是如何解决问题的,带你在问题中体会这些算法的本质。我觉得,这比单纯记忆原理和定义要更有价值。

今天,我们先来学习一下贪心算法(greedy algorithm)。贪心算法有很多经典的应用,比如霍夫曼编码(Huffman Coding)、Prim和Kruskal最小生成树算法、还有Dijkstra单源最短路径算法。最小生成树算法和最短路径算法我们后面会讲到,所以我们今天讲下霍夫曼编码,看看它是如何利用贪心算法来实现对数据压缩编码,有效节省数据存储空间的

如何理解“贪心算法”?

关于贪心算法,我们先看一个例子。

假设我们有一个可以容纳100kg物品的背包,可以装各种物品。我们有以下5种豆子,每种豆子的总量和总价值都各不相同。为了让背包中所装物品的总价值最大,我们如何选择在背包中装哪些豆子?每种豆子又该装多少呢?

实际上,这个问题很简单,我估计你一下子就能想出来,没错,我们只要先算一算每个物品的单价,按照单价由高到低依次来装就好了。单价从高到低排列,依次是:黑豆、绿豆、红豆、青豆、黄豆,所以,我们可以往背包里装20kg黑豆、30kg绿豆、50kg红豆。

这个问题的解决思路显而易见,它本质上借助的就是贪心算法。结合这个例子,我总结一下贪心算法解决问题的步骤,我们一起来看看。

第一步,当我们看到这类问题的时候,首先要联想到贪心算法:针对一组数据,我们定义了限制值和期望值,希望从中选出几个数据,在满足限制值的情况下,期望值最大。

类比到刚刚的例子,限制值就是重量不能超过100kg,期望值就是物品的总价值。这组数据就是5种豆子。我们从中选出一部分,满足重量不超过100kg,并且总价值最大。

第二步,我们尝试看下这个问题

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/151071.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

622.设计循环队列(LeetCode)

思路 先确定什么情况为空,什么情况为满。 这里有两种解决方案, 1.留一个空间空置,当rear1 front时 ,则队列为满 (这里我们选用方案一) 2.增加一个size变量记录数据个数,size 0则为空&#xff…

Uniapp导出的iOS应用上架详解

​ 目录 Uniapp导出的iOS应用上架详解 摘要 引言 苹果审核标准 苹果调试 注意事项和建议 总结 摘要 本文将探讨Uniapp导出的iOS应用能否成功上架的问题。我们将从苹果审核标准、性能影响、调试流程等多个方面进行深入分析,以及向开发者提供相关注意事项和建…

【计算机网络笔记】DHCP协议

系列文章目录 什么是计算机网络? 什么是网络协议? 计算机网络的结构 数据交换之电路交换 数据交换之报文交换和分组交换 分组交换 vs 电路交换 计算机网络性能(1)——速率、带宽、延迟 计算机网络性能(2)…

JAVA 中集合取交集

日常工作 经常需要取两个数据集的交集。对常用的List 和Set集合做了一个测试 public static void main(String[] args) {List<Integer> list1 Lists.newArrayList();List<Integer> list2 Lists.newArrayList();Set<Integer> set3 Sets.newHashSet();Set&l…

优秀智慧园区案例 - 重庆AI PARK智慧创意园区,先进智慧园区建设方案经验

一、项目背景 1、智慧园区是国家实现经济增长、产业升级的载体 智慧园区建设是城市智慧化创新发展的核心&#xff0c;在数智化升级和低碳化转型的经济发展双引擎的驱动下&#xff0c;十四五、数字经济的政策大力支持&#xff0c;以及人工智能、5G、大数据、区块链等技术的不断…

ubuntu中cuda12.1配置(之前存在11.1版本的cuda)(同时配置两个版本)

ubuntu中cuda12.1配置 由于YOLOv8项目中Pytorch版本需要cuda12.1版本 在官网下载12.1版本的deb包 官网地址 sudo dpkg -i cuda-keyring_1.0-1_all.deb sudo apt-get update sudo apt-get -y install cuda然后需要修改bashrc文件&#xff08;隐藏文件&#xff09; 添加 exp…

Postman实现接口的加密和解密

近期在复习Postman的基础知识&#xff0c;在小破站上跟着百里老师系统复习了一遍&#xff0c;也做了一些笔记&#xff0c;希望可以给大家一点点启发。 1、目前市面上的加密的方式 对称式加密&#xff1a;DES&#xff0c;AES&#xff0c;Base64加密算法 非对称加密&#xff1a…

基于STC12C5A60S2系列1T 8051单片机的数模芯片TLC5615实现数模转换应用

基于STC12C5A60S2系列1T 8051单片的数模芯片TLC5615实现数模转换应用 STC12C5A60S2系列1T 8051单片机管脚图STC12C5A60S2系列1T 8051单片机I/O口各种不同工作模式及配置STC12C5A60S2系列1T 8051单片机I/O口各种不同工作模式介绍数模芯片TLC5615介绍通过按键调节数模芯片TLC5615…

Postman的Cookie鉴权

近期在复习Postman的基础知识&#xff0c;在小破站上跟着百里老师系统复习了一遍&#xff0c;也做了一些笔记&#xff0c;希望可以给大家一点点启发。 一&#xff09;什么是Cookie 定义&#xff1a;存储在客户端的一小段文本信息&#xff0c;格式为键值对的形式. 二&#xff09…

低代码编辑平台后台实现

背景 之前做过一个前端低代码编辑平台&#xff0c;可以实现简单的移动端页面组件拖拽编辑&#xff1a; https://github.com/li-car-fei/react-visual-design 最近基于C的oatpp框架实现了一下后台。使用oatpp框架做web后台开发时&#xff0c;发现按照官方的示例使用的话&#…

氢原子波函数等概率面的绘制

氢原子波函数等概率面的绘制 归一化后的氢原子波函数

高浓度白酒废水处理需要哪些设备

高浓度白酒废水处理需要的设备包括预处理设备、生物反应器、二级处理设备、消毒装置等。 预处理设备&#xff1a;包括格栅、筛网等&#xff0c;用于去除污水中的大颗粒物和杂质。生物反应器&#xff1a;用于进行生物反应&#xff0c;去除污水中的有机物和氨氮等污染物。二级处…

基于平衡优化器算法优化概率神经网络PNN的分类预测 - 附代码

基于平衡优化器算法优化概率神经网络PNN的分类预测 - 附代码 文章目录 基于平衡优化器算法优化概率神经网络PNN的分类预测 - 附代码1.PNN网络概述2.变压器故障诊街系统相关背景2.1 模型建立 3.基于平衡优化器优化的PNN网络5.测试结果6.参考文献7.Matlab代码 摘要&#xff1a;针…

Linux 系统编程,Binder 学习,文件访问相关的接口

文章目录 Linux 系统编程&#xff0c;Binder 学习&#xff0c;文件访问相关的接口1.概念2.linux文件结构3.文件描述符4.Linux文件系统的两类常用接口&#xff0c;linux系统内置库函数4.1 open4.2 close4.3 read4.4 write 5.标准I/O库函数5.1 fopen Linux 系统编程&#xff0c;B…

IDEA 高分辨率卡顿优化

VM设置优化 -Dsun.java2d.uiScale.enabledfalse 增加该条设置&#xff0c;关闭高分切换 https://intellij-support.jetbrains.com/hc/en-us/articles/115001260010-Troubleshooting-IDE-scaling-DPI-issues-on-Windows​intellij-support.jetbrains.com/hc/en-us/articles/1…

c语言判断链表是否为循环链表

普通链表与循环链表的区别在于&#xff1a;普通链表的最后一个节点指向为NULL&#xff0c;而循环链表最后一个节点指向该链表中的任意一个节点&#xff0c;如同一个环。循环链表问题引出了一个在链表中很重要的概念&#xff1a;快、慢指针。快、慢指针可以帮助我们解决很多经典…

使用jmeter+ant进行接口自动化测试(数据驱动)

本次接着介绍如何利用apache-ant执行测试用例并生成HTML格式测试报告 ①下载安装 apache-ant-1.9.9&#xff0c;配置环境变量 如下方式检验安装成功 ②安装好ant后&#xff0c;把jmeter中extras目录下的ant-jmeter-1.1.1.jar 文件copy到ant安装目录下的lib文件夹中 ③配置ant…

ssm045基于jsp的精品酒销售管理系统+jsp

ssm045基于jsp的精品酒销售管理系统jsp 交流学习&#xff1a; 更多项目&#xff1a; 全网最全的Java成品项目列表 https://docs.qq.com/doc/DUXdsVlhIdVlsemdX 演示 项目功能演示&#xff1a; ————————————————

247:vue+openlayers 根据坐标显示多边形(3857投影),计算出最大幅宽

第247个 点击查看专栏目录 本示例是演示如何在vue+openlayers项目中根据坐标显示多边形(3857投影),计算出最大幅宽。这里先通过Polygon来显示出多边形,利用getExtent() 获取3857坐标下的最大最小x,y值,通过ransformExtent转换坐标为4326, 通过turf的turf.distance和计算…

Vue3清除Echarts图表

一&#xff1a;前言 Vue3是一款流行的JavaScript框架。它提供了丰富的工具和组件&#xff0c;使得开发者可以轻松构建交互式的Web应用程序。而Echarts是一款功能强大的图表库&#xff0c;它可以帮助开发者以直观的方式展示数据。 在使用Vue3和E charts的过程中&#xf…