作者介绍：10年大厂数据\经营分析经验，现任大厂数据部门负责人。
会一些的技术：数据分析、算法、SQL、大数据相关、python
欢迎加入社区：码上找工作
作者专栏每日更新：
备注说明：方便大家阅读，统一使用python，带必要注释，公众号 数据分析螺丝钉 一起打怪升级
贪心算法是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法策略。贪心算法不像动态规划那样考虑整个问题的最优解结构，而是通过局部最优选择递进到最终的解决方案。这种方法通常更简单、更快速，但需要仔细选择问题场景，因为它并不保证总能得到最优解。
1. 贪心算法的核心思想
贪心算法的核心是构建问题的解决方案的过程中，每一步都选择最优的操作，以便获得最优的解决方案。这些选择在做出时可能看起来是最佳的局部选择，但并不一定能导致全局最优的解决方案。
优点：
- 简单易实现
- 运行效率高
缺点：
- 通常情况下不会得到最优解
- 对于需要求取全局最优解的问题只能在某些情况下使用
2. 贪心算法的适用条件
贪心算法适用于满足以下两种主要特性的问题：
- 贪心选择性质：可以通过作出局部最优的选择来构建全局最优解。
- 最优子结构：一个问题的最优解包含其子问题的最优解。
这意味着局部最优解能递推到全局最优解，即选择最优的当前步骤不会影响之后的步骤。
3. 分发饼干问题
问题描述：假设你是一位很棒的家长，想要给你的孩子们一些饼干，但是只有一定大小的饼干可用。每个孩子最多只能给一块饼干。对每个孩子 i，都有一个胃口值 g[i]，这是能满足该孩子的最小饼干大小；并且每块饼干 j，都有一个大小s[j]。如果 s[j] >=g[i]，我们可以将这个饼干 j 分配给孩子 i，这个孩子会感到满足。你的目标是尽可能满足更多数量的孩子，并输出最大数目。
贪心策略：为了最大化满足孩子的数量，优先考虑胃口最小的孩子，并给他最小的足以满足他的饼干。即使用从小到大排序后的孩子列表和饼干列表，然后进行匹配。
代码实现：
def findContentChildren(g, s): g.sort() s.sort() child_i = cookie_j = 0 while child_i < len(g) and cookie_j < len(s): if s[cookie_j] >= g[child_i]: child_i += 1 cookie_j += 1 return child_i # 示例 g = [1, 2, 3] # 孩子的胃口值 s = [1, 1] # 饼干的尺寸 print("最大满足孩子数:", findContentChildren(g, s)) # 输出: 1
为了提供更清晰的理解，我们将通过图解展示上述 findContentChildren 函数的工作过程，并进行详细的算法分析。这个函数旨在通过分配尽可能小的饼干满足尽可能多的孩子，从而解决分发饼干问题。
函数 findContentChildren 图解步骤
初始状态
- 孩子们的胃口值：
g = [1, 2, 3] - 饼干的尺寸：
s = [1, 1]
第一步：排序
对孩子的胃口和饼干的尺寸进行排序（在这个例子中，孩子的胃口已经有序，饼干同样有序）。
排序后的孩子胃口：g = [1, 2, 3]
排序后的饼干尺寸：s = [1, 1]
第二步：初始化指针
设置两个指针 child_i 和 cookie_j 分别用来遍历孩子和饼干数组。
第三步：分配饼干
遍历饼干数组，尝试分配给每个孩子：
- 比较第一个饼干 (
s[0] = 1) 与第一个孩子 (g[0] = 1):
- 饼干大小等于孩子的胃口，满足条件。
- 孩子被满足，两个指针都向前移动一步。
- 比较第二个饼干 (
s[1] = 1) 与第二个孩子 (g[1] = 2):
- 饼干大小小于孩子的胃口，不满足条件。
- 只移动饼干指针，尝试下一个饼干。
由于没有更多的饼干，而且剩余的孩子 (g[2] = 3) 的胃口都比剩下的饼干大，循环结束。
图解展示
| 孩子/饼干 | 1 | 1 |
| 1 | ✓ | |
| 2 | X | |
| 3 |
✓表示孩子被满足。X表示尝试分配但未能满足孩子。
结束
函数返回 child_i 的值，即 1，表示有一个孩子得到满足。
算法分析
时间复杂度
- O(n log n + m log m): 其中
n是孩子的数量，m是饼干的数量。排序孩子和饼干数组各需要 O(n log n) 和 O(m log m)，遍历饼干数组和尝试满足孩子需要 O(m + n)。通常，排序是占主导的部分。
空间复杂度
- O(1): 除了输入的数组外，只使用了常数额外空间。
优点
- 简单易实现。
- 贪心选择保证了使用最少的资源满足最多的孩子。
缺点
- 贪心算法不一定能得到全局最优解，但在这个问题中它确实能提供最优解。
- 必须先对数组进行排序，这增加了复杂度。
通过以上详细的图解和步骤分析，我们可以清楚地看到如何用贪心算法解决分发饼干问题，并理解其背后的算法逻辑。
4. 总结
贪心算法适用于一些特定问题，它能提供简单快速的解决方案。但贪心算法的最大挑战是正确证明贪心选择的有效性。在实践中，当一个问题可以通过贪心算法解决时，通常需要对问题有深刻的理解和准确的问题建模，以保证贪心策略的正确性和效率。对于那些不能完全通过贪心解决的问题，可能需要考虑其他算法，如动态规划或回溯算法。
欢迎关注微信公众号 数据分析螺丝钉
