分发饼干问题（非常详细，附带源码）
前面章节介绍了什么是贪心算法，本节趁热打铁，带大家用贪心的思想解决一个实际问题，叫做分发饼干问题。
下面是分发饼干问题的官方描述：
假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。
对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j]。如果 s[j]>=g[i]，我们可以将这个饼干j分配给孩子 i，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。
简单理解分发饼干问题，就是将 n 块尺寸不等的饼干分给 m 个不同胃口的孩子，每个孩子最多只能分一块，要求满足尽可能多的孩子。
例如，三个孩子的胃口分别是 g=[1, 2, 3]，两块饼干的尺寸分别是 s=[1, 1]。这种情况下，只能满足胃口是 1 的孩子，所以满足孩子的最大数量是 1。
再例如，两个孩子的胃口分别是 g=[1, 2]，三块饼干的尺寸分别是 s=[1, 2, 3]。这种情况下，有很多种分法可以让两个孩子都得到满足，比如把尺寸是 3 的饼干分给胃口为 2 的孩子，把尺寸是 2 的饼干分给胃口为 1 的孩子，所以满足孩子的最大数量是 2。
接下来给大家讲解，如何用贪心的思想解决这个问题。
贪心算法解决分发饼干问题
我们知道，贪心算法注重的是每次都选择当下最优的解决方案，又叫局部最优解。贪心算法解决分发饼干问题的整体思路是：大饼干优先分给胃口大的孩子，小饼干优先分给胃口小的孩子。
具体来讲，先按照胃口大小给孩子排序，可以是升序排列（胃口由小到大），也可以是降序排列（胃口由大到小）。采用同样的排序规则，按照尺寸大小给饼干排序。
如果是升序排列，则从胃口最小的孩子开始，先尝试把尺寸最小的饼干分给他，如果无法满足，再试着分他稍大一些的饼干，还不能满足的话再尝试尺寸更大的。当前的孩子被满足后，再以同样的方式继续为后续的孩子分饼干，直到无法再分为止（可能是所有的饼干都尝试分完了，也可能是所有的孩子都满足了。）。该实现过程对应的伪代码如下：
findContentChildren(g, s):
// 先对胃口值和饼干尺寸进行升序排序
g.sort()
s.sort()
count <- 0
j <- 0
// 遍历饼干列表和孩子列表
while count < length(g) and j < length(s):
// 如果当前饼干能满足当前孩子的胃口值，count就加1，否则就继续查找更大的饼干
if g[count] <= s[j]:
count <- count + 1
j <- j + 1
return count
如果是降序排列，则从尺寸最大的饼干开始发放，先试着发给胃口最大的孩子，如果无法满足，就试着发给胃口稍小一些的孩子，还不满足的话再尝试胃口更小的。如果有孩子被满足，就以同样的方式继续发放后续的饼干，直到无法再发放为止（可能是所有的孩子都尝试分完了，也可能是所有的饼干都分完了。）。该实现过程对应的伪代码如下：
findContentChildren(g, s):
// 先对胃口值和饼干尺寸进行降序排序
g.sort()
s.sort()
count <- 0
i <- 0
// 遍历饼干列表和孩子列表
while i < length(g) and count < length(s):
// 如果当前饼干能满足当前孩子的胃口值，count就加1，否则就换一个胃口稍小一些的孩子
if g[i] <= s[count]:
count <- count + 1
i <- i + 1
return count
贪心算法实现分发饼干问题
用贪心的思想解决分发饼干问题，具体的实现思路有两种，就是前面给出的两段伪代码。接下来结合第一段伪代码，分别给出解决分发饼干问题的 C 语言、Java 和 Python 完整程序。读者可以自行结合第二段伪代码尝试写出可运行的程序。
下面是用贪心算法实现分发饼干问题的 C 语言程序：
#include
#include
// 用于qsort的比较函数
int compare(const void* a, const void* b) {
return (*(int*)a - *(int*)b);
}
int findContentChildren(int g[], int gLength, int s[], int sLength) {
// 先对胃口值和饼干尺寸进行升序排序
qsort(g, gLength, sizeof(int), compare);
qsort(s, sLength, sizeof(int), compare);
int count = 0;
int j = 0;
// 遍历饼干列表和孩子列表
while (count < gLength && j < sLength) {
// 如果当前饼干能满足当前孩子的胃口值，count就加1，否则就继续查找更大的饼干
if (g[count] <= s[j]) {
count++;
}
j++;
}
return count;
}
int main() {
int g[] = { 1, 2, 3 };
int s[] = { 1, 1 };
int gLength = sizeof(g) / sizeof(g[0]);
int sLength = sizeof(s) / sizeof(s[0]);
int result = findContentChildren(g, gLength, s, sLength);
printf("可以满足的孩子数量：%d\n", result);
return 0;
}
下面是用贪心算法实现分发饼干问题的 Java 程序：
import java.util.Arrays;
public class ContentChildren {
public static void main(String[] args) {
int[] g = {1, 2, 3};
int[] s = {1, 1};
int result = findContentChildren(g, s);
System.out.println("可以满足的孩子数量：" + result);
}
public static int findContentChildren(int[] g, int[] s) {
// 先对胃口值和饼干尺寸进行升序排序
Arrays.sort(g);
Arrays.sort(s);
int count = 0;
int j = 0;
// 遍历饼干列表和孩子列表
while (count < g.length && j < s.length) {
// 如果当前饼干能满足当前孩子的胃口值，count就加1，否则就继续查找更大的饼干
if (g[count] <= s[j]) {
count = count + 1;
}
j = j + 1;
}
return count;
}
}
下面是用贪心算法实现分发饼干问题的 Python 程序：
def find_content_children(g, s):
# 先对胃口值和饼干尺寸进行升序排序
g.sort()
s.sort()
count = 0
j = 0
# 遍历饼干列表和孩子列表
while count < len(g) and j < len(s):
# 如果当前饼干能满足当前孩子的胃口值，count就加1，否则就继续查找更大的饼干
if g[count] <= s[j]:
count = count + 1
j = j + 1
return count
# 示例用法
g = [1, 2, 3]
s = [1, 1]
result = find_content_children(g, s)
print("可以满足的孩子数量：", result)
运行程序，输出结果为：
可以满足的孩子数量： 1