食品网站策划,网站建设送企业邮箱吗,建设工程项目管理网站,好的模板网站建设Python实现贪心算法(Greedy Algorithm)
概念
贪心算法是一种在每一步选择中都采取当前状态下最优的选择#xff0c;从而希望导致结果是全局最优的算法策略。
基本特点
局部最优选择#xff1a;每一步都做出当前看起来最佳的选择不可回退#xff1a;一旦做出选择#xf…Python实现贪心算法(Greedy Algorithm)
概念
贪心算法是一种在每一步选择中都采取当前状态下最优的选择从而希望导致结果是全局最优的算法策略。
基本特点
局部最优选择每一步都做出当前看起来最佳的选择不可回退一旦做出选择就不可更改高效性通常比其他全局优化算法更快不保证全局最优但能得到近似最优解
基本实现框架
以分数背包问题为栗子
def greedy_algorithm(items, capacity):# 通常先按某种规则排序items.sort(keylambda x: x[1]/x[0], reverseTrue)#按单位重量价值value/weight降序排序total_value 0 #背包中物品的总价值selected_items [] #选择的物品列表完整或部分物品#开始选择for item in items:if capacity item[0]:capacity - item[0]total_value item[1]selected_items.append(item)else:# 可选: 部分物品的情况(如分数背包问题)fraction capacity / item[0]total_value item[1] * fractionselected_items.append((item[0]*fraction, item[1]*fraction))breakreturn total_value, selected_items经典应用示例
1. 找零钱问题
def coin_change(coins, amount):coins.sort(reverseTrue)count 0change []for coin in coins:while amount coin:amount - coincount 1change.append(coin)return count if amount 0 else -1, change# 示例
coins [25, 10, 5, 1]
print(coin_change(coins, 63)) # 输出: (6, [25, 25, 10, 1, 1, 1])2. 区间调度问题
def interval_scheduling(intervals):# 按结束时间排序intervals.sort(keylambda x: x[1])selected []last_end -float(inf)for start, end in intervals:if start last_end:selected.append((start, end))last_end endreturn selected# 示例
intervals [(1, 3), (2, 4), (3, 5), (4, 6)]
print(interval_scheduling(intervals)) # 输出: [(1, 3), (3, 5)]3. 霍夫曼编码(数据压缩)
import heapqdef huffman_encoding(freq):heap [[weight, [symbol, ]] for symbol, weight in freq.items()]heapq.heapify(heap)while len(heap) 1:lo heapq.heappop(heap)hi heapq.heappop(heap)for pair in lo[1:]:pair[1] 0 pair[1]for pair in hi[1:]:pair[1] 1 pair[1]heapq.heappush(heap, [lo[0] hi[0]] lo[1:] hi[1:])return sorted(heapq.heappop(heap)[1:], keylambda p: (len(p[-1]), p))# 示例
freq {a: 5, b: 9, c: 12, d: 13, e: 16, f: 45}
print(huffman_encoding(freq))适用场景
问题具有贪心选择性质局部最优能导致全局最优最优子结构问题的最优解包含子问题的最优解典型应用 最小生成树(Prim和Kruskal算法)最短路径问题(Dijkstra算法)背包问题的分数版本任务调度问题文件压缩(霍夫曼编码)
贪心算法的局限性
不总是能得到全局最优解需要证明问题的贪心选择性质对某些问题可能需要结合其他算法(如动态规划)
贪心 vs 动态规划
特性贪心算法动态规划决策每个阶段做局部最优选择考虑所有可能的子问题复杂度通常更低通常更高最优解保证不总是总是存储需求通常更少需要存储子问题结果典型问题找零钱、任务调度背包问题、最长子序列
总结
贪心算法因其高效性在实际工程中应用广泛但使用时需要仔细分析问题是否适合贪心策略。
