贪心算法总结

贪心算法的核心思想

贪心算法通过在每一步都做出当前看起来最优的选择，从而希望导致全局最优解。

关键特征：

1. 局部最优选择：每步都选择当前最好的
2. 无后效性：当前选择不依赖未来的选择
3. 不可撤销：一旦做出选择就不再改变

贪心算法的适用条件

1. 贪心选择性质

问题的全局最优解可以通过一系列局部最优选择来达到。

2. 最优子结构

问题的最优解包含其子问题的最优解。

3. 无后效性

前面的选择不会影响后面的选择，每个子问题都是独立的。

贪心算法设计步骤

第一步：理解问题本质

• 明确要求什么（最大值、最小值、最优方案等）
• 分析问题的约束条件

第二步：找到贪心策略

• 关键问题：在每一步，什么选择是"最优"的？
• 常见贪心策略：
  • 选择最大/最小的元素
  • 选择最早/最晚的时间
  • 选择性价比最高的选项
  • 选择剩余容量最大的选择

第三步：证明贪心策略的正确性

• 交换论证法：证明贪心选择可以替换最优解中的选择
• 归纳法：证明每步贪心选择后，剩余问题仍有最优解
• 反证法：假设贪心策略错误，推出矛盾

第四步：实现算法

• 通常需要排序或使用优先队列
• 按照贪心策略逐步构造解

经典贪心问题模式

1. 区间调度问题

问题：选择最多的不重叠区间
贪心策略：每次选择结束时间最早的区间

// 按结束时间排序，贪心选择
Arrays.sort(intervals, (a, b) -> a[1] - b[1]);

2. 活动选择问题

问题：在有限时间内安排最多活动
贪心策略：选择结束时间最早的活动

3. 分数背包问题

问题：背包容量有限，物品可分割，求最大价值
贪心策略：按性价比（价值/重量）排序，优先选择性价比高的

4. 霍夫曼编码

问题：构造最优前缀编码
贪心策略：每次合并频率最小的两个节点

5. 最小生成树（Kruskal/Prim）

贪心策略：每次选择权重最小的边（不形成环）

最长递增子序列中的贪心

问题分析

• 目标：找到最长的严格递增子序列
• 关键洞察：对于相同长度的递增序列，尾部元素越小越好

贪心策略

// 维护tails数组：tails[i] = 长度为i+1的递增序列的最小尾部元素
// 贪心选择：总是保持每个长度对应的最小尾部元素

为什么贪心正确？

• 局部最优：尾部元素小的序列有更大的扩展潜力
• 全局最优：这种选择不会错过任何可能的最优解

贪心算法通用模板

public class GreedyTemplate {
    public ResultType solve(InputType input) {
        // 1. 预处理：通常需要排序
        preprocess(input);
        
        // 2. 初始化结果
        ResultType result = initResult();
        
        // 3. 贪心选择循环
        for (Element element : input) {
            // 4. 判断是否可以选择当前元素
            if (canSelect(element, result)) {
                // 5. 做出贪心选择
                makeGreedyChoice(element, result);
            }
        }
        
        return result;
    }
    
    // 预处理：根据贪心策略排序
    private void preprocess(InputType input) {
        // 常见排序策略：
        // - 按值大小排序
        // - 按时间排序  
        // - 按性价比排序
    }
    
    // 判断选择条件
    private boolean canSelect(Element element, ResultType result) {
        // 检查约束条件
        return true;
    }
    
    // 执行贪心选择
    private void makeGreedyChoice(Element element, ResultType result) {
        // 更新结果
    }
}

识别贪心问题的技巧

1. 关键词识别

• "最多"、"最少"、"最优"
• "尽可能"、"最大化"、"最小化"

2. 问题特征

• 可以分解为子问题
• 局部最优选择很明显
• 不需要考虑所有可能的组合

3. 常见错误

• 贪心策略错误：选择的策略不能导致全局最优
• 忽略约束条件：没有正确处理问题的限制条件
• 缺乏正确性证明：没有验证贪心策略的正确性

贪心 vs 动态规划

练习建议

1. 从经典问题开始：区间调度、活动选择等
2. 理解贪心策略：每个问题的贪心选择是什么
3. 练习证明：学会证明贪心策略的正确性
4. 识别模式：总结不同类型问题的贪心策略
5. 对比思考：什么时候用贪心，什么时候用DP

记住：贪心算法的关键是找到正确的贪心策略，并能证明其正确性！