贪心算法总结
目录
贪心算法简介
贪心算法，思路也是非常简单的，每一步总是做出在当前看来最好的选择。
也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。
基本思路就是从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。
贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。 贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。
存在的问题
贪心法存在的问题：
1. 不能保证求得的最后解是最佳的；
2. 不能用来求最大或最小解问题；
3. 只能求满足某些约束条件的可行解的范围
基本思路
1.建立数学模型来描述问题；
2.把求解的问题分成若干个子问题；
3.对每一子问题求解，得到子问题的局部最优解；
4.把子问题的解局部最优解合成原来解问题的一个解。
算法实现
1.从问题的某个初始解出发。
2.采用循环语句，当可以向求解目标前进一步时，就根据局部最优策略，得到一个部分解，缩小问题的范围或规模。
3.将所有部分解综合起来，得到问题的最终解。
算法框架
从问题的某一初始解出发；
while （能朝给定总目标前进一步）
{
利用可行的决策，求出可行解的一个解元素；
}
由所有解元素组合成问题的一个可行解；
贪心算法适用的问题
贪心策略适用的前提是：局部最优策略能导致产生全局最优解。
实际上，贪心算法适用的情况很少。一般，对一个问题分析是否适用于贪心算法，可以先选择该问题下的几个实际数据进行分析，就可做出判断。
因为用贪心算法只能通过解局部最优解的策略来达到全局最优解，因此，一定要注意判断问题是否适合采用贪心算法策略，找到的解是否一定是问题的最优解。
贪心算法并不是完全不可以使用，贪心策略一旦经过证明成立后，它就是一种高效的算法。
利用贪心算法解题，需要解决两个问题：
一是问题是否适合用贪心法求解。我们看一个找币的例子，如果一个货币系统有三种币值，面值分别为一角、五分和一分，求最小找币数时，可以用贪心法求解；如果将这三种币值改为一角一分、五分和一分，就不能使用贪心法求解。用贪心法解题很方便，但它的适用范围很小，判断一个问题是否适合用贪心法求解，目前还没有一个通用的方法，在信息学竞赛中，需要凭个人的经验来判断。
二是确定了可以用贪心算法之后，如何选择一个贪心标准，才能保证得到问题的最优解。在选择贪心标准时，我们要对所选的贪心标准进行验证才能使用，不要被表面上看似正确的贪心标准所迷惑（可以看题目：最大整数）
贪心算法所作的选择可以依赖于以往所作过的选择，但决不依赖于将来的选择，也不依赖于子问题的解，因此贪心算法与其他算法相比具有一定的速度优势。如果一个问题可以同时用几种方法解决，贪心算法应该是最好的选择之一。
贪心算法所作的选择可以依赖于以往所作过的选择，但决不依赖于将来的选择，也不依赖于子问题的解，因此贪心算法与其他算法相比具有一定的速度优势。如果一个问题可以同时用几种方法解决，贪心算法应该是最好的选择之一。
贪心算法的经典例题
最小生成树
求最小生成树的Prim算法和Kruskal算法都是漂亮的贪心算法。
https://blog.csdn.net/xushiyu1996818/article/details/90475757
错误样例：背包算法
有一个背包，背包容量是M=150。有7个物品，物品可以分割成任意大小。
要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。
物品 A B C D E F G
重量 35 30 60 50 40 10 25
价值 10 40 30 50 35 40 30
记得当时学算法的时候，就是这个例子，可以说很经典。
分析：
目标函数： ∑pi最大
约束条件是装入的物品总重量不超过背包容量，即∑wi<=M( M=150)
（1）根据贪心的策略，每次挑选价值最大的物品装入背包，得到的结果是否最优？
（2）每次挑选所占重量最小的物品装入是否能得到最优解？
（3）每次选取单位重量价值最大的物品，成为解本题的策略?
贪心算法是很常见的算法之一，这是由于它简单易行，构造贪心策略简单。但是，它需要证明后才能真正运用到题目的算法中。一般来说，贪心算法的证明围绕着整个问题的最优解一定由在贪心策略中存在的子问题的最优解得来的。
对于本例题中的3种贪心策略，都无法成立，即无法被证明，解释如下：
（1）贪心策略：选取价值最大者。反例：
W=30
物品：A B C
重量：28 12 12
价值：30 20 20
根据策略，首先选取物品A，接下来就无法再选取了，可是，选取B、C则更好。
（2）贪心策略：选取重量最小。它的反例与第一种策略的反例差不多。
（3）贪心策略：选取单位重量价值最大的物品。反例：
W=30
物品：A B C
重量：28 20 10
价值：28 20 10
根据策略，三种物品单位重量价值一样，程序无法依据现有策略作出判断，如果选择A，则答案错误。
均分纸牌
有N堆纸牌，编号分别为1，2，…，n。每堆上有若干张,但纸牌总数必为n的倍数.可以在任一堆上取若干张纸牌,然后移动。移牌的规则为：在编号为1上取的纸牌，只能移到编号为2的堆上；在编号为n的堆上取的纸牌，只能移到编号为n-1的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。例如：n=4，4堆纸牌分别为：① 9 ② 8 ③ 17 ④ 6 移动三次可以达到目的：从③取4张牌放到④ 再从③区3张放到②然后从②去1张放到①。
输入输出样例：4
9 8 17 6
屏幕显示：3
算法分析：设a[i]为第I堆纸牌的张数（0<=I<=n），v为均分后每堆纸牌的张数，s为最小移动次数。
我们用贪心算法，按照从左到右的顺序移动纸牌。如第I堆的纸牌数不等于平均值，则移动一次（即s加1），分两种情况移动：
1．若a[i]>v，则将a[i]-v张从第I堆移动到第I+1堆；
2．若a[i]<v，则将v-a[i]张从第I+1堆移动到第I堆。
为了设计的方便，我们把这两种情况统一看作是将a[i]-v从第I堆移动到第I+1堆，移动后有a[i]=v; a[I+1]=a[I+1]+a[i]-v.
在从第I+1堆取出纸牌补充第I堆的过程中可能回出现第I+1堆的纸牌小于零的情况。
如n=3，三堆指派数为1 2 27 ，这时v=10，为了使第一堆为10，要从第二堆移9张到第一堆，而第二堆只有2张可以移，这是不是意味着刚才使用贪心法是错误的呢？
我们继续按规则分析移牌过程，从第二堆移出9张到第一堆后，第一堆有10张，第二堆剩下-7张，在从第三堆移动17张到第二堆，刚好三堆纸牌都是10，最后结果是对的，我们在移动过程中，只是改变了移动的顺序，而移动次数不便，因此此题使用贪心法可行的。
最大整数
设有n个正整数，将它们连接成一排，组成一个最大的多位整数。
例如：n=3时，3个整数13，312，343，连成的最大整数为34331213。
又如：n=4时，4个整数7，13，4，246，连成的最大整数为7424613。
输入：n
N个数
输出：连成的多位数
算法分析：此题很容易想到使用贪心法，在考试时有很多同学把整数按从大到小的顺序连接起来，测试题目的例子也都符合，但最后测试的结果却不全对。按这种标准，我们很容易找到反例：12，121应该组成12121而非12112，那么是不是相互包含的时候就从小到大呢？也不一定，如12，123就是12312而非12123，这种情况就有很多种了。是不是此题不能用贪心法呢？
其实此题可以用贪心法来求解，只是刚才的标准不对，正确的标准是：先把整数转换成字符串，然后在比较a+b和b+a，如果a+b>=b+a，就把a排在b的前面，反之则把a排在b的后面。（用这种方法对所有数字进行排序，然后从大到小连起来）
分糖果
题目：已知一些孩子和一些糖果，每个孩子有需求因子g，每个糖果有大小s，当某个糖果的大小s>=某个孩子的需求因子g时，代表该糖果可以满足该孩子，求使用这些糖果，最多能满足多少孩子（注意，某个孩子最多只能用1个糖果满足）
思考：
当某个孩子可以被多个糖果满足时，是否需要优先用某个糖果满足这个孩子？
当某个糖果可以满足多个孩子时，是否需要优先满足某个孩子？
贪心规律是什么？
贪心规律：
某个糖果如果不能满足某个孩子，则该糖果也一定不能满足需求因子更大的孩子
某个孩子可以用更小的糖果满足，则没必要用更大糖果满足，因为可以保留更大的糖果满足需求因子更大的孩子
孩子的需求因子更小则其更容易被满足，故优先从需求因子小的孩子尝试，可以得到正确的结果(因为我们追求更多的孩子被满足，所以用一个糖果满足需求因子较小或较大的孩子都是一样的)。
算法设计：
对需求因子数组g和糖果大小数组s进行从小到大的排序
按照从小到大的顺序使用各糖果尝试是否可满足某个孩子，每个糖果只尝试1次，只有尝试成功时，换下一个孩子尝试，直到发现没更多的孩子或者没有更多的糖果，循环结束。
摇摆序列
题目：一个整数序列，如果两个相邻元素的差恰好正负(负正)交替出现，则该序列呗成为摇摆序列，一个小于2个元素的序列直接为摇摆序列，给一个随机序列，求这个序列满足摇摆序列定义的最长子序列的长度。
例如：
序列[1,7,4,9,2,5],相邻元素的差(6,-3,5,-7,3),该序列为摇摆序列
序列[1,4,7,2,5]相差(3,3,-5,3)不是摇摆序列
思考与分析：
[1,17,5,10,13,15,10,5,16,8]，整体不是摇摆序列，但是我们观察该序列的前6位：[1,17,5,10,13,15…];5,10,13,15部分为上升段，其中有三个子序列是摇摆序列：
[1,17,5,10….]
[1,17,5,13,…]
[1,17,5,15…..]
在不清楚原始序列的7为是什么的情况下，只看前6位，摇摆子系列的第四位从10，13，15中选择一个数，我们应该选择那一个？
应该选择使得摇摆子序列长度更长的数，所以应该是15，这样遇到比他小的数的可能性就会大一点，按照这种思路总结出贪心规律
贪心规律：
当序列有一段连续的递增(或递减)时，为形成摇摆子序列，我们只需要保留这段连续的递增(或递减)的首尾元素，这样更有可能使得尾部的后一个元素成为摇摆子序列的下一个元素。
算法设计：
设置最长摇摆子序列长度为max_length，从头到尾扫描原始序列，这个过程中设置三种状态，即起始、上升、下降；不同的状态中，根据当前数字和前一个数字的比较结果进行累加max_length计算或者状态切换
这里一旦状态转换，maxlength++
移除K个数字
题目：已知一个使用字符串表示非负整数num，将num中的k个数字移除，求移除k个数字后，可以获得的最小的可能的新数字(num不会以0开头，num长度小于10002)
例如：输入：num = “1432219”,k=3
在去掉3个数字后得到的很多可能里，如1432，4322，2219，1219。。。。；去掉数字4、3、2、得到的1219最小
思考与分析：
一个长度为n的数字，去掉k个数字，可以有多少种可能？C(k,n)=n!/(n−k)!∗k!C(k,n)=n!/(n−k)!∗k!种可能
所以用枚举法肯定是不可能的。
若去掉某一位数字，为了使得到的新数字最小，需要尽可能让得到的新数字优先最高位最小，其次次位最小，再其次第三位最小。。。。
例如：一个四位数 “1。。。”，一定比任何“9.。。。”小。
一个四位数若最高位确定，如“51。。”一定比任何“59。。”、“57。。”小。
贪心规律：
从高位向地位遍历，如果对应的数字大于下一位数字，则把该位数字去掉，得到的数字最小。
算法设计：
使用栈存储最终结果或删除工作，从高位向低位遍历num，如果遍历的数字大于栈顶元素，则将该数字push入栈，如果小于栈顶元素则进行pop弹栈，直到栈为空或不能再删除数字(k==0)或栈顶小于当前元素为止。最终栈中从栈底到栈顶存储的数字，即为结果。