数据结构与算法 / 系统课时
贪心算法的基本思想
贪心算法的基本思想
贪心算法通过一系列不可撤销的局部选择构造答案。本课用“分发饼干”建立判断与证明框架:先明确局部标准,再验证它能安全地出现在某个全局最优解中,最后用排序和双指针完成实现。
学习目标
- 说明贪心选择、最优子结构与不可回退的含义
- 使用交换论证判断局部最优是否能导向全局最优
- 实现并分析排序加双指针的分发饼干算法
从局部选择到全局答案
给定若干儿童的最低尺寸需求和若干饼干尺寸,一块饼干只能分给一个儿童,目标是满足尽可能多的儿童。直接枚举全部分配方案代价很高,而贪心策略是先按需求和尺寸升序排列,再优先满足当前需求最小的儿童。
局部规则是:使用“当前最小但足够大”的饼干。若最小饼干仍小于当前需求,它也不可能满足后续需求更大的儿童,因此可以直接丢弃;若能够满足,则同时消耗这名儿童和这块饼干。

为什么这个选择是安全的
贪心算法成立的关键不是“看起来合理”,而是贪心选择性质:至少存在一个全局最优解包含当前选择。假设某个最优方案给当前需求最小的儿童分配了更大的饼干,而较小的可用饼干也能满足他,那么交换两块饼干不会减少满足人数,也不会让其他儿童获得更差的可用资源。
完成这次安全交换后,剩余儿童与剩余饼干仍构成同类型问题,目标仍是最大化满足人数,这就是最优子结构。证明时可按“取一个最优解、交换首个不同选择、保持目标值不变、递归处理剩余部分”的顺序展开。
主示例:排序与双指针
下面的 Java 17 程序会复制输入数组,避免排序修改调用方数据。childIndex 既指向当前待满足儿童,也等于已经满足的儿童数量。
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;
}
}预期输出:
最多满足儿童数量: 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 的儿童,只能满足一人。另一个错误是在饼干不足时移动儿童指针;正确做法是丢弃当前饼干,因为它对需求更大的儿童同样无用。