贪心算法（英语：greedy algorithm），是用计算机来模拟一个「贪心」的人做出决策的过程。这个人十分贪婪，每一步行动总是按某种指标选取最优的操作。而且他目光短浅，总是只看眼前，并不考虑以后可能造成的影响。
可想而知，并不是所有的时候贪心法都能获得最优解，所以一般使用贪心法的时候，都要确保自己能证明其正确性。
解释
适用范围
贪心算法在有最优子结构的问题中尤为有效。最优子结构的意思是问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。
要点
常见题型
在提高组难度以下的题目中，最常见的贪心有两种。
「我们将 XXX 按照某某顺序排序，然后按某种顺序（例如从小到大）选择。」。
「我们每次都取 XXX 中最大/小的东西，并更新 XXX。」（有时「XXX 中最大/小的东西」可以优化，比如用优先队列维护）
二者的区别在于一种是离线的，先处理后选择；一种是在线的，边处理边选择。
排序解法
用排序法常见的情况是输入一个包含几个（一般一到两个）权值的数组，通过排序然后遍历模拟计算的方法求出最优值。
后悔解法
思路是无论当前的选项是否最优都接受，然后进行比较，如果选择之后不是最优了，则反悔，舍弃掉这个选项；否则，正式接受。如此往复。
区别
与动态规划的区别
贪心算法与动态规划的不同在于它对每个子问题的解决方案都做出选择，不能回退。动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能。
一、找零钱问题
有 1 元，5元，10元，20元，100元，200元的钞票无穷多张。现在使用这些钞票支付X元，最少需要多少张钞票。
X = 628
最佳支付方法：
3张200块的，1张20块的，1张5块的，3张1块的
共需3+1+1+3 = 8张
直觉告诉我们:尽可能多的使用面值较大的钞票!
贪心法: 遵循某种规律，不断贪心的选取当前最优策略的算法设计方法。
分析：面额为1元、5元、10元、20元、100元、200元，任意面额是比自己小的面额的倍数关系。 所以当使用一张较大面额钞票时，若用较小面额钞票替换，一定需要更多的其他面额的钞票!
#include<cstdio>
#include<iostream>
using namespace std;
int main(){
const int RMB[]= {200,100,20,10,5,1};
const int NUM = 6;//6种面值
int X = 628;
int count = 0;
for(int i= 0;i< NUM;i++){
int use = X / RMB[i];需要面额为RMB[i]的use张
count + = use；
X = X -RMB[i] * use;
printf("需要面额为%d 的%d张",RMB[i],use);
printf("剩余需要支付金额%d.\n",X);
}
printf("总共需要%d张\n",count);
return 0;
}
为何这么做一定是对的？
面额为 1元，5元，10元，20元，100元，200元，任意面额是比自己小的面额的倍数关系。
所以当使用一张较大面额钞票时，若使用较小面额钞票替换，一定需要更多的其他面额的钞票。
例如：
5=1+1+1+1+1
10=5+5
20=10+10
100=20+20+20+20+20
200=100+100
故：当前最优解即为全局最优解，贪心成立。
例题2：
有1元，5元，6元的纸币，现在用这些钞票支付K元，至少多少张纸币？
经我们分析，这种情况是不适合用贪心算法的，因为我们上面提供的贪心策略不是最优解。比如，要支付10元的话，按照上面的算法，至少需要1张6元的，4张1元的，而实际上最优的应该是2张5元的。
例题3：假设1元、2元、5元、10元、20元、50元、100元的纸币分别有a,b,c,d,e,f,g张。现在要用这些钱来支付m元，至少要用多少张纸币？如果能支付输出最少支付的张数，如果不能支付，输出-1。
#include<iostream>
#include<algorithm>
using namespace std;
const int N=7;
int Count[N]={3,0,2,1,0,3,5}; //每种面值的数量
int Value[N]={1,2,5,10,20,50,100}; //面值
int solve(int money)
{
int num=0;
for(int i=N-1;i>=0;i--)
{
int c=min(money/Value[i],Count[i]);
money=money-c*Value[i];
num+=c;
}
if(money>0) num=-1;
return num;
}
int main()
{
int money;
cin>>money;
int res=solve(money);
if(res!=-1) cout<<res<<endl;
else cout<<"NO"<<endl;
}