贪心算法+练习
正值国庆之际,祝愿祖国繁荣昌盛,祝愿朋友一生平安!终身学习,奋斗不息!
目录
1.贪心算法简介
2.贪心算法的特点
3.如何学习贪心算法
题目练习(持续更新)
1.柠檬水找零(easy)
算法原理
代码实现
证明(交换论证法)
1.贪心算法简介
贪心策略:解决问题的一种策略,由局部最优->全局最优。
一般步骤:
1.把解决问题的过程分为若干步
2.解决每一步的时候,都选择当前“最优的”解法
3.“希望”得到全局最优解
例1:找零问题
有20,10,5,1面值货币若干张,如何用最少的张数支付46元?
贪心策略:每次选取尽可能大的货币
例2:背包问题
一个背包容量为8,有3种物品若干,选择要装的物品,使背包内物品总价值最大
贪心策略:每次选择单位体积价值尽可能大的物品。类似也可选择体积小(装更多的物品,总价值可能最大),价值大(每次选价值大的,总价值可能最大)。
通过贪心策略得到的结果是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
设贪心策略下不同面值货币使用张数分别为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
综上,该贪心策略得到的就是最优解。
3.如何学习贪心算法
1放平心态
贪心算法并不是一种模版,它是一种解题策略。对于一些题目,想不到正确的贪心策略很正常。
2积累经验
学习贪心算法时,应该把重点放在贪心的策略上,对于每一道题目的贪心策略,我们应该当成经验去吸收,积累多了,我们“贪心的思维”自然就熟练了。
3尝试证明
一些贪心题目的原理比较简单,理解了贪心算法后基本不需要证明,对于一些较难的题目,我们学会解决它的贪心策略后可以尝试理解或证明它的正确性。
题目练习(持续更新)
1.柠檬水找零(easy)
题目链接:柠檬水找零
题目描述:
算法原理
1讨论找零情况:
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;}
};
证明(交换论证法)
交换论证法:假设一种接近贪心算法的最优算法,通过交换它的一个步骤或元素,该算法的最优性不变,或者更接近贪心算法(贪心算法更优),那么贪心算法就是最优解。
证明该题目贪心策略的最优性:
假设最优解其中一步给20找零使用5+5+5
讨论:
①最优解后面没有用贪心解的那个10找零
用10交换最优解给20找零的其中2个5,其仍然是最优解
②最优解后面有一次用了贪心解的10找零
给20找零的其中两个5可以与后面使用的10交换,其仍然最优
综上,该贪心算法是最优解(正确解)
其它贪心题目会根据个人学习情况不定时更新,敬请期待。
如果本文内容对你有帮助,可以点赞收藏,感谢支持,期待你的关注。
相关文章:

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

使用华为eNSP组网试验⑷-OSPF多区域组网
今天进行了OSPF的多区域组网试验,本来这是个很简单的操作,折腾了好长时间,根本原因只是看了别人写的配置代码,没有真正弄明白里面对应的规则。 一般情况下,很多单位都使用OSPF进行多区域的组网,大体分为1个…...
P1843 奶牛晒衣服 【贪心】
P1843 奶牛晒衣服 【贪心】 题目背景 熊大妈决定给每个牛宝宝都穿上可爱的婴儿装 。但是由于衣服很湿,为牛宝宝晒衣服就成了很不爽的事情。于是,熊大妈请你(奶牛)帮助她完成这个重任。 题目描述 一件衣服在自然条件下用一秒的时间…...

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

GPU如何成为AI的加速器
0. 前言 按照国际惯例,首先声明:本文只是我自己学习的理解,虽然参考了他人的宝贵见解,但是内容可能存在不准确的地方。如果发现文中错误,希望批评指正,共同进步。 本文关键词: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 往期回顾 机器人中的数值优化|【一】数值优化基础 机器人中的数值优化|【二】最速下降法,可行牛顿法的python实现,以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…...

洛谷题目题解详细解答
洛谷是一个很不错的刷题软件,可是找不到合适的题解是个大麻烦,大家有啥可以私信问我,以下是我已经通过的题目。 你如果有哪一题不会(最好是我通过过的,我没过的也没关系),可以私信我࿰…...

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

2023年中国智能电视柜产量、需求量、市场规模及行业价格走势[图]
电视柜是随着电视机的发展和普及而演变出的家具种类,其主要作用是承载电视机,又称视听柜,随着生活水平的提高,与电视机相配套的电器设备也成为电视柜的收纳对象。 随着智能家具的发展,智能电视机柜的造型和风格都是有了…...
docker容器使用初体验
我们写程序时,都会搭建相关的环境,比如写了一个web,使用了tomcat、nginx等,现在想要把程序部署到云服务器或者在其他电脑上运行,就需要重新部署一遍环境,尤其是项目开源后,上手成本大。 docker…...
React Hooks ——性能优化Hooks
什么是Hooks Hooks从语法上来说是一些函数。这些函数可以用于在函数组件中引入状态管理和生命周期方法。 React Hooks的优点 简洁 从语法上来说,写的代码少了上手非常简单 基于函数式编程理念,只需要掌握一些JavaScript基础知识与生命周期相关的知识不…...

C#学习系列相关之多线程(一)----常用多线程方法总结
一、多线程的用途 在介绍多线程的方法之前首先应当知道什么是多线程, 在一个进程内部可以执行多个任务,而这每一个任务我们就可以看成是一个线程。是程序使用CPU的基本单位。进程是拥有资源的基本单位, 线程是CPU调度的基本单位。多线程的作用…...

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

Mac安装Ecplise产品报错:dose not contain the JNI_CreateJavaVM symbol
1. 絮絮叨叨 工作中需要借助Ecplise Memory Analyzer (MAT)分析dump文件,直接下载、安装、运行MAT报错 询问同事后,同事说可以先安装Ecplise,再以插件的形式安装MAT下载、安装好Eclipse,点击运行仍然报错,且错误信息一…...

如何使用大语言模型来绘制图画
请创作一张科技感十足的图片,包含siri和iphone两个元素,请帮我挑选合适的style和background 好的,我会为你创作一张科技感十足的图片,包含siri和iphone两个元素。我会根据你的要求,选择一种适合的风格和背景。请稍等一…...

代码随想录算法训练营第23期day11 | 20. 有效的括号、1047. 删除字符串中的所有相邻重复项 、150. 逆波兰表达式求值
目录 一、(leetcode 20)有效的括号 二、(leetcode 1047)删除字符串中的所有相邻重复项 用栈存放 将字符串直接当成栈 三、(leetcode 150)逆波兰表达式求值 一、(leetcode 20)…...

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

C++11新特性(语法糖,新容器)
距离C11版本发布已经过去那么多年了,为什么还称为新特性呢?因为笔者前面探讨的内容,除了auto,范围for这些常用的,基本上是用着C98的内容,虽说C11已经发布很多年,却是目前被使用最广泛的版本。因…...

C++_核心编程_多态案例二-制作饮品
#include <iostream> #include <string> using namespace std;/*制作饮品的大致流程为:煮水 - 冲泡 - 倒入杯中 - 加入辅料 利用多态技术实现本案例,提供抽象制作饮品基类,提供子类制作咖啡和茶叶*//*基类*/ class AbstractDr…...
【Linux】shell脚本忽略错误继续执行
在 shell 脚本中,可以使用 set -e 命令来设置脚本在遇到错误时退出执行。如果你希望脚本忽略错误并继续执行,可以在脚本开头添加 set e 命令来取消该设置。 举例1 #!/bin/bash# 取消 set -e 的设置 set e# 执行命令,并忽略错误 rm somefile…...
IGP(Interior Gateway Protocol,内部网关协议)
IGP(Interior Gateway Protocol,内部网关协议) 是一种用于在一个自治系统(AS)内部传递路由信息的路由协议,主要用于在一个组织或机构的内部网络中决定数据包的最佳路径。与用于自治系统之间通信的 EGP&…...

解决Ubuntu22.04 VMware失败的问题 ubuntu入门之二十八
现象1 打开VMware失败 Ubuntu升级之后打开VMware上报需要安装vmmon和vmnet,点击确认后如下提示 最终上报fail 解决方法 内核升级导致,需要在新内核下重新下载编译安装 查看版本 $ vmware -v VMware Workstation 17.5.1 build-23298084$ lsb_release…...

最新SpringBoot+SpringCloud+Nacos微服务框架分享
文章目录 前言一、服务规划二、架构核心1.cloud的pom2.gateway的异常handler3.gateway的filter4、admin的pom5、admin的登录核心 三、code-helper分享总结 前言 最近有个活蛮赶的,根据Excel列的需求预估的工时直接打骨折,不要问我为什么,主要…...

【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力
引言: 在人工智能快速发展的浪潮中,快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型(LLM)。该模型代表着该领域的重大突破,通过独特方式融合思考与非思考…...
Java多线程实现之Callable接口深度解析
Java多线程实现之Callable接口深度解析 一、Callable接口概述1.1 接口定义1.2 与Runnable接口的对比1.3 Future接口与FutureTask类 二、Callable接口的基本使用方法2.1 传统方式实现Callable接口2.2 使用Lambda表达式简化Callable实现2.3 使用FutureTask类执行Callable任务 三、…...

【配置 YOLOX 用于按目录分类的图片数据集】
现在的图标点选越来越多,如何一步解决,采用 YOLOX 目标检测模式则可以轻松解决 要在 YOLOX 中使用按目录分类的图片数据集(每个目录代表一个类别,目录下是该类别的所有图片),你需要进行以下配置步骤&#x…...
AGain DB和倍数增益的关系
我在设置一款索尼CMOS芯片时,Again增益0db变化为6DB,画面的变化只有2倍DN的增益,比如10变为20。 这与dB和线性增益的关系以及传感器处理流程有关。以下是具体原因分析: 1. dB与线性增益的换算关系 6dB对应的理论线性增益应为&…...
【JavaSE】多线程基础学习笔记
多线程基础 -线程相关概念 程序(Program) 是为完成特定任务、用某种语言编写的一组指令的集合简单的说:就是我们写的代码 进程 进程是指运行中的程序,比如我们使用QQ,就启动了一个进程,操作系统就会为该进程分配内存…...