贪心

贪心算法通常具有以下几个重要性质：

1. 贪心选择性质

• 局部最优：每一步都做出当前看起来最优的选择
• 不可撤销：一旦做出选择，不会回溯修改
• 子问题独立：当前决策不依赖于后续决策 1

示例：

// 常见的贪心模式
while(有选择) {
    choice = 选择当前最优解;
    result = 将选择添加到结果中;
    problem = 在剩余问题上继续;
}

2. 最优子结构性质

• 问题的最优解包含子问题的最优解
• 子问题之间相互独立，不存在交叉影响

3. 特征识别

贪心问题通常具有以下特征：

1. 排序帮助：

// 很多贪心问题第一步是排序
sort(arr.begin(), arr.end()); // 按某种规则排序

1. 局部决策：

for(int i = 0; i < n; i++) {
    // 每一步只考虑当前最优
    if(isGood(current)) {
        ans = max(ans, current);
    }
}

1. 不需要回溯：

// 贪心通常是单向遍历
// 不需要考虑之前的决策
visited[current] = true; // 标记已访问
// 不会再修改visited[current]

4. 正确性证明方法

贪心算法的正确性证明通常包含：

1. 归纳证明：

• 证明局部最优能导致全局最优
• 证明不存在更优解

1. 反证法：

• 假设存在更优解
• 证明可以通过贪心策略得到相同或更优结果

1. 交换论证：

• 证明任何非贪心策略都可以通过交换变成贪心策略
• 且交换不会使结果变差

5. 常见贪心策略

1. 选择排序：

// 按照某种规则排序后遍历
sort(intervals.begin(), intervals.end());
for(auto interval : intervals) {
    // 处理每个区间
}

1. 优先队列：

priority_queue<int> pq;
// 维护当前最优选择
while(!pq.empty()) {
    int top = pq.top();
    pq.pop();
    // 处理最优选择
}

1. 双指针：

int left = 0, right = n-1;
while(left < right) {
    // 从两端向中间处理
    // 每次选择最优的移动方向
}

6. 反例识别

不适合用贪心的情况：

• 需要考虑全局最优
• 当前决策依赖于后续决策
• 存在多个相互影响的约束条件

记住：贪心算法的关键是证明局部最优能导致全局最优！