贪心算法概述贪心算法Greedy Algorithm是一种在每一步选择中都采取当前状态下最优局部最优决策的算法希望通过局部最优解堆叠出全局最优解。贪心算法通常用于解决优化问题如最短路径、最小生成树、任务调度等。其核心思想是“贪心选择性质”和“最优子结构”。贪心算法的基本步骤问题分解将问题分解为多个子问题每个子问题需要做出一个选择。贪心选择在当前状态下选择局部最优解不考虑后续影响。迭代求解将子问题的解合并逐步构建全局解。贪心算法的适用条件贪心选择性质局部最优解能导致全局最优解。最优子结构问题的最优解包含子问题的最优解。经典贪心算法示例1. 找零问题目标用最少数量的硬币凑出指定金额假设硬币面额为1, 5, 10, 25。贪心策略每次选择面额最大的硬币。python复制插入def make_change(amount, coins[25, 10, 5, 1]): change [] for coin in coins: while amount coin: change.append(coin) amount - coin return change复制插入2. 活动选择问题目标选择最多的互不重叠的活动每个活动有开始和结束时间。贪心策略按结束时间排序每次选择最早结束且不与已选活动冲突的活动。python复制插入def activity_selection(activities): activities.sort(keylambda x: x[1]) # 按结束时间排序 selected [activities[0]] for start, end in activities[1:]: if start selected[-1][1]: selected.append((start, end)) return selected复制插入3. 霍夫曼编码目标用变长编码压缩数据频率高的字符用短编码。贪心策略每次合并频率最小的两个节点构建二叉树。贪心算法的优缺点优点简单高效时间复杂度通常较低如O(n log n)。缺点不保证全局最优解需验证问题是否满足贪心性质。贪心算法与动态规划的对比贪心算法不可回溯局部最优直接决定下一步。动态规划保存子问题解通过回溯比较多种选择。实践建议验证问题是否满足贪心性质。尝试反例确认贪心策略的正确性。结合数学归纳法或反证法证明贪心选择的合理性。贪心算法在解决特定问题时非常高效但需谨慎验证其适用性。