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

贪心算法+练习

正值国庆之际,祝愿祖国繁荣昌盛,祝愿朋友一生平安!终身学习,奋斗不息!

目录

1.贪心算法简介

2.贪心算法的特点

3.如何学习贪心算法

题目练习(持续更新)

1.柠檬水找零(easy)

算法原理

代码实现

证明(交换论证法)


1.贪心算法简介

贪心策略:解决问题的一种策略,由局部最优->全局最优。

一般步骤:

1.把解决问题的过程分为若干步

2.解决每一步的时候,都选择当前“最优的”解法

3.“希望”得到全局最优解

例1:找零问题

有20,10,5,1面值货币若干张,如何用最少的张数支付46元?

贪心策略:每次选取尽可能大的货币

7d4aee9086bb42b7953f1f5ba460d792.png

例2:背包问题

一个背包容量为8,有3种物品若干,选择要装的物品,使背包内物品总价值最大

贪心策略:每次选择单位体积价值尽可能大的物品。类似也可选择体积小(装更多的物品,总价值可能最大),价值大(每次选价值大的,总价值可能最大)。

9337df3abc51488f97bb466161a3511b.png

通过贪心策略得到的结果是13,这并不是最优解(选取2个物品2,总价值14),所以贪心策略考虑的是局部最优,全局不一定最优。

2.贪心算法的特点

1.贪心策略没有标准,不同的问题选取的标准不同

2.贪心不一定得到全局最优解,正确的贪心策略需要被“证明”

证明方法:所有可用的数学证明方法


证明:找零问题的贪心策略

在例1中使用的贪心策略是每次选取尽可能大的货币,接下来证明它的正确性,即该贪心策略能够得出最优解。

分析最优情况下的性质

设不同面值货币使用张数分别为A,B,C,D

B有三种可能:B>2;B=2;B<2

当B>=2时,每两张10元货币都可以用一张20元货币代替,所以要使总货币张数最少,B只能<2。同理,C<2;D<5

569aab6e26b8463eae9327ffd279d641.png

设贪心策略下不同面值货币使用张数分别为a,b,c,d

现在只需证明a=A,b=B,c=C,d=D即可

根据贪心策略,显然a>=A。如果a>A,那么相差的每个20元,需要其它面值货币凑够,根据性质,B,C,D最大得到的总额是10+5+4=19元<20元,需要增加货币张数,不符合性质。所以a=A。

同理可证,b=B,c=C,d=D

7ae5161af8694b84963565c85aef4446.png

综上,该贪心策略得到的就是最优解。

3.如何学习贪心算法

1放平心态

贪心算法并不是一种模版,它是一种解题策略。对于一些题目,想不到正确的贪心策略很正常。

2积累经验

学习贪心算法时,应该把重点放在贪心的策略上,对于每一道题目的贪心策略,我们应该当成经验去吸收,积累多了,我们“贪心的思维”自然就熟练了。

3尝试证明

一些贪心题目的原理比较简单,理解了贪心算法后基本不需要证明,对于一些较难的题目,我们学会解决它的贪心策略后可以尝试理解或证明它的正确性。

题目练习(持续更新)

1.柠檬水找零(easy)

题目链接:柠檬水找零

题目描述:

abc2976277064cc98dc11ed3bcf6afa7.png

d600a6e50e5149a698c20906002aa8af.png

算法原理

1讨论找零情况:

e12df0a95f2a4d3a90e5be7bbd668fa5.png

2贪心策略

给20元找零有两种方式,需要选择最优的方式(完成更多的交易)

示例:已有5,5,5,10,下面的支付金额顺序是20,10

选择10+5方式找零,还剩5,5,可以用一个5给下一个10找零,true

选择5+5+5方式找零,给20找完后无剩余5,不能给下一个10找零,false

5元既可以给10元找零也可以给20元找零,所以本题的贪心策略是保留更多的5元,即给20找零优先使用10+5。

代码实现

用两个变量分别统计收下5,10的个数

找零(按分类讨论和贪心实现),5,10对应变量减去数量即可

无法找零返回false

C:

bool lemonadeChange(int* bills, int billsSize){int five = 0, ten = 0;for (int i = 0; i < billsSize; i++){// 分类讨论if (bills[i] == 5)five++;else if (bills[i] == 10){if (five == 0)return false;five--;ten++;}else{if (ten && five)// 贪心{ten--;five--;}else if (five >= 3){five -= 3;}elsereturn false;}}return true;
}

C++:

class Solution {
public:bool lemonadeChange(vector<int>& bills) {int five = 0, ten = 0;for (auto x : bills){// 分类讨论if (x == 5)five++;else if (x == 10){if (five == 0)return false;five--;ten++;}else{if (ten && five)// 贪心{ten--;five--;}else if (five >= 3){five -= 3;}elsereturn false;}}return true;}
};

证明(交换论证法)

交换论证法:假设一种接近贪心算法的最优算法,通过交换它的一个步骤或元素,该算法的最优性不变,或者更接近贪心算法(贪心算法更优),那么贪心算法就是最优解。

347c18c2e6de4336bdea03a083298632.png

证明该题目贪心策略的最优性:

假设最优解其中一步给20找零使用5+5+5

ff722ed8e0c24047a50dc982ce758743.png讨论:

①最优解后面没有用贪心解的那个10找零

用10交换最优解给20找零的其中2个5,其仍然是最优解

f7d03e61162145d19d3a4c5d0d6b8f4b.png

②最优解后面有一次用了贪心解的10找零

给20找零的其中两个5可以与后面使用的10交换,其仍然最优

4764dee0837847c3a9ad102c318f5066.png

综上,该贪心算法是最优解(正确解)


f5e5084bd79548cd97987473d6546bf8.gif

其它贪心题目会根据个人学习情况不定时更新,敬请期待。

如果本文内容对你有帮助,可以点赞收藏,感谢支持,期待你的关注。

相关文章:

贪心算法+练习

正值国庆之际&#xff0c;祝愿祖国繁荣昌盛&#xff0c;祝愿朋友一生平安&#xff01;终身学习&#xff0c;奋斗不息&#xff01; 目录 1.贪心算法简介 2.贪心算法的特点 3.如何学习贪心算法 题目练习&#xff08;持续更新&#xff09; 1.柠檬水找零&#xff08;easy&…...

使用华为eNSP组网试验⑷-OSPF多区域组网

今天进行了OSPF的多区域组网试验&#xff0c;本来这是个很简单的操作&#xff0c;折腾了好长时间&#xff0c;根本原因只是看了别人写的配置代码&#xff0c;没有真正弄明白里面对应的规则。 一般情况下&#xff0c;很多单位都使用OSPF进行多区域的组网&#xff0c;大体分为1个…...

P1843 奶牛晒衣服 【贪心】

P1843 奶牛晒衣服 【贪心】 题目背景 熊大妈决定给每个牛宝宝都穿上可爱的婴儿装 。但是由于衣服很湿&#xff0c;为牛宝宝晒衣服就成了很不爽的事情。于是&#xff0c;熊大妈请你&#xff08;奶牛&#xff09;帮助她完成这个重任。 题目描述 一件衣服在自然条件下用一秒的时间…...

91、Redis - 事务 与 订阅-发布 相关的命令 及 演示

★ 事务相关的命令 Redis事务保证事务内的多条命令会按顺序作为整体执行&#xff0c;其他客户端发出的请求绝不可能被插入到事务处理的中间&#xff0c; 这样可以保证事务内所有命令作为一个隔离操作被执行。 Redis事务同样具有原子性&#xff0c;事务内所有命令要么全部被执…...

GPU如何成为AI的加速器

0. 前言 按照国际惯例&#xff0c;首先声明&#xff1a;本文只是我自己学习的理解&#xff0c;虽然参考了他人的宝贵见解&#xff0c;但是内容可能存在不准确的地方。如果发现文中错误&#xff0c;希望批评指正&#xff0c;共同进步。 本文关键词&#xff1a;GPU、深度学习、GP…...

Map声明、元素访问及遍历、⼯⼚模式、实现 Set - GO语言从入门到实战

Map声明、元素访问及遍历 - GO语言从入门到实战 Map 声明的方式 m := map[string]int{"one": 1, "two": 2, "three": 3} //m初始化时就已经设置了3个键值对,所以它的初始长度len(m)是3。m1 := map[string]int{} //m1被初始化为一个空的m…...

机器人中的数值优化|【七】线性搜索牛顿共轭梯度法、可信域牛顿共轭梯度法

机器人中的数值优化|【七】线性搜索牛顿共轭梯度法、可信域牛顿共轭梯度法 Line Search Newton-CG, Trust Region Newton-CG 往期回顾 机器人中的数值优化|【一】数值优化基础 机器人中的数值优化|【二】最速下降法&#xff0c;可行牛顿法的python实现&#xff0c;以Rosenbro…...

websocket实现go(server)与c#(client)通讯

go 服务端 使用到github.com/gorilla/websocket package mainimport ("fmt""github.com/gorilla/websocket""log""net/http" )func main() {var upgrader websocket.Upgrader{ReadBufferSize: 1024,WriteBufferSize: 1024,CheckOr…...

洛谷题目题解详细解答

洛谷是一个很不错的刷题软件&#xff0c;可是找不到合适的题解是个大麻烦&#xff0c;大家有啥可以私信问我&#xff0c;以下是我已经通过的题目。 你如果有哪一题不会&#xff08;最好是我通过过的&#xff0c;我没过的也没关系&#xff09;&#xff0c;可以私信我&#xff0…...

【C语言】八大排序算法

文章目录 一、冒泡排序1、定义2、思想及图解3、代码 二、快速排序1、hoare版本2、挖坑法3、前后指针法4、非递归快排5、快速排序优化1&#xff09;三数取中选key值2&#xff09;小区间优化 三、直接插入排序1、定义2、代码 四、希尔排序1、定义2、图解3、代码 五、选择排序1、排…...

2023年中国智能电视柜产量、需求量、市场规模及行业价格走势[图]

电视柜是随着电视机的发展和普及而演变出的家具种类&#xff0c;其主要作用是承载电视机&#xff0c;又称视听柜&#xff0c;随着生活水平的提高&#xff0c;与电视机相配套的电器设备也成为电视柜的收纳对象。 随着智能家具的发展&#xff0c;智能电视机柜的造型和风格都是有了…...

docker容器使用初体验

我们写程序时&#xff0c;都会搭建相关的环境&#xff0c;比如写了一个web&#xff0c;使用了tomcat、nginx等&#xff0c;现在想要把程序部署到云服务器或者在其他电脑上运行&#xff0c;就需要重新部署一遍环境&#xff0c;尤其是项目开源后&#xff0c;上手成本大。 docker…...

React Hooks ——性能优化Hooks

什么是Hooks Hooks从语法上来说是一些函数。这些函数可以用于在函数组件中引入状态管理和生命周期方法。 React Hooks的优点 简洁 从语法上来说&#xff0c;写的代码少了上手非常简单 基于函数式编程理念&#xff0c;只需要掌握一些JavaScript基础知识与生命周期相关的知识不…...

C#学习系列相关之多线程(一)----常用多线程方法总结

一、多线程的用途 在介绍多线程的方法之前首先应当知道什么是多线程&#xff0c; 在一个进程内部可以执行多个任务&#xff0c;而这每一个任务我们就可以看成是一个线程。是程序使用CPU的基本单位。进程是拥有资源的基本单位&#xff0c; 线程是CPU调度的基本单位。多线程的作用…...

Vscode爆红Delete `␍`eslintprettier/prettier

一、先看报错 文件中爆红&#xff0c;提示 Delete ␍eslintprettier/prettier 二、解决方案 项目根目录下&#xff0c;.prettierrc.js 文件中&#xff1a; endOfLine: auto,三、重启VsCode 此时不在爆红&#xff0c;问题完美解决...

Mac安装Ecplise产品报错:dose not contain the JNI_CreateJavaVM symbol

1. 絮絮叨叨 工作中需要借助Ecplise Memory Analyzer (MAT)分析dump文件&#xff0c;直接下载、安装、运行MAT报错 询问同事后&#xff0c;同事说可以先安装Ecplise&#xff0c;再以插件的形式安装MAT下载、安装好Eclipse&#xff0c;点击运行仍然报错&#xff0c;且错误信息一…...

如何使用大语言模型来绘制图画

请创作一张科技感十足的图片&#xff0c;包含siri和iphone两个元素&#xff0c;请帮我挑选合适的style和background 好的&#xff0c;我会为你创作一张科技感十足的图片&#xff0c;包含siri和iphone两个元素。我会根据你的要求&#xff0c;选择一种适合的风格和背景。请稍等一…...

代码随想录算法训练营第23期day11 | 20. 有效的括号、1047. 删除字符串中的所有相邻重复项 、150. 逆波兰表达式求值

目录 一、&#xff08;leetcode 20&#xff09;有效的括号 二、&#xff08;leetcode 1047&#xff09;删除字符串中的所有相邻重复项 用栈存放 将字符串直接当成栈 三、&#xff08;leetcode 150&#xff09;逆波兰表达式求值 一、&#xff08;leetcode 20&#xff09;…...

数据结构-优先级队列(堆)

文章目录 目录 文章目录 前言 一 . 堆 二 . 堆的创建(以大根堆为例) 堆的向下调整(重难点) 堆的创建 堆的删除 向上调整 堆的插入 三 . 优先级队列 总结 前言 大家好,今天给大家讲解一下堆这个数据结构和它的实现 - 优先级队列 一 . 堆 堆&#xff08;Heap&#xff0…...

C++11新特性(语法糖,新容器)

距离C11版本发布已经过去那么多年了&#xff0c;为什么还称为新特性呢&#xff1f;因为笔者前面探讨的内容&#xff0c;除了auto&#xff0c;范围for这些常用的&#xff0c;基本上是用着C98的内容&#xff0c;虽说C11已经发布很多年&#xff0c;却是目前被使用最广泛的版本。因…...

使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式

一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明&#xff1a;假设每台服务器已…...

VB.net复制Ntag213卡写入UID

本示例使用的发卡器&#xff1a;https://item.taobao.com/item.htm?ftt&id615391857885 一、读取旧Ntag卡的UID和数据 Private Sub Button15_Click(sender As Object, e As EventArgs) Handles Button15.Click轻松读卡技术支持:网站:Dim i, j As IntegerDim cardidhex, …...

从零实现富文本编辑器#5-编辑器选区模型的状态结构表达

先前我们总结了浏览器选区模型的交互策略&#xff0c;并且实现了基本的选区操作&#xff0c;还调研了自绘选区的实现。那么相对的&#xff0c;我们还需要设计编辑器的选区表达&#xff0c;也可以称为模型选区。编辑器中应用变更时的操作范围&#xff0c;就是以模型选区为基准来…...

智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql

智慧工地管理云平台系统&#xff0c;智慧工地全套源码&#xff0c;java版智慧工地源码&#xff0c;支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求&#xff0c;提供“平台网络终端”的整体解决方案&#xff0c;提供劳务管理、视频管理、智能监测、绿色施工、安全管…...

23-Oracle 23 ai 区块链表(Blockchain Table)

小伙伴有没有在金融强合规的领域中遇见&#xff0c;必须要保持数据不可变&#xff0c;管理员都无法修改和留痕的要求。比如医疗的电子病历中&#xff0c;影像检查检验结果不可篡改行的&#xff0c;药品追溯过程中数据只可插入无法删除的特性需求&#xff1b;登录日志、修改日志…...

visual studio 2022更改主题为深色

visual studio 2022更改主题为深色 点击visual studio 上方的 工具-> 选项 在选项窗口中&#xff0c;选择 环境 -> 常规 &#xff0c;将其中的颜色主题改成深色 点击确定&#xff0c;更改完成...

YSYX学习记录(八)

C语言&#xff0c;练习0&#xff1a; 先创建一个文件夹&#xff0c;我用的是物理机&#xff1a; 安装build-essential 练习1&#xff1a; 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件&#xff0c;随机修改或删除一部分&#xff0c;之后…...

连锁超市冷库节能解决方案:如何实现超市降本增效

在连锁超市冷库运营中&#xff0c;高能耗、设备损耗快、人工管理低效等问题长期困扰企业。御控冷库节能解决方案通过智能控制化霜、按需化霜、实时监控、故障诊断、自动预警、远程控制开关六大核心技术&#xff0c;实现年省电费15%-60%&#xff0c;且不改动原有装备、安装快捷、…...

质量体系的重要

质量体系是为确保产品、服务或过程质量满足规定要求&#xff0c;由相互关联的要素构成的有机整体。其核心内容可归纳为以下五个方面&#xff1a; &#x1f3db;️ 一、组织架构与职责 质量体系明确组织内各部门、岗位的职责与权限&#xff0c;形成层级清晰的管理网络&#xf…...

《通信之道——从微积分到 5G》读书总结

第1章 绪 论 1.1 这是一本什么样的书 通信技术&#xff0c;说到底就是数学。 那些最基础、最本质的部分。 1.2 什么是通信 通信 发送方 接收方 承载信息的信号 解调出其中承载的信息 信息在发送方那里被加工成信号&#xff08;调制&#xff09; 把信息从信号中抽取出来&am…...