【贪心算法】贪心算法

点赞👍👍收藏🌟🌟关注💖💖
你的支持是对我最大的鼓励，我们一起努力吧!😃😃

1.什么是贪心算法

与其说是贪心算法，不如说是贪心策略。

贪心策略：解决问题的策略( 局部最优 —> 全局最优)。

1. 把解决问题的过程分为若干步；
2. 解决每一步的时候，都选择当前看起来 “最优的” 解法；
3. “希望” 得到全局最优解。

接下来我们举三个例子重点突然我们的贪心策略。

例一：找零问题

假设顾客拿着50块钱去买一瓶4块钱的饮料，你需要找顾客46块钱。此时你只有面额20元、10元、5元、1元 若干个纸币。我们要的是用最少的张数完成找零。

我给你找46块钱肯定是一张一张给你凑成46块钱。解决问题的时候整个问题就分为若干步，若干步就是一张一张的给你找。然后解决每一步的时候都选择当前看起来 “最优的” 解法。

当开始凑46块钱的时候，刚开始肯定不会拿最小的1块钱，我想的是最少的张数，那应该是最快的凑够46块钱。所以第一次肯定选择20块。接下来在凑26块钱，然后凑26块钱，我依旧选择当前看起来最优的还是20块钱。接下来凑6块钱，20和10就不要考虑了，然后选5块钱，接下来在选1块钱，最后正好可以凑够46块钱。

回顾找零过程非常符合贪心策略，每次找钱都选择当前能选择的最大面额，选择u最大面额就能用最少的张数凑成46块钱。

例二：最小路径和

我们在动态规划遇到这道题。我想从左上角到达右下角，然后每次走只能向下走或者向右走。每个格子都是路径，问从左上角达到右下角最小路径和是多少？

这里已经把问题拆分若干个了，从起点一步一步走就是。每一步走的时候都选择当前看起来 “最优的” 解法。从左上角开始走最终走到右下角贪心路径和是10 。

但是可能会有个异或，这个10好像不对，我们直接观察最小的路径和是7。现在先不管正确解法是什么，我们先搞懂什么是贪心策略。

例三：背包问题

物品编号从1~3，每个物品都有体积和价值。此时你手里还有一个最大容量为8的背包。每个物品都有无穷多个。然后问从这些物品种挑选一些物品放背包里，你所挑选东西的最大价值是多少？

这道题限制条件有点多，所以此时我们可能会有非常多的贪心策略。

比如只考虑体积这个限制条件，往背包装的话，肯定会选择体积最小的往背包里装，因为装的多价值可能更大。那只考虑体积的贪心策略的最大价值是8

还有只考虑价值，不是让价值最大吗，那就疯狂装价值最大的，但是因为背包容量的限制，只能装一个价值为10的1号物品。然后去装价值为7的2号物品，但是背包装不下，所以接下来考虑价值为1的3号物品。在这种贪心策略下的最大价值是13

甚至还可以考虑单位体积价值，因为2最大但是因为容量的限制只能装一个1号物品，然后考虑1.75但是装不下，然后就考虑3号物品，你会发现这个策略和只考虑价值的策略是一样的。

虽然上面想了三种贪心策略，但是细心发现这三种策略都错，因为如果最大容量是8的话，那装两个2号物品的最大价值是14，比上面的都大。

虽然最后两个例子贪心并没有解决问题，但是希望已经搞懂什么是贪心策略，就是 贪婪 + 鼠目寸光！说白了只考虑眼前的最优解并不考虑全局的最优解，然后通过眼前的最优解，“希望” 得到全局最优解。但是你会发现鼠目寸光并不一定能得到最后的结果。但是例子又是正确的，为什么正确？待会我们证明一下。

2.贪心算法的特点

1.贪心策略的提出

1. 贪心策略的提出是没有标准以及模板的
2. 可能每一道题的贪心策略都是不同的

2.贪心策略的正确性

因为有可能 “贪心策略” 是一个错误的方法，正确的贪心策略，我们是需要 “证明的”。

想证明一个贪心策略是错的还是挺简单的，举一个反例就行了。就比如例二 更短的路径和是7，例三 选择两个2号物品价值是最大的。这样就把之前的贪心策略全部都给推翻了。所以想说一个贪心策略是错的还是挺简单的。但是例一 找零问题每次都去选可选的面额最大的就能用最少的张数凑成46块钱，如何证明它是对的呢？

不能说凭感觉，此时看这样一个例子，比如还是凑46，但是现在你的面额是 [20、18、10、5、1]，如果依旧按照贪心策略，你会选择两张20元的、一张5元的、一张1元的。但是由于此时有18块钱，我可以选两张18元的，再选一个10元的，才三张就能凑46元。然后你刚刚的贪心就不对了。所以不能说凭感觉，一定要有严格的证明。

常用的证明方法：数学中见过的所有证明方法。

证明：找零问题
[20、10、5、1]

我们先不管策略以及最优解是什么，我们先证明一个性质

假设最优解用了20块钱A张、10块钱B张、5块钱C张、1块钱D张，此时我们先证明一个性质B、C、D是有取值范围的。

先考虑B，B的取值范围有三种：B > 2， B = 2，B < 2
为什么考虑2，因为2张10可以凑成一张20。所以就把B分为>2，=2，<2，三种情况考虑。

我们很好证明前两种情况不是B的最优解，如果想用10，B用的数目超过2张，那么任意两种10都可以用一张20替换，那用20来代替10绝对是比刚刚用两种10块更优的。所以B绝对不可能超过2。

同理B=2也是不可能存在的，原因和上面一样，如果B用了两种10块的，那直接用一张20的替换不是更优的。

由此可以得到一个性质，在最优解中，B的张数绝对是小于2的或者可以说的小于等于1。在最优解中B最多就是一张，要么没有。

同理C是和B一样的，要么C > 2、C = 2、C < 2，最终在最优解中，C的数目最多1张，要么没有。

同理D，因为5张D才可以凑出来一张C，D还是分三种情况：D > 5、D = 5、D < 5,
同理前面两种是不存在的，D超过5张不如用一张C，D等于5张也是不如用一张C，所以D < 5 或者 D 小于等于 4

这是我们证明之前得到的性质，10块钱不超过1张，5块钱不超过1张，1块钱不超过4张。

接下来我们证明方法就是等效法。
设贪心策略最后用的张数是 [a、b、c、d]，最优解 [A、B、C、D]。
接下来我们只要证明出来 a = A，b = B，c = C，d = D。那我们就可以说我们贪心就是最优解。

先证明第一个a，回忆一下我们的贪心[a、b、c、d]怎么来的，我们的贪心策略是能用a就用a，直到a不能用了，在用b。所以用这个贪心策略可以得到 a >= A，绝对不可能是 a < A，如果小了就不是贪心策略，因为我们贪心策略就是能用20就尽量用20，所以a >= A。

然后我们还可以证明 a 不可能大于 A，如果 a > A，说明A比较小，别忘了整个钱数是不变的，如果A比较小，那么少的20块钱就会让B、C、D去凑，你会发现根本凑不出来，注意刚才的性质10块钱不超过1张，5块钱不超过1张，1块钱不超过4张，所能凑出来最大的钱是10 + 5 + 4 = 19，根本凑不出20。如果 a 不能大于 A。

因此得到一个结论： a = A

当 a = A，那 b c d 和 B C D 所凑的钱是一样的。 当凑的钱是一样的时候， 我们可以得到 b >= B，因为贪心我们会尽可能的选择10块钱，此时 b >= B ，同理我们也可以证明 b 不可能大于 B，原因和之前的一样，如果B小的话，它会让C和D凑10块钱，但是C和D凑不出来10块钱，C最多一张5块钱，D最多四张1块钱，5 + 4 = 9 最多凑9块钱，根本凑不出10块钱，所以 b 不可能大于 B。

因此 b = B

同理 c = C ，那 d 自然等于 D。

我们严格证明出来贪心策略和最优解是一致的，因此贪心策略得到的结果绝对是最优解。

3.学习贪心的方向

遇到不会的贪心题，很正常，把心态放平。

1. 前期学习的时候，把重点放在贪心的策略上，把这个策略当成经验吸收。往后遇到相同类型的题目时可以用经验去解决这道问题。

2. 当知道贪心是正确的时候，要想到如何去证明。