目录

一、基本概念

二、举几个例子，便于理解

1、找零问题

2、最小路径和

3、背包问题

1）只考虑体积的贪心策略：

2） 只考虑价值的贪心策略：

三、贪心策略的特点

四、贪心策略证明

四、如何学习贪心

五、例题分析

第一题

1、题目描述

2、贪心策略分析

3、代码

 第二题

1、题目描述

2、贪心策略分析

3、代码

 第三题

1、题目描述

2、贪心策略分析

3、代码

 第四题

1、题目描述

2、贪心策略分析

3、代码

---

一、基本概念

什么是贪心算法？
贪心算法不是一个具体的算法，而是一个策略。
具体的策略是：
1、把解决问题的过程氛围若干步
2、解决每一步，都选择当前看起来“最优”的解法
3、最后希望得到一个全局最优解。

二、举几个例子，便于理解

1、找零问题

你是一个超市前台，你有面额为【20，10，5，1】的零钱，数量不限
有个顾客来买东西，要找零50块。
你要给他找零，要求是给的钞票数最少。
按照贪心的策略，核心是我只考虑当前步数的最优的选法。
所以，按照贪心策略，我不管三七二十一，我不管后面怎么样子，我就只管当前的情况。
所以，50块，我先找两张最大的20
剩下10块，然后找一张10块。
结束。

2、最小路径和

以下有一个表格，

每一次只能向下或者向右走，现在要求从左上角走到右下角走的路径最小。
贪心法的策略就是：我不管三七二十一，那个小，我就走那个。我不管后面怎么样子，我就只管现在这一步。
因此：

3、背包问题

假设我们有以下几种物品，每种物品有价值和体积两个属性：
物品 A：价值 10，体积 2
物品 B：价值 8，体积 3
物品 C：价值 5，体积 4
物品 D：价值 3，体积 1
背包体积为8。现在要求尽可能的装东西，体积不超过8，要求价值最大化。

1）只考虑体积的贪心策略：

贪心的策略就是：我不管你别的，那个小，我选那个。
所以我直接选了8个D，3*8 -21；
但是实际上最佳的选择是4个A，价值为40.

2） 只考虑价值的贪心策略：

别的我不管，那个价值大我放那个。
所以按照价值从大到小的顺序选择物品放入背包。
选择4个价值最大的A，总价值为40.

三、贪心策略的特点

根据上述三个简单例子的理解，我们可以总结归纳贪心策略特点如下：
1、贪心策略没有标准和模板可以套用，需要具体问题具体分析
2、贪心策略所得结果无法保证最优解（因此，需要严格证明策略的正确性）

四、贪心策略证明

常用证明方法（数学方法）：
1、贪心选择性质：证明贪心算法每一步的选择都是局部最优的，即当前情况下的最佳选择，不考虑未来可能发生的情况。
2、反证法：假设贪心算法得到的解不是最优解，然后推导出这个假设的结果与实际情况不符，从而证明贪心算法得到的解必须是最优的。
3、交换证明：通过比较贪心算法选择的解和任何其他算法选择的解，证明贪心算法的解比其他算法的解更优或者至少一样好。
4、拼接法：通过将贪心算法得到的局部最优解与其他算法得到的解拼接或组合，证明贪心算法整体上是最优的。

四、如何学习贪心？

根据以上内容，我们怎么学习贪心？
1、遇到不会做的贪心题目，非常正常，非常常见。
不会就去查，就去搜，就去模仿。
先积累模仿，再总结经验，慢慢积累，找感觉。
这就够了，不要想太多。
2、其次，慢慢的，要学会自己去证明贪心策略正确性的过程。

五、例题分析

第一题

1、题目描述

860. 柠檬水找零

  在柠檬水摊上，每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。
每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。
注意，一开始你手头没有任何零钱。
给你一个整数数组 bills ，其中 bills[i] 是第 i 位顾客付的账。如果你能给每位顾客正确找零，返回 true ，否则返回 false 。

2、贪心策略分析

5元不用找，10元找5元，20元找一张10和一张5，而不是3张5。每一次找零都尽可能的留下5，把10兑换出去。

3、代码

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

 第二题

1、题目描述

2208. 将数组和减半的最少操作次数 - 力扣（LeetCode）

给你一个正整数数组 nums 。每一次操作中，你可以从 nums 中选择 任意 一个数并将它减小到 恰好 一半。（注意，在后续操作中你可以对减半过的数继续执行操作）

请你返回将 nums 数组和 至少 减少一半的 最少 操作数。

2、贪心策略分析

每一次选择该数组中最大数字减半，可以使用一个堆，c++中对应的容器是优先队列，priority_queue。

3、代码

class Solution {
public:
    int halveArray(vector<int>& nums) {
        //用优先队列
        //每一次选取top出队列，减半，再插入队列
        //如此保证每一次选择得数据都是最大的
        std::priority_queue<double> q;
        double sum = 0;
        for(auto e : nums)
        {
            sum += e;
            q.push(e);
        }
        double count = 0;
        double half = sum / 2;
        double ret = sum ;

        while(!q.empty())
        {
            double top = q.top() / 2;
            q.pop();
            q.push(top);
            ret -= top;
            count++;
            
            if(ret <= half)
            {
                break;
            }
            
        }
        return count;
    }
};

 第三题

1、题目描述

179. 最大数 - 力扣（LeetCode）

2、贪心策略分析

本题的本质是确定元素的先后顺序
但是，排序规则不同于以往的大小，而是以结果大小为标准。
因此，贪心策略：每一次选择，选择两个数字进行组合，看a和b组合，是ab大还是ba大。

lambda表达式：
[](参数列表){返回值}

3、代码

class Solution {
public:
    string largestNumber(vector<int>& nums) {
        //转换成字符串
        vector<string> v;
        for(auto x : nums)
        {
            v.push_back(to_string(x));
        }
        
            //按照规则排序
            //在范围内进行排序，同时使用lambad表达式
            sort(v.begin(),v.end(),[](const string& s1, const string& s2)
            {
                return s1 + s2 > s2 + s1;
            });
        

        string ret;
        for(auto& e : v)
        {
            ret += e;
        }

        if(ret[0] == '0')
        {
            return "0";
        }

        return ret;
    }
};

 第四题

1、题目描述

376. 摆动序列 - 力扣（LeetCode）

2、贪心策略分析

贪心策略：
当升序时，选择升序序列最大的，保证后面有更多的降序数字满足摆动
当降序时，选择降序序列最小的，保证后面有更多的升序数字满足摆动
即，波峰和波谷。

怎么判断该数字是不是波峰/波谷？
设置状态
设置一个数字的左边和右边
如果left*right<0
说明，要么是波峰，要么是波谷。

3、代码

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        if(nums.size() < 2)
            return 1;

        int ret = 0;
        int left = 0;

        for(int i = 0; i < nums.size() - 1; i++)
        {
            int right = nums[i+1] - nums[i];
            if(right == 0)//非波峰/谷
                continue;

            if(left * right <= 0)//该点是一个波峰/波谷
                ret++;

            left = right;
        }

            return ret + 1;
    }
};