简单到爆炸der贪心算法学习及其证明方法其一:交换论证法

这篇具有很好参考价值的文章主要介绍了简单到爆炸der贪心算法学习及其证明方法其一:交换论证法。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

贪心算法理论:

贪心算法接地气的讲就是贪婪加上鼠目寸光,不像我只会心疼哥哥(啊不是)。

贪心算法解题策略:

通过局部寻找最优解,来试图(不一定就是)寻找到全局的最优解。

实现操作如下:

1.先将做题步骤分为若干步,与分治法有部分相似(后半句算法导论说的,我就负责蹭蹭名气)

2.然后在执行若干步时,对每步操作进行当前阶段的最优解(之所以不一定求得全局最优解皆因为此时鼠目寸光的特性,就比如一个贪官收到礼物时,不管未来与前途,在当时看来只有收下有钱,和拒绝没钱这两个选项,然后使用贪心策略选择了收礼,然后g)

3.最后执行若干个步骤的最优解后返回结果,希望得到最优解。

特点:

1.贪心策略的提出

a.贪心策略的提出没有标准与模板,同一道题会有多种贪心的思路在每一步渴求所想要的相对最优解。

例如一个背包装物品,不同物品有不同的价格和体积,想要装进最大的价值东西,使用贪心策略就有从每次装物品装价值最大的或者每次装东西装体积最小的或者每次装东西装价格/体积的值最大的这三种贪心思路(虽然都不对)

b.贪心策略的提出对于每道题都有不同的思路与解法,不能将一道题的思路套用到任意题中(但是并不是说刷题没有用)

2.贪心策略的正确性

因为贪心策略不一定是正确的,可能是个错误方法所以需要论证。(也就是后续会讲到的证明方法,证明方法不只今天提到的一个,后续会继续更新证明方法以及例题,如果想早看到新内容,请动动发财的小手关注我一下哦)

证明方法1:交换论证法

交换论证法就是用知道头脑中的明了了的最优解时,在不改变最优解的前提下,能够将最优解调整为贪心解(现在有点生涩,一会有个例题以及对应解决方法可以结合着看)

例题:力扣题目860柠檬水找零

贪心法交换论证法证明,炒鸡简单der贪心算法,贪心算法,学习,算法

贪心法交换论证法证明,炒鸡简单der贪心算法,贪心算法,学习,算法

对数据理解

这里看完题目后我们可以(知道,美国柠檬水贩子真黑心,5dollars一杯,真万恶。)

还有正经的就是知道了我们要处理的数据在1e5的范围内,直接暴力一一枚举出来冲他。

具体实现贪心

操作一

然后这里可以发现我们可以将每一个收到的钱找零的过程看成一个步骤

操作二

我们要处理的数据只有5,10,20.因为没有要用到20找零钱的情况,所以只要判断收到20元时能不能找开钱的情况,不用考虑用20找零钱的情况。

然后收到10元时,直接给五元,或者返回false。

以上两种情况选择固定不需要考虑贪心

但收到20时,就要考虑一下了,一种方式是给3张5元,另一种方式是给1张10元一张5元。

我们思考一下,十元只能用于20元找零,但5元可以用于20元和10元的找零,方便我们给更多的人找零,做更多生意,收更多的dollar,所以我们尽可能的保留5元款。也就是先判断是否有十元,和五元如果都有就给10元和5元。如果没有十元,那就给3张5,如果也没有那就return false

实现代码为:(非最优化代码,做个参考就行)

class Solution {
public:
    bool lemonadeChange(vector<int>& bills) {
        int five=0,ten=0;
        for(int i:bills)
        {
            if(i==5)
            five++;
            else if(i==10)
            {
               if(five==0)
               return false;
               else
               five--;
               ten++;
            }
            else
            {
                if(ten!=0&&five!=0)
                {
                    ten--;five--;
                }
                else if(ten==0&&five>=3)
                five-=3;
                else return false;
            }
        }
        return true;
    }
};

操作三

希望得到全局最优解,则就需要我们证明一下了,交换论证法

我们可以知道我们应该尽可能的多做生意,也就i是要求我们能更多的给人找到合适零钱。

这里我们举个对拍来思考,如果我们举了5,10,5,10那我们就发现贪心算法和全局最优解没有区别因为都要遇到5元收着,遇到十元交出5元。所以发现在对于5元和10元时我们不需要调整最优解便已经等于了贪心解。

所以唯一有区别的就是遇到20元时,我们贪心解是先考虑吧10+5.但最优解可能会使用5+5+5.但是10元钱只能用于20元找零,其他情况都用不到给不出去,对于除了20元的情况外没有任何影响,所以在这20元的情况中,我们可以将最优解的5+5+5换成10+5(并不是因为考虑多做生意等什么考虑因素,单纯是因为,两张五块换成十块也不会对此次20元情况有影响)

所以这里最优解的20元情况调整成了贪心解的情况且没有影响到最优解。所以论证成功。

请公主少爷点赞收藏加关注文章来源地址https://www.toymoban.com/news/detail-778737.html

到了这里,关于简单到爆炸der贪心算法学习及其证明方法其一:交换论证法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 算法通关村第十七关:青铜挑战-贪心其实很简单

    1. 难以解释的贪心算法 贪心学习法则:直接做题,不考虑贪不贪心 贪心(贪婪)算法 是指在问题尽心求解时,在每一步选择中都采取最好或者最优(最有利)的选择,从而希望能够导致结果最好或者最优的算法 贪心算法所得到的结果不一定是最优的结果,但是都是相对近似最

    2024年02月09日
    浏览(38)
  • 算法设计方法之贪心算法

    贪心算法是算法设计的一种方法。期盼通过每个阶段的局部最优选择,从而达到全局的最优。但结果不一定是最优的。 场景一 零钱兑换 现有硬币 1 元、2 元、5 元,需要用最少的硬币数量凑够 11 元。 利用贪心算法实现,优先考虑最好的结果就是面值为 5 元的硬币,11 = 5 +

    2024年02月17日
    浏览(43)
  • 跳跃游戏 (DFS->记忆化搜索->动态规划/贪心证明)

            跳跃游戏是一种典型的算法题目,经常是给定一数组arr,从数组的某一位置i出发,根据一定的跳跃规则,比如从i位置能跳arr[i]步,或者小于arr[i]步,或者固定步数,直到到达某一位置,可能是数组的最后一个位置,也有可能是某一特别的数值处,也有可能在这个

    2024年02月03日
    浏览(36)
  • 秒懂百科,C++如此简单丨第二十天:贪心算法2

    目录 Everyday English 前言 洛谷 P1031 均分纸牌 题目描述 思路点拨 AC代码 洛谷 P1094 纪念品分组 题目描述 样例输入 样例输出  思路点拨 AC代码 洛谷 P2660 zzc 种田  题目描述 思路点拨 AC Code 结尾 Don\\\'t miss the opportunity. 机不可失,时不再来。 这节课是贪心算法的习题课,我们会讲解

    2024年02月20日
    浏览(38)
  • 动手学区块链学习笔记(二):区块链以及工作量证明算法

    紧接上文,在介绍完区块链中的加密解密以及公钥私钥等算法后,本篇开始正式进入区块链概念与一个简单区块链系统的实现过程介绍。 什么是区块链? 区块链,就是一个又一个区块组成的链条。每一个区块中保存了一定的信息,它们按照各自产生的时间顺序连接成链条。

    2024年01月17日
    浏览(50)
  • 贪心算法学习——最长单调递增子序列

    目录 ​编辑 一,题目 二,题目接口 三,解题思路和代码 给你一个整数数组  nums  ,找到其中最长严格递增子序列的长度。 子序列  是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如, [3,6,2,7]  是数组  [0,3,1,6,2,2,7]  的子序列。  

    2024年02月08日
    浏览(40)
  • 【算法日志】图论 并查集及其简单应用

    并查集是一种算法设计思想,通过判断两个元素是否在同一个集合里,常用来解决一些和图相关的连通性问题。 并查集主要有以下两个功能: 将两个元素添加到一个集合中。 判断两个元素是否是在一个集合之中(这一功能够有效判断是否成环)。 主要思想: 通过创建一个数组

    2024年01月23日
    浏览(46)
  • 【夜深人静学习数据结构与算法 | 第六篇】贪心算法

    目录 前言: 引入: 贪心算法:     455. 分发饼干 - 力扣(LeetCode) 376. 摆动序列 - 力扣(LeetCode) 53. 最大子数组和 - 力扣(LeetCode) 122. 买卖股票的最佳时机 II - 力扣(LeetCode)         在本文我们将为大家介绍在计算机中比较常见的一种算法:贪心算法。他并没有具体的代

    2024年02月09日
    浏览(47)
  • 【机器学习 | 朴素贝叶斯】朴素贝叶斯算法:概率统计方法之王,简单有效的数据分类利器

    🤵‍♂️ 个人主页: @AI_magician 📡主页地址: 作者简介:CSDN内容合伙人,全栈领域优质创作者。 👨‍💻景愿:旨在于能和更多的热爱计算机的伙伴一起成长!!🐱‍🏍 🙋‍♂️声明:本人目前大学就读于大二,研究兴趣方向人工智能硬件(虽然硬件还没开始玩,但一直

    2024年02月15日
    浏览(52)
  • 【数学分析】闭区间套定理及其证明

    业余爱好者学习温故数学知识,做个记录。 如果数列 { a n } , { b n } {a_n}, { b_n } { a n ​ } , { b n ​ } 满足: (1) a n − 1 ≤ a n ≤ b n ≤ b n − 1 ,      ∀ n a_{n-1} leq a_n leq b_n leq b_{n - 1}, forall n a n − 1 ​ ≤ a n ​ ≤ b n ​ ≤ b n − 1 ​ ,         ∀ n (2) lim ⁡ n → ∞

    2024年02月06日
    浏览(31)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包