贪心

贪心算法是一种在每步决策中均采取当前局部最优选择的策略，其核心在于满足贪心选择与最优子结构性质，以极低的时间复杂度求解全局最优解，但需注意在不满足性质时容易陷入无法回溯的局部最优陷阱。

January 1, 1990算法设计1分钟阅读

贪心算法（Greedy Algorithm） 是一种在每一步决策中都采取当前状态下最好或最优（即最有利）的选择，从而希望导致全局最好或最优的算法策略。

其核心思想非常直接：只顾眼前，不顾大局。它并不从整体最优上加以综合考虑，做出的是某种意义上的局部最优解。

贪心算法简单且高效，但并非所有优化问题都能用贪心解决。能够使用贪心算法求解的问题，必须严苛地满足以下两个核心性质：

贪心选择性质指的是：问题的全局最优解，可以通过一系列局部最优的选择（即贪心选择）一步步构造出来。

在求解过程中的每一个阶段，我们仅凭当前已有的信息做出眼前最好的选择，完全不需要考虑未来的选择，也不需要依赖后续子问题的解，更不存在回溯机制。

在实际应用中，直觉上的“贪心策略”极易出错。要证明一个贪心选择的正确性，最常用的数学方法是剪枝与替换法（通常结合反证法）：

设定假设：假设存在一个全局最优解 $O$ ，且 $O$ 没有做出我们预想的贪心选择 $G$ 。
构造替换：找到 $O$ 中第一个与贪心选择 $G$ 不同的决策点，用 $G$ 替换该决策，构造出一个新的解 $O'$ 。
推导证明：证明新解 $O'$ 的质量（收益/成本）不亚于原最优解 $O$ 。
得出结论：说明贪心选择 $G$ 同样能够导向全局最优解，从而证实贪心策略的正确性。

最优子结构性质指的是：原问题的最优解中，包含了其子问题的最优解。

这意味着整体的最优性可以由局部的最优性递推而来。如果一个问题的最优解包含的子问题解不是最优的，那么原问题的解也绝不可能是最优的。

规模缩减：大问题与子问题的结构完全一致，仅参数与数据规模变小。
决策独立：子问题之间相互独立，在一个子问题中做出的决策不影响其他子问题的选择范围。

💡 注意：最优子结构性质并非贪心算法独有，动态规划（Dynamic Programming） 同样建立在最优子结构的基础之上。

算法类型	核心决策机制	是否回溯	时间复杂度	适用关键条件
贪心算法	每步仅选当前局部最优，单向推进	否	极低（通常 $O(N \log N)$ 或 $O(N)$ ）	同时满足贪心选择与最优子结构
动态规划	穷举所有可能重叠子问题，保留状态最优值	否（无后效性）	中等（通常为多项式复杂度）	满足最优子结构与重叠子问题
暴力搜索/回溯	遍历所有状态空间，尝试每一种可能组合	是	极高（指数级或阶乘级）	无特殊性质要求，求解精确解/可行解

在贪心算法中，局部最优陷阱指的是：算法在求解的每一个阶段，都做出了当前看来最有利的选择，但这些短视的局部最优决策累加起来后，却阻断了通往总体最佳方案（全局最优解）的路径，最终收敛于一个次优结果的现象。

它是导致贪心算法在很多经典组合优化问题中宣告失效的根本原因。

贪心算法运行机制有两个关键约束，这两个约束共同构成了“陷阱”的触发条件：

不可回溯性（No Backtracking）：算法一旦在当前状态做出了选择，该分支就永久固定，绝不“翻案”重新选择。
缺乏前瞻性（Short-sightedness）：算法只评估当前这一步的即时收益，完全不评估该选择对未来可能选项造成的限制。

当原问题不满足“贪心选择性质”时，选择眼前收益最大的选项，往往会导致未来的资源被过度占用或浪费，从而彻底封死了到达最优解的通道。

如果把求解过程抽象为一棵决策树：

                    [初始状态]
                   /        \
            (贪心选择)      (暂非最优选择)
                 /            \
            [状态 A]         [状态 B]
               |                |
         [局部最优解]      [全局最优解]
       (贪心终止于此)     (真实最优终点)

贪心算法：在根节点处直接评估下层节点，发现“状态 A”当前得分高于“状态 B”，便直接裁掉“状态 B”整个分支，顺着状态 A 一路走到底。当走到底部发现总分不够高时，由于不能回溯，已无法挽回。
动态规划（DP）：不会盲目裁剪分支。它会保留“状态 A”和“状态 B”的推导路径，在子问题重叠和递推过程中进行全局比较，最终准确识别并保留通往“全局最优解”的路径。

问题描述：在经典的活动选择问题中，给定 $N$ 个活动的开始与结束时间（同一时间只能参加一个），目标是安排参加尽可能多的活动。

贪心策略：每次优先选择结束时间最早且与已选活动不冲突的活动。

贪心选择性质：最早结束的活动能给后续留出最大的时间空间，替换任何其他选择都不影响总数最优。
最优子结构性质：选定首个活动 $A$ 后，剩余相容活动集合即转化为规模更小的同类子问题。

优先装入单位重量价值最高（性价比 $V/W$ ）的物品。由于物品可以任意切分，高性价比物品总能完整装入或切割填满剩余空间，因此始终满足贪心选择性质。

0-1 背包反例（背包容量 $6$ ）

物品参数：A（重 $4$ /值 $8$ /性价比 $2.0$ ）、B（重 $3$ /值 $5$ /性价比 $1.67$ ）、C（重 $3$ /值 $5$ /性价比 $1.67$ ）。

结果对比：

贪心选择（按性价比优先）：优先装入 A，占用容量 $4$ ，剩余容量 $2$ 无法再装 B/C，最终价值为 $8$ （陷阱解）。
全局最优：选择 B + C，占用总重量 $6$ ，最终价值为 $10$ 。

零钱兑换反例（目标金额： $6$ 元，面额： $\{4, 3, 1\}$ 元）

贪心路线（大面额优先）：选 $4$ 元后再凑 $2$ 元（ $4 + 1 + 1$ ），共需 $3$ 枚硬币 (陷阱解)。
全局最优：直接选择 $3 + 3$ ，只需 $2$ 枚硬币。

[抽象数学模型] ➔ [确定贪心策略] ➔ [尝试数学证明(剪枝替换法)]
                                    │
                  ┌─────────────────┴─────────────────┐
           【证明成功】                         【存在反例/证明失败】
                  │                                   │
       [使用排序/堆实现]                    [切换至动态规划(DP)或回溯]

建立数学模型：明确问题的约束条件与目标函数。
划分决策阶段：将大问题的求解拆解为若干个连续的单步决策。
制定贪心策略：定义什么是“当前局部最优选择”。
验证与避坑（最核心环节）：
- 形式化证明：尝试用数学归纳法或剪枝替换法证明局部最优可导出全局最优。
- 寻找反例：用极小规模的数据做手动推演，若发现反例立刻判定贪心失效。
切换算法框架：若问题不具备贪心选择性质，但具有最优子结构，及时转换为动态规划（DP）或搜索回溯。