分发饼干问题（非常详细，附带源码）

前面章节介绍了什么是贪心算法，本节趁热打铁，带大家用贪心的思想解决一个实际问题，叫做分发饼干问题。

下面是分发饼干问题的官方描述：

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

对每个孩子 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 <stdio.h>
#include <stdlib.h>

// 用于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

分发饼干问题（非常详细，附带源码）

贪心算法解决分发饼干问题

贪心算法实现分发饼干问题

相关文章