贪心：局部选择如何通向全局最优｜算法讲义

问题#

贪心算法在每一步选择当前看来最有利的决策，并且不撤销它。真正困难的部分不是“选最小”或“选最大”，而是回答两个问题：

这个局部选择是否至少出现在某个全局最优解中？
做出选择后，剩余问题是否仍是同一种问题？

下面用四个常见模型建立可复用的方法：

按处理时间升序排队，使总等待时间最小；
每次合并最小的两堆，使总代价最小；
按结束时间升序选择区间，使互不相交区间数量最大；
从高位到低位试探答案，用可行性检查构造最大值。

核心思想与不变量#

相邻交换：短任务优先#

若相邻两个任务耗时分别为 $x>y$ ，顺序 x,y 比 y,x 多产生 $x-y$ 的等待代价。不断交换所有逆序对不会使答案变差，最终得到按耗时升序的最优序列。

不变量是：已经排在前面的任务按耗时升序，任何相邻逆序都可以被无损地消除。

最优合并：最小的两项先合并#

一次合并的重量会在祖先合并中反复计费，因此较小的重量应处在更深的位置。用最小堆反复取出两项合并，正是 Huffman 树的构造过程。

不变量是：堆中保存尚未连接到合并树的子树权值；取出的两个最小权值可作为最深的一对兄弟，而不损失最优性。

交换论证：最早结束的区间#

设当前最早结束的区间为 $I$ 。任取一个最优解，把其中第一个区间替换为 $I$ ，后续区间仍然可选且数量不变，所以总存在一个最优解包含 $I$ 。

不变量是：已经选择的区间互不相交，并且在选择同样数量的前提下，最后结束位置尽可能靠左。

按位贪心：优先保证高位#

非负整数的高位比所有更低位之和还重要。依次尝试把第 $b$ 位设为 1，如果存在一个满足此前高位前缀的完整可行解，就保留该位。

这里的 feasible(candidate) 必须回答“是否存在答案包含当前这些已确定的 1 位”，不能只是检查 candidate 本身是否可行；这是按位贪心正确性的关键契约。

复杂度#

短任务优先和区间选择都先排序，时间 $O(n\log n)$ ，排序后扫描 $O(n)$ 。
最优合并进行 $n-1$ 次堆操作，时间 $O(n\log n)$ ，空间 $O(n)$ 。
按位贪心检查 $B$ 个二进制位，若一次可行性检查为 $T_{check}$ ，总时间为 $O(BT_{check})$ 。

C++17 模板#

#include <algorithm>
#include <functional>
#include <iostream>
#include <numeric>
#include <queue>
#include <utility>
#include <vector>

using namespace std;

// 返回任务下标的最优顺序，以及总等待时间（第一人等待 0）。
pair<vector<int>, long long> shortest_job_first(const vector<long long>& time) {
    vector<int> order(time.size());
    iota(order.begin(), order.end(), 0);
    stable_sort(order.begin(), order.end(), [&](int lhs, int rhs) {
        return time[lhs] < time[rhs];
    });

    long long elapsed = 0;
    long long total_wait = 0;
    for (int id : order) {
        total_wait += elapsed;
        elapsed += time[id];
    }
    return {order, total_wait};
}

long long optimal_merge_cost(const vector<long long>& weights) {
    priority_queue<long long, vector<long long>, greater<long long>> heap(
        weights.begin(), weights.end());
    long long answer = 0;
    while (heap.size() > 1) {
        long long first = heap.top(); heap.pop();
        long long second = heap.top(); heap.pop();
        answer += first + second;
        heap.push(first + second);
    }
    return answer;
}

struct Interval {
    int left;
    int right; // 模板采用半开区间 [left, right)
};

vector<Interval> maximum_non_overlapping(vector<Interval> intervals) {
    sort(intervals.begin(), intervals.end(), [](const Interval& lhs, const Interval& rhs) {
        if (lhs.right != rhs.right) return lhs.right < rhs.right;
        return lhs.left < rhs.left;
    });

    vector<Interval> chosen;
    int last_right = 0;
    bool has_last = false;
    for (const Interval& interval : intervals) {
        if (!has_last || interval.left >= last_right) {
            chosen.push_back(interval);
            last_right = interval.right;
            has_last = true;
        }
    }
    return chosen;
}

template <class Feasible>
long long maximize_by_bits(int highest_bit, Feasible feasible) {
    long long answer = 0;
    for (int bit = highest_bit; bit >= 0; --bit) {
        long long candidate = answer | (1LL << bit);
        if (feasible(candidate)) answer = candidate;
    }
    return answer;
}

int main() {
    auto [order, waiting] = shortest_job_first({4, 1, 3, 2});
    cout << "order:";
    for (int id : order) cout << ' ' << id;
    cout << "\ntotal waiting = " << waiting << '\n';

    cout << "merge cost = " << optimal_merge_cost({1, 2, 3, 4}) << '\n';

    auto selected = maximum_non_overlapping({{1, 4}, {3, 5}, {0, 6}, {5, 7}, {8, 9}});
    cout << "intervals:";
    for (auto [left, right] : selected) cout << " [" << left << ',' << right << ')';
    cout << '\n';

    // 演示契约：所有不超过 limit 的数都可行，因此答案应为 limit。
    long long limit = 173;
    cout << "bitwise answer = "
         << maximize_by_bits(60, [&](long long candidate) { return candidate <= limit; })
         << '\n';
    return 0;
}

示例#

运行模板得到：

order: 1 3 2 0
total waiting = 10
merge cost = 19
intervals: [1,4) [5,7) [8,9)
bitwise answer = 173

任务耗时按 1,2,3,4 排列，总等待时间为 $0+1+3+6=10$ 。合并 1,2,3,4 时，代价依次为 $3,6,10$ ，总计 $19$ 。

易错点#

“每步选最优”不是证明。先尝试构造反例，再写交换论证、归纳或决策包容性证明。
区间端点语义必须统一：闭区间 [l,r] 与半开区间 [l,r) 的相交判断不同。
最优合并必须使用最小堆；默认的 priority_queue 是最大堆。
累加等待时间与合并代价容易超过 32 位，应使用 long long。
按位贪心的 feasible 要检查某个“高位前缀能否扩展成完整答案”，否则保留一个局部可行位可能堵死后续选择。
零钱问题中“每次取最大面额”只对某些币制成立，并不是通用定理。

问题#