贪心算法总结
目录
贪心算法简介
存在的问题
基本思路
算法实现
算法框架
贪心算法适用的问题
贪心算法的经典例题
最小生成树
错误样例：背包算法
均分纸牌
最大整数
分糖果
摇摆序列
移除K个数字
贪心算法简介
贪心算法，思路也是非常简单的，每一步总是做出在当前看来最好的选择 。
换句话说，并非从整体最优的角度出发**（即并非从全局最优化的角度出发）** ，贪心算法它所做出的选择只是寻找局部最优解。
基本思路就是从问题的一个初始解出发逐步趋近于给定的目标尽快获得更优的解当达到某算法中的某一步不能再继续前进时算法停止
贪心算法（又称greedy approach）是一种解决优化问题的有效方法，在每一步选择中都采取当前状态下最好或最合理的选择。这种方法并不寻求全局最优解而是通过一系列局部最优选择来实现整体目标。然而，并非所有的优化问题都可以通过贪心算法得到全局最优解因此在应用时需要谨慎选择合适的贪心策略并确保其满足无后效性的要求：即某状态以前的过程不会影响以后的状态仅与当前状态相关。这种特性被称为无后效性。
存在的问题
贪心法存在的问题：
- 无法确保最终获得的是最优解；
- 不适用于解决极值相关的问题；
- 仅能确定满足一定限制条件下的可行解范围
基本思路
1.建立数学模型来描述问题；
2.把求解的问题分成若干个子问题；
3.对每一子问题求解，得到子问题的局部最优解；
4.把子问题的解局部最优解合成原来解问题的一个解。
算法实现
1.从问题的某个初始解出发。
通过循环语句，在每当能够朝着求解目标前进一步时，基于局部最优策略获得这一部分解答，并逐步缩小问题规模。
3.将所有部分解综合起来，得到问题的最终解。
算法框架
从问题的某一初始解出发；
while （能朝给定总目标前进一步）
{
利用可行的决策，求出可行解的一个解元素；
}
由所有解元素组合成问题的一个可行解；
贪心算法适用的问题
贪心策略适用的前提是：局部最优策略能导致产生全局最优解。
事实上, 贪心算法应用的情况较为有限. 通常情况下, 在判断一个问题是否适合使用贪心算法时, 可以通过选取一些具体的实例来验证其有效性.
由于贪心算法仅限于通过解决局部最优问题来获取全局最优结果，在应用时必须特别注意评估问题是否适合应用贪心算法。因此必须特别注意评估问题是否适合应用贪心算法，并确保所得到的解决方案是否一定是该问题的最佳解决方案。
并非完全无法使用贪心算法；当贪心策略被证明成立时，则这种算法就是一种高效的方法。
利用贪心算法解题，需要解决两个问题：
关键在于判断问题是否适合采用贪心算法求解 。让我们以一个找零问题为例来探讨：假设有三种不同面值的货币单位——1角、5分及1分——当计算最小的找零金额时（即找出最少数量硬币/纸币），我们可以应用贪心算法；然而若将这些货币单位重新设定为1角1分、5分及1分，则无法直接使用贪心算法来解决该问题。尽管应用贪心算法通常非常便捷，在信息学竞赛中经常遇到此类情况；但其适用范围却非常有限，在实际应用中并不常见。
二是一旦确定了可以用贪心算法后（例如：最大整数问题），如何制定一个有效的 greedy 准则以确保能够获得该问题的整体最优解？在这一过程中（步骤），我们必须对所制定的 greedy 准则进行验证后才能应用；切勿被表面看似合理的 greedy 准则误导
该算法基于过去的历史信息作出决策，并不受未来因素的影响；此外，在求解过程中无需考虑子问题的解决方案。由此可知，在速度方面该方法具有一定优势。在这种情况下（当多种方法可用），优先考虑 greedy approach 是最合理的策略。
贪心算法作出的选择能够依赖以往所作出的选择,但绝对不依赖未来的选择以及子问题的解,由此可见,贪心算法相较于其他算法具有显著的速度优势。若一个问题允许多种方法并行求解,那么贪心算法无疑将是最佳的方案之一。
贪心算法的经典例题
最小生成树
求最小生成树的Prim算法和Kruskal算法都是漂亮的贪心算法。
<>
错误样例：背包算法
有一个背包，背包容量是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)
根据贪心算法的原则，在选择物品时优先选择那些具有最高价值的物品放入背包中，这样的结果是否为全局最优？
（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至n。每堆纸牌数量任意分布,但总数量必须是n的整数倍.游戏规则规定:从第一个抽屉移出卡片只能放入第二个抽屉;从第n个抽屉移出卡片只能放入第n-1个抽屉;而其他各抽屉取出卡片时则可以选择将卡片放入相邻左边或右边的一个抽屉中进行处理.目标是在最少的操作次数内实现所有抽屉内卡片数量相等.例如:当n=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堆。
在设计过程中，在考虑各种可能性时，在思考如何简化运算步骤时
在该过程中可能会遇到从第I+1堆移取纸牌至第I堆的情况，可能导致第I+1堆纸牌数量减少至负值的结果。
如n=3时的情况而言，在三组分配数目分别为1、2及27的情况下，在v被设定为10时，则若希望第一组能够达到目标值10，则需从第二组转移9个单位至第一组；然而由于第二组仅有剩余两个单位可供转移
按照既定规则对牌局进行分析后发现：将第二层的所有9张转移至第一层后使第一层拥有完整的10张；随后将第三层转移的17张加入到已出现不足的一层中此时三层均达到数量上的均衡状态最终结果正确；在整个操作过程中仅调整了转移的先后次序而转移总次数保持不变因此此题适合采用贪心算法解决
最大整数
设有n个正整数，将它们连接成一排，组成一个最大的多位整数。
例如：n=3时，3个整数13，312，343，连成的最大整数为34331213。
又如：n=4时，4个整数7，13，4，246，连成的最大整数为7424613。
输入：n
N个数
输出：连成的多位数
算法分析：对于这个问题来说，贪心算法是一个常用的解决方法。在考试中有很多学生尝试将整数按照从大到小的顺序连接起来作为解决方案，并且这一方法在测试题目的示例中也得到了验证。然而，在实际应用中这种方法却并不总是有效：例如数字串''和''按照这种方法处理后会得到不同的结果。在这种情况下我们很容易找到反例：如数字串''和''应该组成''而不是''这样就会产生矛盾的结果。其实这并不总是适用的：比如像数字串''和''这样的情况就不满足这种条件。由此可见，并不能一概而论地说这种方法就完全适用。
对于这个问题而言，我们可以采用贪心算法来解决它。然而我之前所采用的标准并不正确。正确的做法是将整数转换为字符串形式，并且需要对这些字符串进行排序以达到最优效果。具体来说，在排序过程中应当遵循以下原则：首先将每个数字统一转换为统一长度的字符串（例如全部转化为两位数字），然后依次比较相邻两个元素的连接结果（即比较ab与ba）。如果ab的结果大于或等于ba的结果，则应将字符a放置在字符b之前；反之，则应将字符a放置在字符b之后。（按照这一排序规则对所有数字进行处理后即可得到最终结果）
分糖果
假设有一定数量的孩子和若干颗糖果需要分配给这些孩子。每颗糖都有固定的体积量s，在这里我们假设每颗糖的体积都是相同的。对于每一个小孩来说都有一个特定的需求量g，在这里我们称其为孩子的"口渴度"。只有当某一颗糖的体积不小于某一孩子的口渴度时，则表示这颗糖能够满足这个小孩的基本需求。我们的目标就是通过合理分配这些糖块，在保证每个小孩至多只能获得一颗满足其需求条件下的情况下，请问：最多能有多少个小孩得到满足？需要注意的是，在这种情况下任何一个小孩也只能被分配到至多一颗符合条件的糖块来满足他们的需求
思考：
当一个孩子能被多种糖果满足时，则需先使用特定的糖果来满足该孩子？
当一种糖果能为多个孩子提供服务时，则需先为特定的孩子分配这颗糖果？
如何体现这一贪心策略？
贪心规律：
对于某个孩子来说, 如果某个糖果无法满足他的需求, 则同样地, 在面对更高需求水平的孩子时, 该糖果也无法满足他们的要求.
某个孩子可以用较小的糖果来满足，则无需使用较大的糖果来满足需求因子较大的孩子。这是因为孩子的需求因子较小意味着其更容易被满足；因此应优先考虑需求因子较小的孩子。算法设计中发现，在这种情况下，并不会影响最终的结果（因为我们的目标是尽可能多地使孩子们得到满足）。
将需求因子数组g与 candies size array s按照升序进行排列
摇摆序列
一个整数序列如果满足两个相邻元素差值的正负交替出现则称其为摆动序列特别地当序列长度少于两个时直接判定为摆动序列给定一个随机生成的整数序列要求找出其最长摆动子序列的长度例如对于序列为1 7 4 9 2 5其相邻元素之差依次为6 -3 5 -7 3满足摆动特征因此该序列为摆动序列而另一组数据如1 4 7 -2 -5其相邻差值分别为3 -5 -3 -2由于存在连续同号差值因此不符合摆动特征
分析与思考
最佳选择使得摇摆子序列长度最长的那个数是15，在这种情况下遇到小于它的数的概率会更高一些。通过这种思路得出了贪心算法的基本规律
贪心规律：
当序列中存在一段连续递增或递减的区间时，在构造一个摆动子序列的过程中，我们应优先考虑保留该区间两端的关键元素。这种策略有助于提高后续元素作为摆动子序列延续点的可能性。
算法设计：
将最长振荡子序列的长度设定为max_length，并依次遍历原始序列。在此过程中划分三种状态类别：初始态、上升态及下降态。在每种状态下依据当前数值与前一数值的关系判断并据此累加当前的最大长度值或转移状态。
这里一旦状态转换，maxlength++
移除K个数字
给定一个由字符串表示的非负整数num，在其中删除其中k个字符（digit）后，请确定在删除这k个字符之后能够获得的最小可能的新数值。（需要注意的是原始数值不会以零开头，并且原始数值的位数不超过10,002位）
输入：num = “1432219”,k=3
在删除k位数字后会生成许多可能性；例如，在删除了 k 位数字后会生成许多可能性。
其中最小的可能性就是移除第四个、第三个和第二个字符所得到的结果。
对于一个长度为n的数字来说，在去掉k个数字的情况下，共有多少种选择方式？根据组合数学原理可知：C(k,n) = n!/(n−k)!×k! 种可能。显然用穷举法无法实现目标。若去掉某一位数字，则为了得到一个新的尽可能小的数字，则需要使得新得到的数字在高位上尽量取较小值，并依次类推后续各位的选择。
例如，在一个四位数中，“1...”的数值必然低于任何“9...”的数值。
当最高位固定为某一数值时，则如“51..”的情况必然低于所有“59..”和“57..”。
贪心规律：
从最高位开始依次检查每一位。若当前位上的数字大于其右边的一位，则将其舍弃。最终得到的结果就是最小的数值。
算法设计：
通过栈实现数据的临时存储与处理，在对数值进行处理时采用从高位依次处理每一位数字的方法。具体操作如下：当遇到比栈顶元素大的数字时，则将该数字压入栈中；若当前数字小于栈顶元素，则连续弹出栈顶元素直至满足以下任一终止条件：一是栈为空；二是已无任何数字需要处理（k=0）；三是当前数字不小于当前栈顶元素。
