【算法:贪心】:贪心算法介绍+基础题(四个步骤);柠檬水找零(交换论证法)

🎁个人主页:我们的五年

🔍系列专栏:C++课程学习

🎉欢迎大家点赞👍评论📝收藏⭐文章

前言:

暑假马上就要留校学习算法了,现在先学习一下基本的算法打打基础。本篇要讲的是贪心算法的介绍,然后会讲两道基础的题目,用的贪心证明方法是:交换论证法。目前对贪心算法还是很感兴趣的,贪心没有固定的解法,遇到不会的,希望我可以把这种贪心算法搞清楚。

贪心算法:

🍩1.概念:

贪心算法是把问题分成很多步,每次都是选择看起来最优的那一步,就可以得到正确的答案。能用贪心解决的问题是具有贪心性质的。要想能用贪心解题,需要充分挖掘题目的条件。而且没有固定的模式。

🍩2.步骤:

对于一道贪心题,要解决并学会,可以分为:

1.题目解析。2.算法原理。3.手撕代码。4.贪心策略证明。

对于一道贪心题,可能前三步很简单,但是第四步一定是可以多多思考,多多证明的。在证明贪心策略的过程也是很有趣的。

🍩3.对于学习贪心算法建议:

贪心算法,没有一个固定的模式,我不是孙膑。我更多是去学习别人的贪心方法,并理解运用。所以在遇到有一些贪心问题的时候,我们可能没有任何思路,但是我们可以看别人的贪心解法,然后学习别人的思路。能把别人想出来的东西运用,也是一节伟大事情。

例题1

LeetCode:柠檬水找零(860)

860. 柠檬水找零 - 力扣(LeetCode)

🍩1.题目解析:

●每杯柠檬水售价5元。

●顾客排队购买。

●顾客向你付给你的钞票面额:5元,10元,20元。对于10元的,要找一张五块钱。对于20元的,你可以找三张五块钱,也可以找一张五块钱和一张十块钱。

●一开始没有零钱,也就是只能有顾客的钱来找零。

🍩2.算法原理:

1.对于顾客给的五块钱,我们直接收下,不需要找零。


2.对于顾客付的十块钱,我们将十块钱收下,然后进行找五块钱。


3.对于顾客付的二十块钱,我们有两种找零的方式。

找零一:找三张五块钱的。

找零二:找一张十块钱的, 找一张五块钱的。

🚁🚁🚁

从上面三种情况来看,五块钱有两种用途,十块钱只有一种用途(十块钱只能用来找零二十块钱的)。贪心解的情况下就是在找零二十块钱的时候,如果有十块钱就先用十块钱找(即找零方法一)。如果没有十块钱,才用三张五块钱进行找零。

🍩3.手斯代码:

class Solution {
public:
    bool lemonadeChange(vector<int>& bills) {
        int five=0,ten=0;   //20元有和没有都没关系
        for(auto& i:bills)
        {
            if(i==5)
                ++five;
            else if(i==10)
            {
                if(five)
                {
                    --five;
                    ++ten;
                }
                else
                    return false;
            }
            else if(i==20)
            {
                //有十块钱时,先用十块钱
                if(ten&&five)
                {
                    --ten;
                    --five;
                }
                else if(five>=3)
                {
                    five-=3;
                }
                else
                    return false;
            }
        }
        return true;
    }
};

🍩4.证明贪心策略:

在这道题中,贪心解和正确解的不同只发生在找零二十块钱的时候,贪心解用十块钱和五块钱进行找零,正确解用三张五块钱的进行找零。

🎡情况一:对于贪心解中用的十块钱,如果后面我们没有在正确解中用这十块钱,就直接用十块钱替换正确解的两种五块钱就得到了贪心解。

🎡情况二:如果后面正确解要用贪心解里的十块钱,那么此时用两张五块钱进行替换,也是满足最优性质的。

相关推荐

  1. 贪心算法】之买柠檬水

    2024-07-10 23:56:03       49 阅读

最近更新

  1. easyExcel

    easyExcel

    2024-07-10 23:56:03      0 阅读
  2. 什么是等保测评

    2024-07-10 23:56:03       0 阅读
  3. acml可用订阅到起始位姿

    2024-07-10 23:56:03       0 阅读
  4. Windows 12 网页版

    2024-07-10 23:56:03       0 阅读
  5. 网络融合的艺术:Xcode中应用Web服务集成全指南

    2024-07-10 23:56:03       0 阅读
  6. 提示工程的技术与策略分类

    2024-07-10 23:56:03       0 阅读
  7. css font 优化

    2024-07-10 23:56:03       0 阅读
  8. 基于深度学习的金融交易

    2024-07-10 23:56:03       0 阅读
  9. MATLAB中balance函数用法

    2024-07-10 23:56:03       0 阅读
  10. 栈和队列之间有哪些区别

    2024-07-10 23:56:03       0 阅读
  11. python 爬虫技术 第04节 函数和模块

    2024-07-10 23:56:03       0 阅读
  12. 打造安全堡垒:Xcode应用权限管理全解析

    2024-07-10 23:56:03       0 阅读

热门阅读

  1. std::deque和std::list的区别是什么

    2024-07-10 23:56:03       4 阅读
  2. 华为OD机试(C卷,200分)- 字符串拼接、田忌赛马

    2024-07-10 23:56:03       5 阅读
  3. 如何设置PHP wkhtmltopdf

    2024-07-10 23:56:03       6 阅读
  4. yolov5中训练长条型目标召回率低问题

    2024-07-10 23:56:03       8 阅读
  5. openssl error:0A000126:SSL routines:ssl3_read_n:unexpected eof

    2024-07-10 23:56:03       9 阅读
  6. 各种软件启动方式

    2024-07-10 23:56:03       6 阅读
  7. 【创作纪念日】我的三周年创作纪念日

    2024-07-10 23:56:03       7 阅读