什么是贪心算法？？？
贪心算法是指通过每一次都选择最优解情况，然后通过局部最优从而达到全局最优，简单理解为目光短浅，走一步看一步。
需要注意的是，贪心算法是一种思想，而非直接的方法！！！
下面我们进入具体的贪心算法中来帮助大家理解贪心其思想
一.最少硬币问题
下面我们通过leedcode上面的这题来带大家了解最简单的贪心：最少硬币问题
需要注意的是：
我们的钱只有三种：5 10 20
由于我们开始手里没钱，所以如果第一位顾客给的不是5元，那么直接false，如果是5元
接下来我们就需要统计我们手里的5元钱数和10元钱数，注意不需要统计20元钱数，因为20元根本不参与找钱，然后就是一边统计一边找钱，检查是否可行
贪心点：如果用户给10元我们只能找5元，但是如果用户给20元我们是有选择的，可以10+5，也可以3*5，所以这里我们优先选择10+5,就是贪心策略（保障手里的5元钱可以尽可能满足更多用户）
解题代码：
class Solution {
public:
bool lemonadeChange(vector<int>& bills)
{
if(bills[0]!=5)
{
return false;
}
else
{
int five=0,ten=0;
for(auto i:bills)
{
if(i==5)five++;
else if(i==10)
{
if(five==0)
return false;
else
{
five--;
ten++;
}
}
else
{
if(ten&&five)
{
ten--,five--;
}
else if(five>=3)
{
five-=3;
}
else
return false;
}
}
return true;
}
}
};如果你认为选硬币就是贪心问题的话，我再带大家看一道题：
来源：洛谷
看完题目，感觉没错就是通过局部最优，从而到全局最优情况好，现在我们来看看下面情况：
如果n==15，如果按照贪心思路，就是选11+1+1+1+1共5个硬币，但是如果选5元的只需要3个是不是就错了，实际上这题考察的是dp（动态规划）
如果你学过了dp，可以写下，但是如果你还没学，可以跳过我的代码实现：
#include<bits/stdc++.h>
using namespace std;
const int M=1e6+1;
int n;
int dp[M];
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
dp[i]=dp[i-1]+1;//注意{0,1,2,3,4,1,2,3,4,5,2,1};
if(i>=5)
dp[i]=min(dp[i],dp[i-5]+1);
if(i>=11)
dp[i]=min(dp[i],dp[i-11]+1);
}
cout<<dp[n]<<'\n';
return 0;
}此时的你是不是非常好奇，什么时候是贪心呢？？？
贪心通常有如下两种结构：
1.最优子结构性质
当一个问题的最优解包含其子问题的最优解时，则此问题具有最优子结构
2.贪心选择性质：
问题整体的最优解可以通过一系列局部最优解得到
此时我们回到第二题，发现15元钱时，选择11元并不是其子问题最优解，也无法满足性质2
关于这方面的题，我也没有找到太多，希望大家谅解！！！
答案：
#include <bits/stdc++.h>
using namespace std;
int n,coin;
int main()
{
//输入
cin>>n;
coin=1024-n;
int count=0;
//贪心
while(coin)
{
if(coin>=64)
{
coin-=64;
count++;
}
else if(coin<64&&coin>=16)
{
coin-=16;
count++;
}
else if(coin<16&&coin>=4)
{
coin-=4;
count++;
}
else
{
coin-=1;
count++;
}
}
//输出
cout<<count<<endl;
return 0;
}二.活动安排问题
该问题通常又叫区间调度问题
通常是指：
有非常的内容（例子：节目），完成这些内需要一定的时间，起始时间和结束时间给出，问如何合理安排才能尽可能安排最多的内容，或者问是否能够全部不冲突
该类问题关键在于选择策略：
我们该关注的是哪个时间：
A起始时间 B结束时间 C总共用时
很显然，我们最应该关注的是B，只有这样我们才能保证最大可能容纳更多的内容
如上图，我们关注结束时间，找最早结束时间，然后不断找在上一次结束时间之后的起始时间找最早结束时间，直到结束
以上是关于贪心算法思想的前一部分，我们之后会出关于后序内容，感谢大家的支持！！！
