贪心算法详解

---

前言

在本次文章中我们将会详细介绍贪心算法的相关内容

一、什么是贪心算法

贪心算法：在解决问题时，每一步都选择最优解，从而实现整体最优的过程。总是做出在当前看来最好的选择

我们再来细分一下
🏉🏉.把求解问题的过程分为若干步骤。
🏉🏉.每个步骤都选择当前最优的解法
🏉🏉.最终我们希望得到全局最优解（注意希望）

我们来看几个例子进一步理解一下：
🌟 🌟 .找零问题

我们手中有无限张20，10，5，1元纸币。顾客通过购买商品，我们需要给顾客找零钱，问我们可以给顾客的最少的纸币张数？？

比如顾客给了我们50元，购买了6元的商品，我们需要给顾客46元，需要给他的最少张数是多少。这就是我们求解的问题
🎁我们分为若干步骤，就是一张一张的找给顾客
🎁贪心算法的关键就是每一步做出最优的选择
🎁我们需要给他46元，最优就是给他一张20元的，现在还剩下26元，再给他一张20元的
🎁现在还剩下6元，最优的就是给他一张5元的
🎁现在还剩下1元，最优的就是给他一张1元的
🎁最终我们求得最少需要4张纸币就可以完成找零
🌟 🌟 .最小路径和

有一个二维数组，每个数组都有一个整数，现在我们从数组左上角移动到数组右下角，我们只能向右或者向下走，问我们经过的路径上所有整数加起来最小的路径和

假设二维数组arr如图所示

🎁我们分为若干步，就是一步步的走
🎁贪心算法的关键就是每一步做出最优的选择
🎁我们首先位于arr[0][0]位置,右边值为2，下边值为1，下边的值比较小，最优解应该往下走，到达arr[0][1]位置。
🎁我们现在位于arr[0][1]位置,右边值为1，下边值为7，右边值小于下边值，最优解应该往右走，到达arr[1][1]位置。
🎁同理，我们最终到达arr[2][2]位置
此时贪心策略的路径如图所示

二、贪心算法的特点

1.贪心策略的提出

贪心策略是没有标准和模板的，每一道题的策略都不同

2.贪心策略的正确性

我们发现在最小路径和这个问题上我们通过贪心策略求得的结果并不是正确的答案，正确的如下所示

贪心策略可能是有错误的，正确的贪心算法是需要相关的证明的

证明的方法就是用我们数学中所学到的所有证明方法

三、学习贪心算法的方向

我们仅仅需要关注贪心正确的策略就可以

对于初学者来说，遇到不会的题目是很正常的，我们要把心态放平，重点放在贪心策略上，当成经验吸收。

相关的证明方法可以了解也可以不了解。

总结

以上就是今天要讲的内容，本文仅仅详细介绍了贪心算法，希望对大家的学习有所帮助，仅供参考 如有错误请大佬指点我会尽快去改正 欢迎大家来评论~~ 😘 😘 😘 😘