【算法】-贪心算法

简介

贪心算法（Greedy Algorithm）是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法。贪心算法并不保证得到最优解，但在很多情况下，它的结果已经足够好，且实现简单，效率高。

什么是贪心算法

贪心策略：解决问题的策略，局部最优->全局最优

1. 把问题的过程分为若干步
2. 解决每一步的时候，都选择当前看起来“最优”的解法
3. “希望”得到全局最优解

贪心算法的特点

1. 贪心策略的提出
   贪心策略的提出是没有标准以及模板的
   可能每道题的贪心策略都不同

2. 贪心策略的正确性
   因为有可能“贪心策略”是一个错误的方法，我们可以用常见的证明方法去证明。

例题

860.柠檬水找零

860.柠檬水找零

题目是问我们能否正确找零，能返回true，不能返回false，这里注意一开始我们手上没有零钱，只能用收取的钱找零。

贪心
分类讨论：
5元----->收下
10元----->找5元，收下

20元---->找10 +5
------>找5+5+5

通过分类讨论我们看到，5元既能找给10元，又能找给20元，所以这里的贪心策略是尽可能留下多的5元在手中，能用10找零就用10

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

2208.将数组和减半的最少操作数

2208.将数组和减半的最少操作数

由题：我们要进行一个操作：将数组中的一个数减半，使得数组和为原数组和的一半或以下，求最小的操作数。
很容易想到，我们每次让数组中最大的数减半，则能得到最小的操作数。获取每次数组的最大数我们可以用大根堆

具体解法：贪心+大根堆

具体策略：
每次挑选当前数组中最大的那个数，然后减半
直到数组和减少到至少一半为止

class Solution {
public:int halveArray(vector<int>& nums) {priority_queue<double> heap;double sum=0.0;for(int x:nums){heap.push(x);sum+=x;}sum/=2.0;int count=0;while(sum>0){double t=heap.top()/2;sum-=t;count++;heap.pop();heap.push(t);}return count;}
};