【贪心算法】贪心算法一_贪心算法案例
贪心算法一
- 1.柠檬水找零
- 2.将数组和减半的最少操作次数
- 3.最大数
- 4.摆动序列
点赞👍👍收藏🌟🌟关注💖💖
你的支持是对我最大的鼓励，我们一起努力吧!😃😃
1.柠檬水找零
题目链接： 860. 柠檬水找零
题目分析：
这里有两点需要注意：
- 顾客排队购买你的产品
- 一开始你手头没有任何零钱，你要拿着顾客的钱去找钱
顾客排队购买你的产品，也就是说如果第一个顾客给你10或者20美元你就找不了，返回false。
算法原理：
这里我们只关注正确的贪心策略，不用管它怎么来的。最后我们来证明一下。
贪心可不是上来就贪，而是在分析问题的过程中，发现可以贪，我们才贪。
这道题就是一个找零问题，顾客会给5美元，10美元，20美元。我们分情况给他找钱就可以了。
当顾客给5块钱，我们直接收下就行了
当顾客给10块钱，我们要找5块钱，顺手把10块钱收下，但是找5元前提是我们有5块钱可以找，如果没有返回false
当顾客给20块钱，关于20块钱找零其实我们有两种策略，
第一种：找一张10块钱，在找一张5块钱
第二种：找三张5块钱
此时就有分歧了，我们要想哪一种最好，这就体现了贪心。贪心就体现在这一步，我们应该选择更优的策略来完成这个找零工作。
到底那个优秀，其实是根据5块钱来的，5块钱不仅完成20块钱找零工作，还能完成10块钱找零工作。因此我们尽量保留5块钱。
所以看起来当前最优策略就是第一种策略。如果第一种策略不成立，我们再选第二种策略，如果第二种策略都不成立就返回false
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; five--; ten++; } else { if(ten && five) //贪心 { ten--; five--; } else if(five >= 3) { five -= 3; } else return false; } } return true; }};证明：贪心策略是正确的
证明策略：交换论证法
假设
贪心策略解决这道题的方法顺序是：a、b、c、d、e、f，
最优解解决这道题的方法顺序是：e、b、c、d、a、f
此时如果在不破坏最优解的 “最优性质的” 前提下，能够将最优解调整成贪心解。那我们就说贪心解就是最优解。
这就是我们的交换论证法，交换论证法的核心就是找到不破坏最优性质的前提下把假设出来的最优解逐步的调整出贪心解。
如果顾客给我们5美元或者10美元，贪心解和最优解是没有区别的。5块就收下，10块就找5块。
