别再死记硬背了！用Python实战5个经典问题，彻底搞懂贪心算法

予晚

352人浏览 · 2026-05-30 12:32:22

予晚 · 2026-05-30 12:32:22 发布

用Python实战5大经典问题，掌握贪心算法的核心逻辑

第一次接触贪心算法时，很多人会被它"简单粗暴"的特性所迷惑——看似只需要每一步选择当前最优解，但真正动手实现时却常常陷入局部最优的陷阱。本文将带你通过五个经典问题的完整实现过程，从代码细节中理解贪心策略的精妙之处。不同于教科书式的理论讲解，我们会重点关注每个问题在实际编码中的关键转折点和易错环节。

1. 从硬币找零问题理解贪心算法的局限性

找零问题是最直观的贪心算法入门案例。假设我们需要用面额为[1, 5, 10, 20, 50]的硬币凑出63元，贪心策略会优先选择最大面额：

def greedy_change(amount, coins):
    coins.sort(reverse=True)  # 关键步骤：降序排列
    change = []
    for coin in coins:
        while amount >= coin:
            change.append(coin)
            amount -= coin
    return change if amount == 0 else None  # 处理无法找零的情况

这个实现有三个值得注意的细节：

降序排序 确保优先使用大面额
while循环 保证尽可能多地使用当前面额
最终检查 处理无法精确找零的情况

注意：当硬币面额为[1, 3, 4]时，用贪心算法凑6元会得到[4,1,1]而非最优解[3,3]。这是理解贪心局限性的典型案例。

硬币问题的现实变体包括：

自动售货机的找零系统
支付系统的最小纸币组合
资源分配中的最小单位切割

2. 活动选择问题中的贪心策略证明

会议室安排是活动选择问题的典型场景。我们需要在多个活动中选择最多数量的互不冲突活动：

def select_activities(activities):
    activities.sort(key=lambda x: x[1])  # 按结束时间排序
    selected = [activities[0]]
    for start, end in activities[1:]:
        if start >= selected[-1][1]:  # 检查时间冲突
            selected.append((start, end))
    return selected

这个实现揭示了贪心算法的关键特征：

排序标准的选择 ：按结束时间而非开始时间排序
冲突检测 ：只需比较与最后一个入选活动的时间
时间复杂度 ：O(nlogn)主要来自排序步骤

实际应用中的常见误区：

错误地按持续时间排序
忽略活动可能已经按某种顺序排列的情况
未考虑活动权重时的简单贪心失效

3. 霍夫曼编码中的优先队列应用

数据压缩领域的经典算法展示了贪心策略如何构建最优前缀码：

import heapq
from collections import defaultdict

class HuffmanNode:
    def __init__(self, char=None, freq=0):
        self.char = char
        self.freq = freq
        self.left = None
        self.right = None
    
    def __lt__(self, other):
        return self.freq < other.freq

def build_huffman_tree(freq_map):
    heap = [HuffmanNode(char, freq) for char, freq in freq_map.items()]
    heapq.heapify(heap)
    while len(heap) > 1:
        left = heapq.heappop(heap)
        right = heapq.heappop(heap)
        merged = HuffmanNode(freq=left.freq + right.freq)
        merged.left, merged.right = left, right
        heapq.heappush(heap, merged)
    return heap[0]

实现中的关键技术点：

优先队列的使用 ： heapq 模块实现最小堆
节点类的定义 ：需要实现 __lt__ 方法支持比较
树的构建过程 ：自底向上合并频率最低的节点

调试霍夫曼编码时常见的问题：

忘记处理单字符的特殊情况
编码表生成时的路径记录错误
非文本数据的频率统计方式

4. 最小生成树问题的两种贪心视角

Prim算法展示了贪心策略在图论中的应用：

import heapq

def prim_mst(graph):
    n = len(graph)
    visited = [False] * n
    heap = [(0, 0)]  # (weight, vertex)
    mst_edges = []
    
    while heap and len(mst_edges) < n - 1:
        weight, u = heapq.heappop(heap)
        if not visited[u]:
            visited[u] = True
            if weight > 0:  # 忽略初始节点
                mst_edges.append((u, weight))
            for v, w in graph[u]:
                if not visited[v]:
                    heapq.heappush(heap, (w, v))
    return mst_edges

关键实现细节：

邻接表的表示 ： graph 使用字典存储边和权重
堆的初始化 ：从任意节点开始（这里选择节点0）
边的筛选 ：避免将初始节点的虚拟边加入结果

与Kruskal算法的对比：

特性	Prim算法	Kruskal算法
数据结构	优先队列	并查集
时间复杂度	O(ElogV)	O(ElogE)
适用场景	稠密图	稀疏图

5. 车辆路径问题中的最近邻启发式

物流配送中的路径规划展示了贪心策略的实际价值：

import numpy as np

def vehicle_routing(customers, depot):
    route = [depot]
    unvisited = set(customers)
    
    while unvisited:
        current = route[-1]
        nearest = min(unvisited, 
                     key=lambda x: np.linalg.norm(np.array(x)-np.array(current)))
        route.append(nearest)
        unvisited.remove(nearest)
    
    route.append(depot)  # 返回仓库
    return route

实现中的优化空间：