Python常用算法——贪心算法与实战演练：从找零问题到最小生成树

前言

在算法的世界里，**贪心算法（Greedy Algorithm）**以其直观、高效的特点占据着重要的一席之地。顾名思义，“贪心”意味着在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法。

虽然贪心算法不能解决所有优化问题（例如0-1背包问题），但在许多特定场景下，如找零问题、活动选择、哈夫曼编码以及最小生成树等，它能以O(n \log n)甚至O(n)的时间复杂度给出完美的最优解。本文将深入探讨贪心算法的思想基础，并通过8个经典的Python实战案例，配合详细的代码实现与逻辑图解，带你掌握这一强大的算法工具。

算法思想基础与实现思路

核心思想

贪心算法的核心在于**“局部最优导致全局最优”**。它不从整体最优上加以考虑，所做出的仅是在某种意义上的局部最优解。

适用条件

要使用贪心算法解决问题，问题通常需要具备两个关键属性：

1. 贪心选择性质（Greedy Choice Property）：所求问题的整体最优解可以通过一系列局部最优的选择来达到。换句话说，当做出贪心选择时，不需要考虑子问题的解。
2. 最优子结构（Optimal Substructure）：一个问题的最优解包含其子问题的最优解。

实现步骤

1. 建立数学模型：将问题抽象化。
2. 分解问题：将问题分解为若干个子问题。
3. 局部最优选择：对每个子问题，根据某种贪心策略（如最大、最小、最早结束等）做出选择。
4. 合并解：将所有子问题的局部最优解合并成原问题的一个解。
5. 验证：证明该贪心策略确实能产生全局最优解（在博客实战中，我们通过经典案例来验证）。

算法演练

1. 解决“找零方案”问题

问题描述：假设商店有面值为1元、5角、2角、1角、5分、2分、1分的硬币，给定需要找零的金额，求最少需要的硬币数量。

算法分析：
这是典型的贪心应用场景。为了硬币数量最少，我们应该尽可能多地使用面值大的硬币。

• 策略：每次选择不超过剩余金额的最大面值硬币。
• 注意：此策略仅在硬币面值体系满足特定条件（如人民币体系）时有效。若面值为{1, 3, 4}，找6元时贪心会选4+1+1(3枚)，而最优是3+3(2枚)。但在本题给定的人民币面值下，贪心是最优的。

示意图逻辑：

目标金额: 0.78元 (78分)
可用面值: [100, 50, 20, 10, 5, 2, 1] (单位:分)

Step 1: 78 >= 50? 是 -> 选50分, 剩余28分 (硬币数: 1)
Step 2: 28 >= 50? 否 -> 跳过50
Step 3: 28 >= 20? 是 -> 选20分, 剩余8分  (硬币数: 2)
Step 4: 8 >= 20? 否 ... 8 >= 10? 否 ... 8 >= 5? 是 -> 选5分, 剩余3分 (硬币数: 3)
Step 5: 3 >= 5? 否 ... 3 >= 2? 是 -> 选2分, 剩余1分 (硬币数: 4)
Step 6: 1 >= 1? 是 -> 选1分, 剩余0分 (硬币数: 5)

结果: 50+20+5+2+1 = 78分，共5枚。

代码实现：
文件名：greedy_change.py

def greedy_change(amount, coins):
    """
    贪心算法解决找零问题
    :param amount: 需要找零的金额 (浮点数，单位元)
    :param coins: 硬币面值列表 (单位元)
    :return: 各面值硬币的数量字典
    """
    # 为了避免浮点数精度问题，转换为分 (整数)
    amount_cents = int(round(amount * 100))
    coins_cents = sorted([int(c * 100) for c in coins], reverse=True)
    
    result = {}
    count = 0
    
    for coin in coins_cents:
        if amount_cents == 0:
            break
        # 计算当前面值能用的最大数量
        num = amount_cents // coin
        if num > 0:
            result[coin/100.0] = num
            amount_cents -= num * coin
            count += num
            
    if amount_cents > 0:
        return None, "无法精确找零"
        
    return result, count

# 测试
if __name__ == "__main__":
    coins = [1, 0.5, 0.2, 0.1, 0.05, 0.02, 0.01]
    target = 0.78
    res, total = greedy_change(target, coins)
    print(f"找零 {target} 元:")
    if res:
        for k, v in res.items():
            print(f"  {k}元: {v}枚")
        print(f"总硬币数: {total}")
    else:
        print(res)

2. 解决“汽车加油”问题

问题描述：一辆汽车加满油后可行驶n公里，旅途中有k个加油站。指出应在哪些加油站停靠加油，使沿途加油次数最少。

算法分析：

• 策略：只要还能开到下一个加油站，就不加油；一旦无法到达下一个加油站，必须在当前能到达的最后一个加油站加油（或者说，在不得不加油时，选择离起点最远的那个可达加油站加油，这等同于“能跑多远跑多远”）。
• 思路：遍历加油站，累加距离。如果当前油量不足以到达下一站，则在上一个站点加油（计数+1，重置油量为满），并检查上一站是否也无法到达（若两站间距大于n，则无解）。

示意图逻辑：

满油里程 n = 100km
站点距离起点: [0, 50, 90, 140, 210, 260] (0为起点)
间距: 50, 40, 50, 70, 50

1. 起点(0)出发，油量100。
2. 到站1(50): 耗油50，剩50。能到下一站(90)吗？距离40 <= 50，能。不加油。
3. 到站2(90): 耗油40，剩10。能到下一站(140)吗？距离50 > 10，不能！
   -> 必须在站2加油。加油后油量100。计数=1。
4. 从站2(90)出发，去站3(140): 耗油50，剩50。能到下一站(210)吗？距离70 > 50，不能！
   -> 必须在站3加油。加油后油量100。计数=2。
5. 从站3(140)出发，去站4(210): 耗油70，剩30。能到下一站(260)吗？距离50 > 30，不能！
   -> 必须在站4加油。加油后油量100。计数=3。
6. 到达终点。
结果: 在站点2, 3, 4加油，共3次。

代码实现：
文件名：greedy_refuel.py

def min_refuel_stops(n, stations):
    """
    :param n: 满油可行驶公里数
    :param stations: 加油站距离起点的距离列表 (已排序，包含起点0和终点)
    :return: 最少加油次数，若无法到达返回-1
    """
    stops = 0
    current_fuel = n
    last_pos = 0
    
    # stations应该包含起点和终点，这里假设输入是距离列表
    # 为了逻辑清晰，我们计算相邻站点的间距
    for i in range(1, len(stations)):
        dist = stations[i] - stations[i-1]
        
        if dist > n:
            return -1 # 两站之间距离超过满油里程，无法到达
        
        if current_fuel >= dist:
            current_fuel -= dist
        else:
            # 油不够了，必须在上一站(stations[i-1])加油
            stops += 1
            current_fuel = n - dist # 加满后减去这段路程
            
    return stops

# 测试
if __name__ == "__main__":
    n = 100
    # 距离起点的距离：起点0, 站1:50, 站2:90, 站3:140, 站4:210, 终点:260
    stops_locs = [0, 50, 90, 140, 210, 260]
    res = min_refuel_stops(n, stops_locs)
    print(f"最少加油次数: {res}")

3. 解决“求最大子元素之和”问题

问题描述：给定一个整数数组（有正有负），找到一个具有最大和的连续子数组。
(注：此题通常使用动态规划Kadane算法，但其核心思想也包含贪心策略：若当前累加和为负，则丢弃前面的部分，从新元素重新开始，这是一种局部最优的贪心选择。)

算法分析：

• 策略：遍历数组，维护一个current_sum。如果current_sum加上当前元素后变小了（特别是变成负数），那么前面的序列对后续的和只有副作用，不如丢弃，从当前元素重新开始累加。
• 贪心点：一旦发现当前累积和小于0，立即“贪心”地放弃之前的所有努力，归零重来。

示意图逻辑：

数组: [-2, 1, -3, 4, -1, 2, 1, -5, 4]

i=0, val=-2: cur=-2 (<0, 丢弃), max=-2
i=1, val=1:  cur=1 (重新开始), max=1
i=2, val=-3: cur=-2 (<0, 丢弃), max=1
i=3, val=4:  cur=4 (重新开始), max=4
i=4, val=-1: cur=3, max=4
i=5, val=2:  cur=5, max=5
i=6, val=1:  cur=6, max=6  <-- 最大子数组 [4, -1, 2, 1]
i=7, val=-5: cur=1, max=6
i=8, val=4:  cur=5, max=6

代码实现：
文件名：greedy_max_subarray.py

def max_sub_array(nums):
    """
    基于贪心思想的Kadane算法
    :param nums: 整数列表
    :return: 最大连续子数组和
    """
    if not nums:
        return 0
    
    current_sum = nums[0]
    max_sum = nums[0]
    
    for i in range(1, len(nums)):
        # 贪心选择：如果当前累加和 + 当前值 < 当前值 (即current_sum < 0)，
        # 则抛弃前面的和，从当前值重新开始
        if current_sum < 0:
            current_sum = nums[i]
        else:
            current_sum += nums[i]
        
        # 更新全局最大值
        if current_sum > max_sum:
            max_sum = current_sum
            
    return max_sum

# 测试
if __name__ == "__main__":
    arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
    print(f"最大子数组和: {max_sub_array(arr)}")

4. 解决“幼儿园分糖果”问题

问题描述：老师给孩子们分糖果，每个孩子有需求因子g，每个糖果有大小s。当s \ge g时，代表该糖果能够满足孩子。求糖果最多能满足多少个孩子。

算法分析：

• 策略：为了满足不同需求的孩子，我们应该用最小的且能满足该孩子的糖果去喂他。这样可以把大糖果留给需求更大的孩子。
• 步骤：
  1. 将孩子需求g和糖果大小s都从小到大排序。
  2. 双指针遍历：尝试用当前最小的糖果去满足当前需求最小的孩子。
  3. 如果满足，计数+1，两个指针都后移；如果不满足，说明这个糖果太小，无法满足当前孩子（更无法满足后面的），只能丢弃该糖果（糖果指针后移），继续试下一个糖果。

示意图逻辑：

孩子需求 g: [1, 2, 3]
糖果大小 s: [1, 1, 3] (排序后)

1. 孩子(需1) vs 糖果(1): 1>=1 满足! (count=1), 移向下一个孩子和糖果
2. 孩子(需2) vs 糖果(1): 1>=2 不满足! 丢弃糖果, 移向下一个糖果
3. 孩子(需2) vs 糖果(3): 3>=2 满足! (count=2), 移向下一个孩子和糖果
4. 孩子(需3) vs 无糖果: 结束
结果: 2个孩子

代码实现：
文件名：greedy_assign_cookies.py

def find_content_children(g, s):
    """
    :param g: 孩子需求因子列表
    :param s: 糖果大小列表
    :return: 最多满足的孩子数
    """
    g.sort()
    s.sort()
    
    child_idx = 0
    cookie_idx = 0
    
    while child_idx < len(g) and cookie_idx < len(s):
        if s[cookie_idx] >= g[child_idx]:
            # 满足当前孩子
            child_idx += 1
        # 无论是否满足，当前糖果都被消耗或丢弃，尝试下一个糖果
        cookie_idx += 1
        
    return child_idx

# 测试
if __name__ == "__main__":
    g = [1, 2, 3]
    s = [1, 1, 3]
    print(f"最多满足孩子数: {find_content_children(g, s)}")

5. 解决“摇摆序列”问题

问题描述：如果连续数字之间的差严格地在正数和负数之间交替，则称为摇摆序列。求最长摇摆子序列的长度。

算法分析：

• 策略：不需要删除元素，只需要统计“峰”和“谷”的数量。如果一个序列一直在上升，我们只保留最高点作为“峰”；如果一直在下降，只保留最低点作为“谷”。
• 贪心点：在上升过程中，只要还在升，就继续往后看，直到开始下降的那一刻，之前的那个点就是局部极大值（峰），计入长度。反之亦然。

示意图逻辑：

数组: [1, 7, 4, 9, 2, 5]
差值: +6, -3, +5, -7, +3 (正负交替) -> 全长6

数组: [1, 17, 5, 10, 13, 15, 10, 5, 16, 8]
趋势: 
1->17 (升) -> 峰值候选17
17->5 (降) -> 确认17是峰, 5是谷候选 (长度+1)
5->10->13->15 (持续升) -> 贪心忽略中间，只看15
15->10 (降) -> 确认15是峰 (长度+1)
...
最终统计波峰波谷的数量 + 1 (起始点)

代码实现：
文件名：greedy_wiggle.py

def wiggle_max_length(nums):
    if len(nums) < 2:
        return len(nums)
    
    up = 1  # 以上升结尾的最长摇摆序列长度
    down = 1 # 以下降结尾的最长摇摆序列长度
    
    for i in range(1, len(nums)):
        if nums[i] > nums[i-1]:
            # 当前上升，可以接在之前的下降序列后面
            # 贪心：up = down + 1
            up = down + 1
        elif nums[i] < nums[i-1]:
            # 当前下降，可以接在之前的上升序列后面
            down = up + 1
        # 如果相等，up和down保持不变
            
    return max(up, down)

# 测试
if __name__ == "__main__":
    nums = [1, 17, 5, 10, 13, 15, 10, 5, 16, 8]
    print(f"最长摇摆子序列长度: {wiggle_max_length(nums)}")

6. 移除k个数字

问题描述：给定一个以字符串表示的非负整数num，移除k位数字，使得剩下的数字最小。

算法分析：

• 策略：要使剩下的数字最小，高位的数字越小越好。因此，我们应该从左到右遍历，如果发现当前数字比前一个数字小，且还有移除名额（k>0），则移除前一个数字（因为前一个数字在高位且更大）。
• 数据结构：使用单调栈。维护一个递增的栈，遇到比栈顶小的元素且k>0时，弹出栈顶。

示意图逻辑：

num = "1432219", k = 3
栈操作:
1. push 1 -> [1]
2. 4 > 1, push 4 -> [1, 4]
3. 3 < 4, pop 4 (k=2), 3 > 1, push 3 -> [1, 3]
4. 2 < 3, pop 3 (k=1), 2 > 1, push 2 -> [1, 2]
5. 2 == 2, push 2 -> [1, 2, 2]
6. 1 < 2, pop 2 (k=0), push 1 -> [1, 2, 1] (k用完，不再pop)
7. push 9 -> [1, 2, 1, 9]
结果: "1219"

代码实现：
文件名：greedy_remove_k_digits.py

def remove_kdigits(num, k):
    stack = []
    
    for digit in num:
        # 贪心：如果当前数字小于栈顶，且还能删除，则弹出栈顶
        while k > 0 and stack and stack[-1] > digit:
            stack.pop()
            k -= 1
        stack.append(digit)
    
    # 如果k还没用完，说明栈是递增的，从末尾删除剩余的k个
    if k > 0:
        stack = stack[:-k]
    
    # 去除前导零
    result = "".join(stack).lstrip('0')
    return result if result else "0"

# 测试
if __name__ == "__main__":
    num = "1432219"
    k = 3
    print(f"移除{k}位后的最小数: {remove_kdigits(num, k)}")

7. 解决“Kruskal”问题 (最小生成树)

问题描述：在一个连通加权无向图中，找到一棵包含所有顶点且边权之和最小的树。

算法分析：

• 策略：将所有边按权重从小到大排序。依次遍历每条边，如果这条边连接的两个顶点尚未连通（即不在同一个集合中），则选择这条边，并将这两个顶点所在的集合合并。
• 工具：并查集（Union-Find）用于高效判断连通性。
• 贪心点：每次总是选择当前未选边中权重最小且不构成环的边。

示意图逻辑：

边排序: (A-B, 1), (C-D, 2), (A-C, 3), (B-D, 4)...
1. 选(A-B, 1): A,B连通。
2. 选(C-D, 2): C,D连通。
3. 选(A-C, 3): A,C不连通，选中。此时{A,B,C,D}全连通。
4. 选(B-D, 4): B,D已在同一集合，跳过（否则成环）。

代码实现：
文件名：greedy_kruskal.py

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
    
    def find(self, i):
        if self.parent[i] != i:
            self.parent[i] = self.find(self.parent[i])
        return self.parent[i]
    
    def union(self, i, j):
        root_i = self.find(i)
        root_j = self.find(j)
        if root_i != root_j:
            self.parent[root_i] = root_j
            return True
        return False

def kruskal(n, edges):
    """
    :param n: 顶点数 (0 to n-1)
    :param edges: 列表 [(u, v, w), ...]
    :return: 最小生成树的边列表和总权重
    """
    # 按权重排序
    edges.sort(key=lambda x: x[2])
    uf = UnionFind(n)
    mst = []
    total_weight = 0
    
    for u, v, w in edges:
        if uf.union(u, v):
            mst.append((u, v, w))
            total_weight += w
            if len(mst) == n - 1:
                break
                
    return mst, total_weight

# 测试
if __name__ == "__main__":
    # 4个顶点，边格式 (u, v, weight)
    edges = [(0, 1, 10), (0, 2, 6), (0, 3, 5), (1, 3, 15), (2, 3, 4)]
    mst, weight = kruskal(4, edges)
    print(f"Kruskal MST边: {mst}")
    print(f"总权重: {weight}")

8. 解决“Prim”问题 (最小生成树)

问题描述：同上，求最小生成树。

算法分析：

• 策略：从任意一个顶点开始，构建一个集合S（已访问节点）。每次寻找连接S内节点和S外节点的权重最小的边，将该边及其连接的S外节点加入S。重复直到所有节点都在S中。
• 贪心点：每次扩展树时，都选择当前可用的最短边。
• 工具：优先队列（最小堆）来存储候选边。

示意图逻辑：

起点: 0
S={0}, 候选边: (0,3,5), (0,2,6), (0,1,10)
1. 选最小 (0,3,5): S={0,3}, 新增候选 (3,2,4), (3,1,15)
   当前候选池: (3,2,4), (0,2,6), (0,1,10), (3,1,15)
2. 选最小 (3,2,4): S={0,3,2}, 新增候选 (无新边或已存在)
   当前候选池: (0,2,6-无效), (0,1,10), (3,1,15) -> 注意(0,2)两端都在S内，忽略
3. 选最小 (0,1,10): S={0,3,2,1}, 完成。

代码实现：
文件名：greedy_prim.py

import heapq

def prim(n, adj_list):
    """
    :param n: 顶点数
    :param adj_list: 邻接表 {u: [(v, w), ...]}
    :return: 最小生成树的边列表和总权重
    """
    visited = [False] * n
    min_heap = [] # (weight, from_node, to_node)
    mst = []
    total_weight = 0
    
    # 从节点0开始
    visited[0] = True
    for v, w in adj_list.get(0, []):
        heapq.heappush(min_heap, (w, 0, v))
    
    while min_heap and len(mst) < n - 1:
        w, u, v = heapq.heappop(min_heap)
        
        if visited[v]:
            continue
        
        visited[v] = True
        mst.append((u, v, w))
        total_weight += w
        
        for next_v, next_w in adj_list.get(v, []):
            if not visited[next_v]:
                heapq.heappush(min_heap, (next_w, v, next_v))
                
    return mst, total_weight

# 测试
if __name__ == "__main__":
    # 构建邻接表
    adj = {
        0: [(1, 10), (2, 6), (3, 5)],
        1: [(0, 10), (3, 15)],
        2: [(0, 6), (3, 4)],
        3: [(0, 5), (1, 15), (2, 4)]
    }
    mst, weight = prim(4, adj)
    print(f"Prim MST边: {mst}")
    print(f"总权重: {weight}")

小结

贪心算法是解决优化问题的一把利器。通过上述8个案例，我们可以看到：

1. 简单高效：代码逻辑通常比动态规划更简洁，运行效率极高。
2. 策略关键：成功的关键在于找到正确的“贪心策略”（如：选最大的硬币、选最近的加油站、选最小的边）。
3. 局限性：并非所有问题都适用。在使用前，务必思考局部最优是否能推导至全局最优。对于无法确定的情况，可能需要回溯法或动态规划。

希望这篇文章能帮助你在Python实战中灵活运用贪心算法，解决更多实际问题！