一、贪心算法理论基础（必看）

（1）贪心算法（greedy algorithm）概念

贪心算法（greedy algorithm），又称贪婪算法，是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择， 从而希望导致结果是最好或最优的算法。比如在旅行推销员问题中，如果旅行员每次都选择最近的城市，那这就是一种贪心算法。    

                                                                                                          ——— 摘自维基百科

注释：可以理解为贪心算法每一步都做出当前最正确的决定（局部最优解），通过堆叠局部最优解得到全局最优解。

一个具象的例子：贪心算法像极了父母为我们设想的一生，从小学起就好好学习，小学上一个重点初中（局部最优解1），再通过重点初中上到重点高中（局部最优解1->2），再通过重点高中上到985或海外名校（局部最优解1->2->3），再通过985或海外名校上到藤校硕博、公司高管或政府高官等走上人生巅峰(全局最优解1->2->3->4）。

（2）贪心算法的基本要素

①贪心选择

贪心选择是指所求问题的全局最优解可以通过不断堆叠局部最优解得到。这是贪心算法可行的基本条件，也是贪心算法与动态规划算法的主要区别。

②最优子结构

当一个问题的最优解包含子问题的最优解时，称此问题具有最优子结构的性质。贪心算法的每一次选择都对结果产生直接的影响，而动态规划不是；贪心算法对每个子问题都做出当前最优的选择，并且不能回退,动态规划则不是，动态规划会根据从前的选择结果对当前进行选择，有回退功能。

贪心算法一般用来解决一维的问题，动态规划一般解决多维问题。

二、贪心算法题目（Python、C++、C、JAVA实现）

（1）初级贪心算法（LeetCode 455.分发饼干为例）

我的个人感觉是，这类问题能自己解决出来，但你不知道自己用了贪心算法或者贪心策略比较明显。

题目：原题链接

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。

对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

示例 1:

输入: g = [1,2,3], s = [1,1]

输出: 1

解释:

你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。

虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。

所以你应该输出1。

示例 2:

输入: g = [1,2], s = [1,2,3]

输出: 2

解释:

你有两个孩子和三块小饼干，2个孩子的胃口值分别是1,2。

你拥有的饼干数量和尺寸都足以让所有孩子满足。

所以你应该输出2.

题目解析：在这里采用贪心策略的思想，让孩子们按胃口大小排成队，胃口小的在前面，饼干按大小也摞好，小的在上面，每次给队头的孩子一个能满足他胃口且尽可能小的饼干（注：这个过程就是求局部最优解的过程），吃到饼干的队头孩子就离开队伍，直到饼干发完或者队伍没人即每个孩子都吃到饼干（注：这是通过局部最优解堆叠求得全局最优解）

Python代码

class Solution:

    def findContentChildren(self, g: List[int], s: List[int]) -> int:

        g.sort()#列表的排序命令，默认从小到大排序。将孩子按胃口大小排成队

        s.sort()#把饼干也从小到大摞起来

        child=0#统计吃到饼干的孩子数

        i=0;j=0;

        while i<len(g) or j<len(s):#设置循环结束条件

            if s[j]>=g[i]:#如果第j个饼干刚好可以满足第i个孩子

                child+=1

                i+=1

                j+=1

            else:#如果不能，换下一个饼干试试能不能满足这个孩子

                j+=1

        print(child)

贪心算法经典应用

• （1）硬币找零问题

• 贪心算法遵循某种既定原则,不断地选取当前条件下最优的选择来构造每一个子步骤,直到获得问题最终的求解。即在求解时,总是做出当前看来最好的选择。也就是说,不从整体最优上加以考虑,他所做出的仅是局部最优解。

• 
  

• 利用贪心算法解题,需要解决以下两个问题。

• 
  

• 是问题是否适合用贪心法求解,即所求解问题是否具有贪心选择性质。所谓贪心选择性质,是指应用同一规则,将原问题变为一个相似的但规模更小的子问题,后面的每一步都是当前看似最佳的选择。这种选择依赖于已做出的选择,但不依赖于未做出的选择。从全局来看,运用贪心策略解决的问题在程序的运行过程中无回溯过程。

• 是问题是否具有局部最优解,从而通过选择一个贪心标准,可以得到问题的最优解。

• 利用贪心算法解题的思路一般为:

• 1>建立对问题精确描述的数学模型,包括定义最优解的模型。

• 2>将问题分成一系列子问题,同时定义子问题的最优解结构。

• 3>应用贪心算法原则可以确定每个子问题的局部最优解,并根据最优解模型,用子问题的局部最优解堆叠出全局最优解。

• 硬币找零问题

• 小明去商店里买棒棒糖，她怎么样才能用最少个数的硬币买到心仪的糖果呢？

• 
  

• 问题描述

• 现在市面上有6中不同面值的硬币，各硬币的面值分别为5分、1角、2角、5角、1元、2元。假定商店里各面值的硬币数量无限，小明想买一只标价为0.55元的棒棒糖。

• 
  

• 解题：

• 展示一种情况：用面值为2角、1角和5分的共四枚硬币来付款。

• 
  

• 另一种情况：小明用1元硬币支付，商店用2角和5分的硬币找零，同样需要4枚硬币。付1元，找：0.2+0.2+0.05.

• 
  

• 最佳情况：小明用1元和5分的硬币支付，商店用5角的硬币找零，整个过程只需要三枚硬币。

• 
  

• 现在问题来了,对于给定的各种面值的硬币个数和付款金额,如何计算使用硬币个数最少的交易方案。

• 
  

• 该问题是对上述场景的简化,即仅考虑商店方,确定了找等金额之后,要用最少的硬币个数进行找零，可以抽象成如下模型：

• 
  

• 寻找找零所用最少的硬币数量,使所有硬币面值之和为待找零金额。

• 在求解上述问题时,每次选择当前阶段的支付价值时,总是优先地(贪心地)选择小于待支付金额的最大面值硬币进行支付。举例来说,假如现在有面值2元、1元、5角的硬币,要找等6.5元,则优先选择2元的硬币3枚支付6元,剩下的0.5元可以选择5角的硬币进行支付,共需要3枚硬币。

• 
  

• 在这里,为了满足我们要用最少的硬币数量支付指定额度的金额这一要求,每次使用可选的最大金额付款符合一贯“贪心”的习惯。根据常识,在当前阶段,使用可用的最大面值金额支付剩余待找零额度,可以使后面的待找零额度尽量小,从而更有可能促使之后支付需要的硬币数量尽量少。

• 
  

• 以下我们来做一些验证,确认上述贪心策略满足贪心选择性质,同时具有最优子结构性质。

• 
  

• 贪心选择性质:如果贪心策略做出的选择所获得的结果与其他选择所获得的结果相比,具有更优或同质的性质,说明该贪心策略具有贪心选择性,即我们可以通过确定的贪心策略寻找局部最优解来构造整体最优解。

• 
  

• 我们先通过一个简单的例子来观察:

• ParValue[]={2,1,0,4.0.2}列出了可用的硬币面值,这里,为了使每次选择最大面值的贪心策略可以获得全局最优解,需要规定各面值硬币对应的出现次数最多为{n,1,2,1}。因为面值为1的硬币出现次数为2时,可以用1个面值为2的硬币来代替,硬币使用数就少了,那么就可以获得更优解,所以面值为1的硬币最多出现次数为1。面值为0.4的硬币只能选用2个,若选用了3个,可以用1枚面值为1和一枚面值为0.2的硬币来代替。概括来讲,就是说如果ParValue[1]超过一定数量,可以用更少的ParValue[i-1]来代替,因此,我们优先选择大的面值的话,就会用更少的硬币数,因此满足贪心选择性质。

• 
  

• 从另一方面看,对于组合Parvalue[]={2,1,0.7,0.2}而言,则不满足贪心选择性质,比如要找零的金额是1.4元时,若按照贪心选择策略,得到的支付组合是1元硬币1枚、0.2元硬币2枚共3枚硬币,而通过观察我们知道,存在更优解,即使用0.7元硬币2枚即可完成支付。

• 
  

• 综上,对于可用面值从大到小排列的支付组合ParValue[],只有当ParValue[i]>=2* ParValue[i+1]时,才满足贪心性质,否则,若ParValue[i] < 2ParValue[i+1],对于待找零值在(ParValue[i], ParValue[i+1])时,不满足贪心选择性质。

• 
  

• 这里回归到问题的序列C[],容易看出, C[j]总可以用更大的C[i-1]或者配合一些小币值来代替,但是数量<-C[i]的使用数量,因此满足贪心选择性质。当然在这个过程中要考虑消费者硬币是否足够的问题。

• 
  

• 最优子结构性质:用反证法证明。设Cm为待找零价格为P时的最优解,即最少使用Cm个硬币。当前价格可拆分为用最大面值支付的部分aParValue m与其他部分Pm-1之和,即P=aParValue m+ Pm-i, a为当前最大面值硬币使用数量, ParValue m为当前最大面值硬币面值, Pm-1为其他硬币面值之和,且有Cm=a+Cm-1, Cm-1为满足剩余价格需要支付的硬币数量。若存在Cm-1.’,满足Cm-1.’<Cm-1,即存在更优的解,则有Cm-1’+a<Cm-1 + a=Cm,与Cm为最优解的前提矛盾。由此证明满足最优子结构性质.

• 
  

• 最终代码

• par = [0.05,0.1,0.2,0.5,1.0,2.0] #存储每种硬币，从小到大排列

• sum = float(input("请输入需要找的零钱:")) 

• #从面值最大的开始遍历

• i = len(par) -1

• while i >= 0:

•     if sum >= par[i]:

•         n = int(sum // par[i])

•         change = n * par[i]

•         sum = float("%.6f" %(sum - change))

•         print("用了%d个%1.2f元硬币" % (n,par[i]))

•     i -= 1

• 
  

• 
  

• 
  

• 
  

• 分发饼干

• 摆动序列

• 最大子序列和

• 买卖股票的最佳时机ii

• 跳跃游戏

• 跳跃游戏ii

• K次取反后最大化数组和

• 加油站

• 分发糖果

• 柠檬水找零

• 根据身高重建队列

• 用最少数量的箭引爆气球

• 无重叠区间

• 划分字母区间

• 合并区间

• 单调递增的数字

• 买卖股票的最佳时机含手续费

• 监控二叉树

————————————————

版权声明：本文选摘自CSDN博主「不会变成恶龙的少年」、「Travislgd」、「黎明之道」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。

原文链接1：https://blog.csdn.net/Harry______/article/details/109187476

•  原文链接2：https://blog.csdn.net/sjjsaaaa/article/details/106932401