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

贪心选择思想

贪心选择思想

本课解决“为什么某个局部最优选择可以直接保留”的问题。你将从任务装载示例理解贪心算法只向前推进、不回溯的执行方式,并学会判断一条规则是可证明的贪心策略,还是仅凭经验有效的启发式。

学习目标

  • 解释贪心算法如何通过连续的局部选择构造完整解。
  • 使用贪心选择性质和最优子结构判断策略是否可靠。
  • 区分可证明的贪心策略与只在部分输入上有效的启发式规则。

贪心选择的本质

贪心算法在每一步都从当前可行候选中选择一个最符合规则的对象,然后把问题缩小为剩余子问题。已经作出的选择不会被撤销,因此算法通常只需排序和一次扫描,执行路径清晰、状态数量少。

考虑“在总耗时不超过 10 的前提下完成尽可能多的同价值任务”。任务耗时为 6、2、4、1、3 时,优先选择耗时最短的任务,可以依次装入 1、2、3、4,恰好完成 4 个任务。每次选择后只更新剩余预算,不重新组合此前任务。

贪心选择与剩余子问题流程

正确性与启发式的边界

局部规则看起来合理,并不代表它一定得到全局最优解。一个可靠的贪心算法通常需要同时满足两个条件:存在某个最优解包含当前贪心选择;作出该选择后,剩余部分仍是同类型的最优子问题。

判断维度 可证明的贪心策略 简单启发式
选择依据 与目标函数直接对应 来自经验或直觉
正确性 能用交换论证、归纳等方法证明 只能通过样例观察效果
失败处理 在定义域内保证最优 可能在特殊输入上失效
是否回溯 通常不回溯 也可能不回溯,但不保证最优

在任务数量最大化问题中,设某个最优方案选择的第一个任务耗时为 x,全局最短任务耗时为 g,则必有 g <= x。用 g 替换 x 不会增加总耗时,也不会减少可选任务数量,因此至少存在一个最优方案包含 g。这就是交换论证的核心。

排序需要 O(n log n) 时间,随后扫描需要 O(n) 时间。若输入已经按耗时升序排列,扫描本身只需要 O(n)。

完整可运行示例

下面的程序分别执行“最短优先”和“最长优先”。前者与“最大化任务数量”的目标一致并可证明最优;后者只是一个看似积极但效果较差的启发式。

将代码保存为 GreedyChoiceDemo.java。

java
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class GreedyChoiceDemo {

    record Task(String name, int duration) {
        @Override
        public String toString() {
            return name + "(" + duration + ")";
        }
    }

    static List<Task> selectTasks(List<Task> tasks, int budget, boolean shortestFirst) {
        List<Task> sorted = new ArrayList<>(tasks);
        Comparator<Task> comparator = Comparator.comparingInt(Task::duration);
        sorted.sort(shortestFirst ? comparator : comparator.reversed());

        List<Task> selected = new ArrayList<>();
        int used = 0;

        // 接受当前顺序下仍能放入预算的任务,不撤销此前选择。
        for (Task task : sorted) {
            if (used + task.duration() <= budget) {
                selected.add(task);
                used += task.duration();
            }
        }
        return selected;
    }

    static int totalDuration(List<Task> tasks) {
        return tasks.stream().mapToInt(Task::duration).sum();
    }

    public static void main(String[] args) {
        List<Task> tasks = List.of(
                new Task("T1", 6),
                new Task("T2", 2),
                new Task("T3", 4),
                new Task("T4", 1),
                new Task("T5", 3)
        );
        int budget = 10;

        List<Task> shortestFirst = selectTasks(tasks, budget, true);
        List<Task> longestFirst = selectTasks(tasks, budget, false);

        System.out.println("按耗时升序选择: " + shortestFirst);
        System.out.println("已选数量: " + shortestFirst.size());
        System.out.println("总耗时: " + totalDuration(shortestFirst));
        System.out.println("按耗时降序选择: " + longestFirst);
        System.out.println("已选数量: " + longestFirst.size());
    }
}

编译并运行:

bash
javac GreedyChoiceDemo.java
java GreedyChoiceDemo

预期输出

text
按耗时升序选择: [T4(1), T2(2), T5(3), T3(4)]
已选数量: 4
总耗时: 10
按耗时降序选择: [T1(6), T3(4)]
已选数量: 2

常见错误

1. 把“局部最好”直接等同于“全局最优”

例如硬币面额为 1、3、4,金额为 6 时,优先取最大面额会得到 4 + 1 + 1,但最优解是 3 + 3。修复方法不是给规则增加更多特例,而是重新证明贪心选择性质,证明失败时应考虑动态规划等方法。

2. 选择后又尝试撤销

一旦算法需要枚举此前选择并频繁回滚,它就不再是典型贪心过程。应先明确局部规则是否足以保证安全选择,再决定是否需要搜索、回溯或动态规划。

3. 只计算扫描复杂度

“每个元素只访问一次”并不代表总复杂度一定是 O(n)。当贪心顺序依赖排序时,总时间通常由排序阶段决定,即 O(n log n)。

本课练习

  1. 给定任务耗时 8、1、5、2、3、4 和预算 11,手工执行最短优先策略,记录每一步的剩余预算。验收条件是给出最终任务数量、总耗时和选择顺序。
  2. 构造一个“优先选择耗时最接近剩余预算”的启发式规则,并给出至少一组使其少选任务的反例。验收条件是同时展示启发式结果和真正的最优结果。

本课总结

  • 贪心算法通过不可撤销的局部选择持续缩小问题,通常具有排序加扫描的结构。
  • 一条规则只有在贪心选择性质和最优子结构得到证明后,才能称为可靠的贪心策略。
  • 启发式也可以很快,但它只描述“怎么选”,不自动提供最优性保证。

下一课预告

下一课将学习“活动选择问题”,把本课的判断框架应用到时间区间上,并证明“每次选择最早结束的兼容活动”为什么能够得到最多活动。

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

目录与阅读设置

阅读设置

17

记录一个想法

贪心选择思想

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

登录哪都通