蓝桥杯备考：贪心算法简介
贪心算法就是企图用局部最优的策略找出全局最优步骤就是1，把解决问题的过程分成若干步。2，每一步都选择当前看起来最优的解法 。 3，希望得到全局最优的结果
比较经典的例题一个就是
找零问题
钞票种类[20,10,5,1]用最小的张数找零46的时候，先把最大的20的找完，然后找10的，再找5的，最后再找1的直到不能再找，过程就是 46：找零20 ---》 26：找零20 -----》 6 ：找零5 -----》 1 ：找零1 -----》 0
另一个就是最小路径和问题
我们如果用贪心的话，一定是先从下走，因为2是比4小的，然后再从右走，加起来就是1+2+1+10+1=15，但是这个贪心策略一定对吗？不一定，先从右走的话路径和是更小的
有时候啊，局部最优是不等同于全局最优的，所以我们要对贪心策略进行证明
比如我们证明一下找零问题的正确，找零问题有个性质就是 设20的张数为A，10的是B，5的是C，1的是D，B一定≤1，如果大于1的话可以用20来替代，B=2的时候可以换成一张20的，B=3的时候可以换成一张20的和一张10的，C小于等于1，D小于等于4 如果C大于1可以用10来替代，如果D大于5可以用5来替代
好的，设贪心策略的结果是 a b c d 正确是A B C D
一定可以得出a是大于等于A的，因为贪心策略是取到不能再取，如果a大于A的时候，没有用到A的钱数一定是大于20的，然而根据我们正确策略的性质，没有用到A的剩余钱数应该是<=10+5+4=19的，所以a不会大于A，a是等于A的，其他证明同理
贪心策略是很难想到的，我们前期要积极的汲取经验
在平常学习的时候，我们尽可能证明一下贪心策略的正确性，这有利于培养我们严谨的思维，但是我们在比赛的时候，如果很多边界情况能过了，我们就可以写代码了，在赛完再严谨的证明一下