【贪心算法】专题练习一

发布时间:2023年12月24日

在这里插入图片描述

欢迎来到Cefler的博客😁
🕌博客主页:那个传说中的man的主页
🏠个人专栏:题目解析
🌎推荐文章:题目大解析(3)

在这里插入图片描述


前言
1.什么是贪心算法?——贪婪+鼠目寸光

贪心策略:解决问题的策略,局部最优->全局最优
(1)即把解决问题的过程分为若干步
(2)解决每一步的时候吗,都选择当前看起来“最优的”解法
(3)希望得到全局最优解

2.贪心算法的特点
(1) 贪心策略的提出是没有标准以及模板的
(2) 可能每一道题的贪心策略都是不同的
(3)贪心策略的正确性:可能会出错;正确的贪心策略,我们是需要“证明的”

3.证明贪心策略的方法:数学中见过的所有证明方法

4.学习贪心的方向
(1):遇到不会的贪心题,很正常,把心态放平
(2):把策略当成经验吸收
(3):能证明则证明贪心策略的正确性


👉🏻柠檬水找零

原题链接:柠檬水找零

mycode:

class Solution {
public:
    bool lemonadeChange(vector<int>& bills) {
        int five = 0,ten = 0,twenty = 0;
        for(auto e:bills)
        {
            if(e==5)
            {
                five++;
            }
            else if(e==10)
            {
                ten++;
                if(--five<0)
                    return false;
            }
            else if(e==20)
            {
                twenty++;
                //10+5 && 5+5+5 都不可以才找零失败
                int tmp1 = ten,tmp2 = five,tmp3 = five;
                if(--tmp1>=0&&--tmp2>=0)
                {
                    --ten;
                    --five;
                }
                else if((tmp3-=3)>=0)
                {
                    five-=3;
                }
                else
                    return false;
            }
        }
        return true;
    }
};

交换论证法
在这里插入图片描述

文章来源:https://blog.csdn.net/cefler/article/details/135183485
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。