贪心算法理论与实践总结-EW帮帮网

文章目录

一、贪心算法的基本概念

定义：贪心算法是指在求解问题时，每一步都选择当前状态下的最优解（局部最优），从而希望最终达到全局最优的算法策略。其核心思想是“目光短浅”，不考虑整体影响，仅关注当前步骤的最佳选择。

二、贪心算法的适用条件

贪心算法并非对所有问题有效，需满足以下性质：

贪心选择性质：问题的全局最优解可以通过一系列局部最优选择达到。
最优子结构：问题的最优解包含子问题的最优解。

三、贪心算法的设计步骤

确定问题的最优子结构：分析问题是否可分解为子问题，且子问题的最优解构成全局最优解。
定义贪心策略：确定每一步选择的“最优”标准（如最小代价、最大收益、最短距离等）。
证明策略正确性：通过数学归纳法或反证法证明局部最优选择可推导出全局最优解（关键难点）。
实现算法：根据策略设计具体步骤，通常结合数据结构（如优先队列、排序）优化效率。

四、贪心算法的经典应用场景

1. 区间调度问题

问题描述：给定多个区间，选择不重叠的最大区间集合。
贪心策略：按区间结束时间排序，每次选结束时间最早的区间，确保剩余时间最大化。
示例：活动选择问题（LeetCode 435. 无重叠区间）。

2. 背包问题

0-1背包（不适用贪心）：物品不可分割，需用动态规划（贪心可能选到总价非最优的组合）。
分数背包（适用贪心）：物品可分割，按“单位重量价值”从高到低选择，填满背包。
策略：性价比 = 价值/重量，优先选性价比高的物品。

3. 最小生成树（MST）

Kruskal算法：按边权从小到大选边，用并查集避免环，直到连通所有节点（贪心选最小边）。
Prim算法：从任意节点出发，每次选连接当前树与未连接节点的最小边（贪心选最小边）。

4. 单源最短路径（Dijkstra算法）

策略：维护各节点到源点的最短距离，每次选距离最小的未访问节点，更新其邻接节点的距离（贪心选当前最短路径）。
前提：图中边权非负，否则需用Bellman-Ford算法。

5. 霍夫曼编码

目标：为字符生成最优前缀编码，使编码总长度最短。
策略：按字符频率构建霍夫曼树，频率低的字符分配较长编码，频率高的分配较短编码（贪心选频率最小的两个节点合并）。

6. 零钱兑换

问题：用最少硬币数凑出金额amount（若硬币面值满足“贪心性质”，如1、5、10、25）。
策略：每次选不超过剩余金额的最大面值硬币。
注意：若面值不满足贪心性质（如1、3、4，凑6时贪心选4+1+1，实际最优为3+3），需用动态规划。

五、贪心算法的正确性证明方法

交换论证法：假设存在一个最优解与贪心解不同，通过交换两者的部分选择，证明贪心解可以转化为最优解，且不会更差。
数学归纳法：证明对于所有子问题，贪心策略能得到最优解，进而推导出全局最优。
反证法：假设贪心策略不能得到最优解，推导出矛盾，从而证明策略的正确性。

六、贪心算法与动态规划的对比

特性	贪心算法	动态规划
决策方式	只看当前最优（局部最优）	考虑所有可能，记录子问题解
时间复杂度	通常更低（O(n logn)或O(n)）	通常更高（O(n²)或O(nk)）
适用场景	满足贪心选择性质和最优子结构	需考虑子问题重叠和最优子结构
经典问题	区间调度、Kruskal、Dijkstra	0-1背包、最长公共子序列

七、贪心算法的经典例题与解法

1. 跳跃游戏（LeetCode 55）

问题：给定数组nums，nums[i]表示从位置i可跳跃的最大距离，判断是否能到达最后一个位置。
贪心策略：维护当前能到达的最远位置max_reach，遍历数组时更新max_reach，若当前位置超过max_reach则失败。

代码思路：

def canJump(nums):
    max_reach, n = 0, len(nums)
    for i in range(n):
        if i > max_reach:  # 无法到达当前位置
            return False
        max_reach = max(max_reach, i + nums[i])
        if max_reach >= n - 1:  # 提前到达终点
            return True
    return True

2. 分发饼干（LeetCode 455）

问题：每个孩子有需求值g[i]，每个饼干有大小s[j]，求最多能满足多少孩子（孩子得到的饼干需≥需求）。
贪心策略：将g和s排序，每次用能满足当前孩子的最小饼干（避免浪费大饼干）。

代码思路：

def findContentChildren(g, s):
    g.sort()
    s.sort()
    i = j = 0
    while i < len(g) and j < len(s):
        if s[j] >= g[i]:  # 饼干满足孩子需求
            i += 1
        j += 1
    return i

3. 柠檬水找零（LeetCode 860）

问题：柠檬水5元，顾客付5、10、20元，求能否给所有顾客正确找零。
贪心策略：优先用大面值零钱找零（但需保留足够的5元给后续顾客）。
实现：记录5元和10元的数量，付20元时优先用10+5，其次用3张5元。

4. 加油站（LeetCode 134）

问题：环形路线上有n个加油站，每个加油站有油量gas[i]，从i到i+1需消耗cost[i]，求是否存在起点绕一圈。
贪心策略：若总油量≥总消耗，则必存在解；遍历加油站，当累计油量为负时，重置起点为下一个加油站。

八、贪心算法的陷阱与注意事项

局部最优≠全局最优：贪心策略可能在某些情况下失效（如零钱兑换问题中的非贪心面值），需先证明策略正确性。
策略选择的多样性：同一问题可能有多种贪心策略，需选择能导向全局最优的策略（如区间调度按结束时间排序比按开始时间更优）。
结合数据结构优化：优先队列（堆）、排序、哈希表等常与贪心算法结合，提升效率（如Dijkstra用优先队列优化）。

九、贪心算法的核心思想总结

贪心算法的本质是通过“短视”的局部最优选择，逐步构建全局最优解，其优势在于实现简单、效率高，但适用范围受限于问题的贪心性质。在实际应用中，需先分析问题是否满足贪心条件，再设计策略并验证正确性。对于不满足条件的问题，动态规划或回溯算法可能是更优的选择。

贪心算法理论与实践总结