本文共 2161 字，大约阅读时间需要 7 分钟。
在算法设计中，贪心算法是一种有效且高效的策略，其基本思想是通过局部最佳选择来达到全局最优解。贪心算法广泛应用于多个领域，包括背包问题、活动选择问题、数字拼接以及钢条切割问题等。本文将从贪心算法的基本原理出发，分析其在多个典型问题中的应用。
背包问题主要有两种形式：0-1背包和分数背包。两者的区别在于是否允许对同一物品进行多次选择或部分选择。
贪心算法在这两种背包问题中并不适用。分数背包可以通过特定的贪心策略（按单位重量价值排序）得到最优解，但0-1背包需要使用动态规划等更复杂的算法。
以一个例子为例，假设我们有以下商品：
背包容量为50千克。分数背包算法的实现步骤如下：
goods = [(60, 10), (100, 20), (120, 30)]goods.sort(key=lambda x: x[0] / x[1], reverse=True)m = [0 for _ in range(len(goods))]total_v = 0w = 50for i, (price, weight) in enumerate(goods): if w >= weight: m[i] = 1 total_v += price w -= weight else: m[i] = w / weight total_v += m[i] * price w = 0 breakprint(fractional_backpack(goods, 50))
结果为 (240.0, [1, 1, 0.6666666666666666])，即选取商品1和2，每个物品取完整，再加上商品3的部分。
在数字拼接问题中，贪心策略（按首位排序）虽然能快速得到结果，但并非总能得到最大值。例如，128和1286的拼接顺序决定了最终结果的不同。
128 + 1286 = 12812861286 + 128 = 1286128显然，后一种拼接方式更优。
为避免贪心策略的局限性，可以采用以下优化策略：
a + b 是否大于 b + a。from functools import cmp_to_keyli = [32, 94, 128, 1286, 6, 71]li.sort(key=cmp_to_key(lambda x, y: (x + y) > (y + x) ? -1 : 1 : 0))print(''.join(str(x) for x in li)) 最终结果为 94716321286128，这是最优拼接结果。
活动选择问题的目标是选择最大数量的不重叠的活动。贪心算法通过选择最早结束的活动作为优先选择，能够快速找到最优解。
活动按照结束时间排序后，逐步选择不冲突的活动。
activities = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11), (8, 12), (2, 14), (12, 16)]activities.sort(key=lambda x: x[1])res = [activities[0]]for activity in activities[1:]: if activity[0] >= res[-1][1]: res.append(activity)print(res)
最终结果包含4场活动：[(1, 4), (5, 7), (8, 11), (12, 16)]。
钢条切割问题需要考虑所有可能的切割方案，选择收益最大的方案。直接递归方法在算法复杂度上表现极差。
通过动态规划，避免重复计算，实现高效的递推式：
def cut_rod(p, n): if n == 0: return 0 r = [0] * (n + 1) for i in range(1, n + 1): max_val = p[i] for j in range(i + 1, n + 1): max_val = max(max_val, p[j] + cut_rod(p, j - 1 - i)) r[i] = max_val return r[n]
动态规划的核心在于存储已计算的子问题结果，避免重复计算。
通过对比可发现，动态规划算法大大提高了效率，适合处理较大规模的钢条切割问题。
转载地址：http://xctuk.baihongyu.com/