贪心思想的核心概念与特点
- 定义贪心算法：局部最优解导向全局最优解的策略
- 适用场景：问题具有贪心选择性质与最优子结构
- 典型示例：活动选择问题、霍夫曼编码、最小生成树（Prim/Kruskal）
贪心算法的设计步骤
- 问题分解为多阶段决策过程
- 每阶段选择当前状态下的局部最优解
- 证明贪心选择的正确性（数学归纳法或反证法）
边界条件的识别与分析
- 输入极端情况：空集、单一元素、完全有序/无序数据
- 数值边界：零值、负值、极大/极小值（如整数溢出）
- 结构边界：图论中的孤立节点、完全图；字符串中的空串
贪心算法的局限性
- 失效场景：需全局回溯的问题（如0-1背包）
- 反例构造：硬币找零问题中非规范币值系统的失败案例
- 与动态规划的对比：无后效性 vs 状态转移依赖
实践中的验证方法
- 单元测试设计：覆盖常规输入与边界用例
- 压力测试：大规模数据下的性能与正确性验证
- 反例验证：尝试构造使贪心策略失效的数据
经典案例的边界分析
- 区间调度问题：重叠区间的不同分布模式
- Dijkstra算法：负权边的处理与距离初始化
- 任务调度：处理任务依赖关系与资源冲突
进阶应用与优化方向
- 贪心策略的混合使用：与回溯、分治结合
- 近似算法设计：允许次优解时的性能权衡
- 实际工程调整：动态调整贪心策略的权重参数
