本文目录导读：
我来用几个经典案例详细解释Python贪心算法的实现：
找零钱问题（最基础）
def make_change(amount, coins):
"""
用最少的硬币找零
贪心策略：每次选择面值最大的硬币
"""
coins.sort(reverse=True) # 从大到小排序
change = []
for coin in coins:
while amount >= coin:
amount -= coin
change.append(coin)
if amount == 0:
return change
else:
return None # 无法找零
# 测试
amount = 63
coins = [1, 5, 10, 25] # 常见硬币面值
result = make_change(amount, coins)
print(f"找零 {amount} 元：{result}") # [25, 25, 10, 1, 1, 1]
活动选择问题
def activity_selection(activities):
"""
选择最多不重叠的活动
贪心策略：每次选择结束时间最早的活动
活动格式：(开始时间, 结束时间)
"""
# 按结束时间排序
activities.sort(key=lambda x: x[1])
selected = [activities[0]] # 第一个活动一定选择
last_end = activities[0][1]
for start, end in activities[1:]:
if start >= last_end: # 不重叠
selected.append((start, end))
last_end = end
return selected
# 测试
activities = [(1, 3), (2, 5), (3, 7), (5, 9), (6, 10), (8, 11)]
result = activity_selection(activities)
print(f"选择的活动：{result}") # [(1, 3), (3, 7), (8, 11)]
背包问题（分数背包）
def fractional_knapsack(items, capacity):
"""
分数背包问题：物品可以分割
贪心策略：按单位重量价值从高到低选择
物品格式：(重量, 价值)
"""
# 计算单位价值并按降序排序
items_with_ratio = []
for weight, value in items:
ratio = value / weight
items_with_ratio.append((weight, value, ratio))
items_with_ratio.sort(key=lambda x: x[2], reverse=True)
total_value = 0
selected_items = []
for weight, value, ratio in items_with_ratio:
if capacity >= weight:
# 整个物品放入
total_value += value
selected_items.append((weight, value, 1.0))
capacity -= weight
else:
# 放入部分
fraction = capacity / weight
total_value += value * fraction
selected_items.append((weight, value, fraction))
break
return total_value, selected_items
# 测试
items = [(10, 60), (20, 100), (30, 120)]
capacity = 50
total_value, selected = fractional_knapsack(items, capacity)
print(f"最大价值：{total_value}")
print(f"选择的物品（重量，价值，比例）：{selected}")
霍夫曼编码
import heapq
from collections import Counter
class HuffmanNode:
def __init__(self, char, freq):
self.char = char
self.freq = freq
self.left = None
self.right = None
def __lt__(self, other):
return self.freq < other.freq
def huffman_encoding(text):
"""
霍夫曼编码：最优前缀编码
贪心策略：每次合并频率最小的两个节点
"""
if not text:
return "", {}
# 统计字符频率
freq = Counter(text)
# 创建优先队列
heap = [HuffmanNode(char, freq[char]) for char in freq]
heapq.heapify(heap)
# 构建霍夫曼树
while len(heap) > 1:
left = heapq.heappop(heap)
right = heapq.heappop(heap)
# 合并节点
merged = HuffmanNode(None, left.freq + right.freq)
merged.left = left
merged.right = right
heapq.heappush(heap, merged)
# 生成编码表
codes = {}
def generate_codes(node, code=""):
if node:
if node.char: # 叶子节点
codes[node.char] = code
else: # 内部节点
generate_codes(node.left, code + "0")
generate_codes(node.right, code + "1")
generate_codes(heap[0])
# 编码文本
encoded_text = "".join(codes[char] for char in text)
return encoded_text, codes
# 测试
text = "hello world"
encoded, codes = huffman_encoding(text)
print(f"原始文本：{text}")
print(f"编码表：{codes}")
print(f"编码结果：{encoded}")
print(f"压缩率：{len(encoded) / (len(text) * 8):.2%}")
任务调度问题
def task_scheduling(tasks):
"""
任务调度：最小化延迟时间
贪心策略：按截止时间排序，先做截止时间早的任务
任务格式：(任务名, 处理时间, 截止时间)
"""
# 按截止时间排序
tasks.sort(key=lambda x: x[2])
current_time = 0
schedule = []
max_lateness = 0
for name, processing_time, deadline in tasks:
start_time = current_time
finish_time = current_time + processing_time
# 计算延迟
lateness = max(0, finish_time - deadline)
max_lateness = max(max_lateness, lateness)
schedule.append((name, start_time, finish_time, lateness))
current_time = finish_time
return schedule, max_lateness
# 测试
tasks = [
("Task A", 3, 5),
("Task B", 2, 4),
("Task C", 4, 8),
("Task D", 1, 3)
]
schedule, max_lateness = task_scheduling(tasks)
print("任务调度表：")
for name, start, finish, lateness in schedule:
print(f" {name}: 开始={start}, 结束={finish}, 延迟={lateness}")
print(f"最大延迟：{max_lateness}")
关键实现要点
- 排序：大多数贪心算法需要先对数据排序
- 局部最优：每一步选择当前最优解
- 不可回溯：一旦做出选择就不能改变
贪心算法适用条件
- 最优子结构：问题的最优解包含子问题的最优解
- 贪心选择性质：通过局部最优选择能得到全局最优解
这些案例覆盖了贪心算法的常见应用场景,可以根据实际需求进行调整和扩展。
标签： Python案例
