Python贪心算法

一、贪心算法核心思想

贪心算法（Greedy Algorithm）是一种在每一步选择中都采取当前状态下最优或最有利的选择，从而希望导致结果是全局最优的算法策略。

贪心算法的基本特征：

• 局部最优选择：每一步都选择当前看起来最好的选项

• 不可回溯性：一旦做出选择，就不再重新考虑

• 高效性：通常时间复杂度较低，实现简单

二、贪心算法的优缺点分析

优点：

1. 时间复杂度低：通常是O(n log n)或O(n)

2. 实现简单直观：代码通常简短易懂

3. 空间效率高：多数情况下只需要常数额外空间

4. 实时性好：适合在线处理和实时系统

缺点：

1. 不保证全局最优：局部最优不一定导致全局最优

2. 适用范围有限：只适用于具有贪心选择性质的问题

3. 证明困难：需要严谨的数学证明

4. 对输入敏感：不同输入可能需要不同的贪心策略

三、贪心算法的证明方法

方法一：反证法 - 例1：部分背包问题

反证法证明思路：
1、假设存在最优解A与贪心解B不同
2、找到第一个选择不同的物品，证明贪心选择不会更差
3、逐步调整，最终证明贪心解B至少与A一样好

问题：n个物品，重量w和价值v，背包容量C，可分割物品

# 读取物品数量n和背包容量t n, t = map(int, input().split()) # 存储物品信息：每个物品是(质量, 价值, 单位价值) golds = [] for i in range(n): m, v = map(int, input().split()) # 读取物品的质量和价值 p = v / m # 计算单位价值（价值/质量比） golds.append((m, v, p)) # 将物品信息添加到列表 # 按照单位价值从高到低排序（贪心策略：优先选择性价比高的物品） golds.sort(key=lambda x: x[2], reverse=True) # 初始化总价值和剩余容量 total_value = 0.0 remaining = t # 背包剩余容量 # 遍历排序后的物品 for m, v, p in golds: if remaining <= 0: # 如果背包已满，结束 break if m <= remaining: # 如果当前物品可以完整放入背包 total_value += v # 获得完整价值 remaining -= m # 减少剩余容量 else: # 如果只能放入部分 total_value += p * remaining # 按比例获得部分价值 remaining = 0 # 背包容量用完 # 输出结果，保留两位小数 print(f'{total_value:.2f}')

方法二：归纳法 - 例2：活动选择问题（凌乱的yyy）

归纳法证明：
1、基础：只有一个活动时，贪心选择最优
2、归纳：假设前k个活动的选择是最优的
3、递推：第k+1个活动选择结束最早的，证明仍然最优

问题：选择最大数量的互不重叠活动

# 读取活动数量 n = int(input()) # 存储活动信息：每个活动是(开始时间, 结束时间) contest = [] for i in range(n): a, b = map(int, input().split()) # 读取活动的开始时间和结束时间 contest.append((a, b)) # 将活动添加到列表 # 按照结束时间升序排序 # 贪心策略：优先选择结束时间早的活动，给后面的活动留下更多时间 contest.sort(key=lambda x: x[1]) # 初始化计数和上一个选择的活动的结束时间 count = 0 # 最多能选择的活动数量 last_end = -1 # 上一个选择的活动的结束时间，初始化为-1确保第一个活动可以被选择 # 遍历排序后的活动 for start, end in contest: # 如果当前活动的开始时间不早于上一个选择的活动的结束时间 # 说明两个活动不冲突，可以选择当前活动 if start >= last_end: count += 1 # 选择当前活动 last_end = end # 更新上一个选择的活动的结束时间 # 输出最多能选择的活动数量 print(count)

方法三：交换论证法 - 例3：排队接水问题

交换论证证明：
假设最优解中有两个相邻的人i,j，且t_i > t_j，交换i和j的位置，总等待时间不会增加，因此升序排列是最优的。

问题：n个人排队接水，如何安排使总等待时间最小

# 读取排队人数 n = int(input()) # 读取每个人的接水时间 time = list(map(int, input().split())) # 创建(编号, 时间)的元组列表 times = [] for i in range(n): t = time[i] times.append((i + 1, t)) # i+1作为编号（从1开始） # 按照接水时间升序排序，如果时间相同则按编号升序排序 # 贪心策略：让接水时间短的人先接水，可以减少总等待时间 times.sort(key=lambda x: (x[1], x[0])) # 输出接水顺序（编号） for i, t in times: print(i, end=' ') print() # 换行 # 计算总等待时间 waits = 0.0 # 使用浮点数以确保除法精度 for i in range(n): wait = 0 # 第i个人的等待时间 # 第i个人需要等待前面所有人的接水时间 for j in range(i): wait += times[j][1] waits += wait # 累加到总等待时间 # 计算平均等待时间 waits_mean = waits / n # 输出结果，保留两位小数 print(f'{waits_mean:.2f}')

四、经典贪心问题详解

例4：分卷子问题（最小合并代价）

问题：合并多堆卷子，每次合并两堆，代价为两堆之和，求最小总代价

import heapq def min_merge_cost_greedy(volumes): """ 分卷子问题贪心解法（哈夫曼树应用） 贪心策略：总是合并最小的两堆 参数： volumes: 各堆卷子的数量列表 返回： total_cost: 最小合并总代价 merge_sequence: 合并顺序记录 """ if len(volumes) <= 1: return 0, [] # 使用最小堆 min_heap = volumes[:] heapq.heapify(min_heap) total_cost = 0 merge_sequence = [] # 贪心合并：每次合并最小的两堆 while len(min_heap) > 1: # 取出最小的两个元素 first = heapq.heappop(min_heap) second = heapq.heappop(min_heap) # 合并代价 merge_cost = first + second total_cost += merge_cost merge_sequence.append((first, second, merge_cost)) # 将合并结果放回堆中 heapq.heappush(min_heap, merge_cost) return total_cost, merge_sequence # 示例使用 volumes = [3, 4, 2, 6, 1] min_cost, sequence = min_merge_cost_greedy(volumes) print(f"最小合并代价: {min_cost}") print(f"合并顺序: {sequence}")

例5：合并果子问题

问题：类似分卷子，但可能有额外约束

import heapq # 导入堆队列算法模块（最小堆） # 读取水果数量 n = int(input()) # 读取每个水果的重量，转换为列表 fruits = list(map(int, input().split())) # 将列表转换为最小堆（堆化） # 堆是一种特殊的二叉树结构，最小堆的根节点总是最小的元素 heapq.heapify(fruits) # 初始化总消耗体力值 total_cost = 0 # 当堆中还有不止一个水果时继续合并 while len(fruits) > 1: # 取出堆中最小的两个水果（堆顶元素） a = heapq.heappop(fruits) # 弹出并返回最小元素 b = heapq.heappop(fruits) # 弹出并返回次小元素 # 合并这两个水果需要的体力值 = 它们的重量之和 cost = a + b # 累加到总消耗体力值 total_cost += cost # 将合并后的新水果（重量为cost）放回堆中 heapq.heappush(fruits, cost) # 将新元素推入堆，保持堆性质 # 输出合并所有水果需要的最小总体力值 print(total_cost)

例6：哈夫曼编码问题

问题：给定字符频率，设计最优二进制编码

class HuffmanNode: """哈夫曼树节点类""" def __init__(self, freq, char=None): self.freq = freq # 频率 self.char = char # 字符（叶子节点才有） self.left = None # 左子节点 self.right = None # 右子节点 def __lt__(self, other): """用于堆比较：按频率比较""" return self.freq < other.freq def build_huffman_tree(freq_dict): """ 构建哈夫曼树 贪心策略：每次合并频率最小的两个节点 参数： freq_dict: 字符频率字典 {字符: 频率} 返回： root: 哈夫曼树的根节点 """ if not freq_dict: return None # 创建叶子节点并加入最小堆 heap = [] for char, freq in freq_dict.items(): node = HuffmanNode(freq, char) heapq.heappush(heap, node) # 贪心构建哈夫曼树 while len(heap) > 1: # 取出频率最小的两个节点 left = heapq.heappop(heap) right = heapq.heappop(heap) # 创建新内部节点 merged_freq = left.freq + right.freq merged_node = HuffmanNode(merged_freq) merged_node.left = left merged_node.right = right # 放回堆中 heapq.heappush(heap, merged_node) return heap[0] if heap else None def generate_huffman_codes(root, current_code="", codes={}): """ 生成哈夫曼编码 参数： root: 哈夫曼树根节点 current_code: 当前路径编码 codes: 存储编码的字典 返回： codes: 字符到编码的映射 """ if root is None: return codes # 如果是叶子节点，记录编码 if root.char is not None: codes[root.char] = current_code if current_code else "0" else: # 递归遍历左子树（编码加'0'） generate_huffman_codes(root.left, current_code + "0", codes) # 递归遍历右子树（编码加'1'） generate_huffman_codes(root.right, current_code + "1", codes) return codes def calculate_compression_rate(original_text, freq_dict, huffman_codes): """ 计算哈夫曼编码的压缩率 参数： original_text: 原始文本 freq_dict: 字符频率 huffman_codes: 哈夫曼编码 返回： compression_rate: 压缩率 """ # 原始比特数（假设8-bit ASCII） original_bits = len(original_text) * 8 if original_text else 0 # 编码后比特数 encoded_bits = 0 for char, freq in freq_dict.items(): code_length = len(huffman_codes.get(char, "")) encoded_bits += freq * code_length if original_bits == 0: return 0 compression_rate = 1 - (encoded_bits / original_bits) return compression_rate # 完整示例 def huffman_coding_example(text): """哈夫曼编码完整示例""" if not text: return None # 1. 统计字符频率 freq_dict = {} for char in text: freq_dict[char] = freq_dict.get(char, 0) + 1 # 2. 构建哈夫曼树 root = build_huffman_tree(freq_dict) # 3. 生成编码 codes = generate_huffman_codes(root) # 4. 计算压缩率 compression_rate = calculate_compression_rate(text, freq_dict, codes) # 5. 编码文本 encoded_text = ''.join(codes[char] for char in text) return { 'frequency': freq_dict, 'huffman_tree': root, 'codes': codes, 'encoded_text': encoded_text, 'compression_rate': compression_rate, 'original_length': len(text) * 8, 'encoded_length': len(encoded_text) } # 使用示例 text = "this is an example for huffman encoding" result = huffman_coding_example(text) print(f"字符频率: {result['frequency']}") print(f"哈夫曼编码: {result['codes']}") print(f"压缩率: {result['compression_rate']:.2%}")

五、贪心算法的适用条件与判断

适用条件：

1、贪心选择性质

1）局部最优选择能导致全局最优解

2）可以通过数学证明验证

2、最优子结构

1）问题的最优解包含子问题的最优解

2）子问题独立且可递归求解

3、无后效性

1）当前决策不影响后续决策的最优性

2）决策序列的代价可加性

贪心算法选择决策树：

开始
↓
问题是否可分解为子问题？ → No → 不适合贪心
↓ Yes
子问题是否具有最优子结构？ → No → 考虑动态规划
↓ Yes
能否做出局部最优选择？ → No → 考虑回溯/分支限界
↓ Yes
局部最优是否保证全局最优？ → No → 可能需要其他方法
↓ Yes
✓ 适合使用贪心算法

六、贪心 vs 动态规划对比

对比维度	贪心算法	动态规划
决策方式	局部最优，不可回溯	考虑所有可能，可回溯
时间复杂度	通常O(n log n)或O(n)	通常O(n²)或更高
空间复杂度	通常O(1)或O(n)	通常O(n²)需要存储状态
解的质量	可能不是全局最优	保证全局最优
适用问题	活动选择、哈夫曼编码、最小生成树	0-1背包、最长公共子序列
实现难度	相对简单	相对复杂

七、贪心算法的实战技巧

技巧1：预处理排序

def greedy_with_sorting(data): """大多数贪心算法需要先排序""" # 关键：确定正确的排序标准 sorted_data = sorted(data, key=custom_key_function) # ... 贪心处理逻辑

技巧2：使用优先队列

def greedy_with_heap(data): """需要频繁获取最小/最大值时使用堆""" import heapq heapq.heapify(data) while condition: current = heapq.heappop(data) # 获取当前最优 # ... 处理逻辑 heapq.heappush(data, new_item) # 更新堆

技巧3：边界条件处理

def robust_greedy(data): """健壮的贪心算法实现""" if not data: # 空输入处理 return default_value # 特殊输入处理 if len(data) == 1: return handle_single_case(data[0]) # 正常贪心逻辑 try: result = greedy_logic(data) except Exception as e: # 异常处理 return fallback_solution(data) return result

八、常见陷阱与避免方法

陷阱1：错误的贪心策略

# 错误示例：0-1背包问题用贪心（单位价值排序） def wrong_knapsack_greedy(weights, values, capacity): items = sorted(zip(weights, values), key=lambda x: x[1]/x[0], reverse=True) total_value = 0 for w, v in items: if capacity >= w: capacity -= w total_value += v return total_value # 可能不是最优解！ # 正确：0-1背包应用动态规划

陷阱2：忽略证明

• ❌ 直接实现看似合理的贪心策略

• ✅ 先用数学证明或构造反例验证

陷阱3：过度优化

• ❌ 追求过于复杂的贪心策略

• ✅ 保持简单，必要时用其他算法补充

九、总结与最佳实践

贪心算法是算法工具箱中的重要工具。正确使用时，它能提供高效的解决方案。总结关键点：

1. 先证明后实现：确保问题具有贪心选择性质

2. 从简单开始：先实现基础版本，再优化

3. 充分测试：用边界用例和随机数据测试

4. 保持灵活性：当贪心失败时，考虑动态规划等其他方法

总结：

• 掌握经典的贪心问题模板

• 理解各种证明方法的适用场景

• 在实际问题中积累经验，培养对贪心适用性的直觉

（本文例题来自洛谷）