基本框架

贪心框架通常包含四个部分：候选集合、可行性判断、局部选择规则和状态更新。

result = initial_solution
state = initial_state

while there are candidates:
    candidate = best_feasible_choice(candidates, state)
    if candidate does not exist:
        break
    apply(candidate, state)
    record(candidate, result)
    remove_or_update(candidate, candidates)

return result

best_feasible_choice() 不是简单地返回绝对值最大或最小的候选项，而是要同时满足：

1. 符合当前问题的局部评价标准；
2. 加入当前解后仍然满足约束；
3. 后续证明能够说明这一步是安全的。

不同问题的实现方式并不相同：活动选择通常先排序再扫描，Huffman 编码需要优先队列，Kruskal 需要排序和并查集。因此，贪心是一种策略，不是一段可以直接套用的固定代码。

WARN易错点 · 不要随意丢弃候选项

“当前最优候选不可行，所以以后也不可能有用”并不是通用事实。只有在题目约束和正确性证明支持这个结论时，才能安全地删除候选项。

两个关键性质

并不是所有具有最优子结构的问题都适合贪心。通常需要分别考察下面两个性质；其中“最优子结构”本身并不足以保证贪心正确。

贪心选择性质

DEF定义 · 贪心选择性质

对当前问题存在一个最优解，使得它包含贪心策略选择的第一步。换句话说，我们可以安全地先做出这个局部选择，而不会失去得到全局最优解的机会。

这里强调的是“存在一个包含贪心选择的最优解”，而不是“所有最优解的第一步都必须相同”。

最优子结构

DEF定义 · 最优子结构

如果一个问题的最优解已经做出某个合法选择，那么剩余部分必须由对应剩余子问题的最优解组成；否则可以替换剩余部分，得到更好的原问题解。

最优子结构说明“如何组合最优子问题”，但不告诉我们第一步应该选择什么，因此不能单独推出贪心策略正确。

典型应用类型

排序与选择

这类问题通常有一组候选对象，需要选出满足约束的子集，使目标函数最优。活动选择问题是经典例子：按结束时间升序处理，每次选择与已选活动不冲突且结束最早的活动。

区间覆盖、任务调度等问题也可能使用贪心，但具体排序规则取决于目标和约束，不能笼统地说“按截止时间排序就一定正确”。

优先队列驱动的构造

每一步从当前集合中取出最小或最大的元素，处理后可能生成新元素并重新放回集合。Huffman 编码和合并果子都属于这一类：它们反复处理当前最小的两个对象。

图上的特定优化问题

Kruskal、Prim 和 Dijkstra 都使用了贪心思想，但正确性依据不同：Kruskal 依赖环性质，Prim 依赖跨越当前树内外的最小权边具有安全性，Dijkstra 依赖非负边权带来的距离单调性。

可分数化的资源分配

分数背包允许切割物品，通常可以按单位价值从高到低装入。0-1 背包不允许切割物品，不能直接使用同样的贪心规则。