数据结构与算法 / 系统课时

贪心算法的基本思想

贪心算法的基本思想

贪心算法通过一系列不可撤销的局部选择构造答案。本课用“分发饼干”建立判断与证明框架:先明确局部标准,再验证它能安全地出现在某个全局最优解中,最后用排序和双指针完成实现。

学习目标

  • 说明贪心选择、最优子结构与不可回退的含义
  • 使用交换论证判断局部最优是否能导向全局最优
  • 实现并分析排序加双指针的分发饼干算法

从局部选择到全局答案

给定若干儿童的最低尺寸需求和若干饼干尺寸,一块饼干只能分给一个儿童,目标是满足尽可能多的儿童。直接枚举全部分配方案代价很高,而贪心策略是先按需求和尺寸升序排列,再优先满足当前需求最小的儿童。

局部规则是:使用“当前最小但足够大”的饼干。若最小饼干仍小于当前需求,它也不可能满足后续需求更大的儿童,因此可以直接丢弃;若能够满足,则同时消耗这名儿童和这块饼干。

分发饼干的贪心选择流程

为什么这个选择是安全的

贪心算法成立的关键不是“看起来合理”,而是贪心选择性质:至少存在一个全局最优解包含当前选择。假设某个最优方案给当前需求最小的儿童分配了更大的饼干,而较小的可用饼干也能满足他,那么交换两块饼干不会减少满足人数,也不会让其他儿童获得更差的可用资源。

完成这次安全交换后,剩余儿童与剩余饼干仍构成同类型问题,目标仍是最大化满足人数,这就是最优子结构。证明时可按“取一个最优解、交换首个不同选择、保持目标值不变、递归处理剩余部分”的顺序展开。

主示例:排序与双指针

下面的 Java 17 程序会复制输入数组,避免排序修改调用方数据。childIndex 既指向当前待满足儿童,也等于已经满足的儿童数量。

java
import java.util.Arrays;

public class GreedyBasicsDemo {

    public static void main(String[] args) {
        int[] childNeeds = {1, 2, 3};
        int[] cookieSizes = {1, 1, 2, 3};

        int satisfied = findContentChildren(childNeeds, cookieSizes);
        System.out.println("最多满足儿童数量: " + satisfied);
    }

    private static int findContentChildren(int[] childNeeds, int[] cookieSizes) {
        int[] needs = Arrays.copyOf(childNeeds, childNeeds.length);
        int[] cookies = Arrays.copyOf(cookieSizes, cookieSizes.length);
        Arrays.sort(needs);
        Arrays.sort(cookies);

        int childIndex = 0;
        int cookieIndex = 0;

        while (childIndex < needs.length && cookieIndex < cookies.length) {
            if (cookies[cookieIndex] >= needs[childIndex]) {
                childIndex++;
            }
            // 无论是否满足当前儿童,这块饼干都已完成判断。
            cookieIndex++;
        }

        return childIndex;
    }
}

预期输出:

text
最多满足儿童数量: 3

需求为 1、2、3 的儿童分别获得尺寸为 1、2、3 的饼干,额外的尺寸 1 饼干被丢弃,不影响最优结果。

边界、反例与复杂度

空数组会自然返回 0。排序后扫描每个元素至多一次,时间复杂度为 O(n log n + m log m),扫描复杂度为 O(n + m);额外空间来自复制数组和排序实现。

常见错误是把最大饼干先给最小需求儿童。例如需求 [1, 2]、饼干 [1, 2],若先把 2 分给需求 1 的儿童,只能满足一人。另一个错误是在饼干不足时移动儿童指针;正确做法是丢弃当前饼干,因为它对需求更大的儿童同样无用。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

贪心算法的基本思想

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通