贪心思想的核心概念与特点

• 定义贪心算法：局部最优解导向全局最优解的策略
• 适用场景：问题具有贪心选择性质与最优子结构
• 典型示例：活动选择问题、霍夫曼编码、最小生成树（Prim/Kruskal）

贪心算法的设计步骤

• 问题分解为多阶段决策过程
• 每阶段选择当前状态下的局部最优解
• 证明贪心选择的正确性（数学归纳法或反证法）

边界条件的识别与分析

• 输入极端情况：空集、单一元素、完全有序/无序数据
• 数值边界：零值、负值、极大/极小值（如整数溢出）
• 结构边界：图论中的孤立节点、完全图；字符串中的空串

贪心算法的局限性

• 失效场景：需全局回溯的问题（如0-1背包）
• 反例构造：硬币找零问题中非规范币值系统的失败案例
• 与动态规划的对比：无后效性 vs 状态转移依赖

实践中的验证方法

• 单元测试设计：覆盖常规输入与边界用例
• 压力测试：大规模数据下的性能与正确性验证
• 反例验证：尝试构造使贪心策略失效的数据

经典案例的边界分析

• 区间调度问题：重叠区间的不同分布模式
• Dijkstra算法：负权边的处理与距离初始化
• 任务调度：处理任务依赖关系与资源冲突

进阶应用与优化方向

• 贪心策略的混合使用：与回溯、分治结合
• 近似算法设计：允许次优解时的性能权衡
• 实际工程调整：动态调整贪心策略的权重参数