贪心算法的正确性证明

一、贪心算法概述

1.1 核心思想

每一步都做出局部最优选择，期望最终得到全局最优解。

1.2 与动态规划的区别

特性	贪心	动态规划
决策方式	每步唯一选择	保留多个子问题解
回溯	不回溯	可能回溯
复杂度	通常更低	较高
适用范围	满足贪心选择性质	满足最优子结构

1.3 适用条件

1. 贪心选择性质：局部最优能导致全局最优
2. 最优子结构：问题的最优解包含子问题的最优解

二、正确性证明方法

2.1 反证法

假设贪心解不是最优，推出矛盾。

2.2 归纳法

证明前k步贪心选择都包含在某个最优解中。

2.3 交换论证

将最优解中的某个选择替换为贪心选择，证明不会变差。

三、经典问题

3.1 活动选择问题

问题：选择最多不重叠的活动。

贪心策略：每次选择结束时间最早的活动。

证明：
设贪心选择的活动 ( g_1 ) 结束最早。假设最优解第一个活动为 ( o_1 )。
由于 ( g_1 ) 结束不晚于 ( o_1 )，用 ( g_1 ) 替换 ( o_1 ) 不会减少可选活动数。

public int maxActivities(int[][] activities) {
    // 按结束时间排序
    Arrays.sort(activities, (a, b) -> a[1] - b[1]);
    
    int count = 1;
    int end = activities[0][1];
    
    for (int i = 1; i < activities.length; i++) {
        if (activities[i][0] >= end) {
            count++;
            end = activities[i][1];
        }
    }
    return count;
}

3.2 跳跃游戏

问题：能否到达最后一个位置。

贪心策略：维护最远可达位置。

public boolean canJump(int[] nums) {
    int maxReach = 0;
    for (int i = 0; i < nums.length; i++) {
        if (i > maxReach) return false;  // 无法到达当前位置
        maxReach = Math.max(maxReach, i + nums[i]);
    }
    return true;
}

3.3 最少跳跃次数

public int jump(int[] nums) {
    int jumps = 0, currentEnd = 0, farthest = 0;
    
    for (int i = 0; i < nums.length - 1; i++) {
        farthest = Math.max(farthest, i + nums[i]);
        if (i == currentEnd) {
            jumps++;
            currentEnd = farthest;
        }
    }
    return jumps;
}

3.4 分发饼干

public int findContentChildren(int[] g, int[] s) {
    Arrays.sort(g);
    Arrays.sort(s);
    
    int child = 0, cookie = 0;
    while (child < g.length && cookie < s.length) {
        if (s[cookie] >= g[child]) {
            child++;
        }
        cookie++;
    }
    return child;
}

3.5 区间覆盖

选择最少点覆盖所有区间：每次选择当前区间的右端点。

public int findMinArrowShots(int[][] points) {
    if (points.length == 0) return 0;
    Arrays.sort(points, (a, b) -> Integer.compare(a[1], b[1]));
    
    int arrows = 1;
    int pos = points[0][1];
    
    for (int i = 1; i < points.length; i++) {
        if (points[i][0] > pos) {
            arrows++;
            pos = points[i][1];
        }
    }
    return arrows;
}

四、何时不能用贪心

4.1 0/1背包问题

贪心按价值/重量比选择，不一定最优。必须用动态规划。

4.2 判断方法

尝试构造反例，如果能找到贪心失败的情况，则不能用贪心。

五、总结

贪心算法的核心是证明贪心选择的正确性。常用方法包括反证法、归纳法和交换论证。贪心适用的问题通常具有”无后效性”和”局部最优即全局最优”的特性。当不确定时，先用小例子验证贪心策略是否总是正确。