12 贪心算法的应用之经典贪心算法实例

在上一篇中，我们探讨了贪心算法与动态规划之间的区别，强调了它们在解决不同问题时的适用场景。贪心算法通常是一种较为简单且高效的策略，通常用于解决优化问题。接下来，我们将深入一些经典的贪心算法实例，以便更好地理解其实际应用及实现。

贪心算法概述

贪心算法是一种构造算法，它通过逐步选择当前最优解的方法来实现整体最优解。贪心算法通常包括以下几个步骤：

1. 选择一个局部最优解：在每一步中选择一个看似最优的选项。
2. 设定完成条件：确保在选择完成后能正确判断出整体的最优解。
3. 证明局部最优能导致全局最优：确保选取某个局部最优解不会影响最终解。

经典贪心算法实例

1. 找零问题

在找零问题中，我们有无限数量的不同面额的硬币，需要用最少数量的硬币来找零。假设我们有面额为 1、3 和 4 的硬币，而找零的金额为 6。

解法

我们可以贪心地选择最大面额的硬币。具体步骤如下：

1. 选择面额为 4 的硬币，剩余金额为 $6 - 4 = 2$。
2. 剩余金额 $2$ 可用两枚面额为 1 的硬币。

最终组合是：一枚面额为 4 的硬币和两枚面额为 1 的硬币，共三枚。

代码实现

def coin_change(coins, amount):
    coins.sort(reverse=True)  # 从大到小排序
    count = 0
    for coin in coins:
        while amount >= coin:
            amount -= coin
            count += 1
    return count if amount == 0 else -1

coins = [4, 3, 1]
amount = 6
print(coin_change(coins, amount))  # 输出: 3

2. 活动选择问题

活动选择问题是一个经典的调度问题，其中我们希望选择最大数量的活动，使得每对活动之间没有重叠。假设活动的开始和结束时间如下表所示。

活动	开始时间	结束时间
1	1	3
2	2	5
3	4	6
4	5	7
5	3	4

解法

该问题可以通过选择结束时间最早的活动来解决。具体步骤如下：

1. 将活动按结束时间排序。
2. 选择第一个活动，然后继续选择下一个活动，确保下一个活动的开始时间不与已选活动重叠。

代码实现

def activity_selection(activities):
    activities.sort(key=lambda x: x[1])  # 按结束时间排序
    selected = [activities[0]]  # 选择第一个活动
    last_end_time = activities[0][1]
    
    for i in range(1, len(activities)):
        if activities[i][0] >= last_end_time:  # 不重叠
            selected.append(activities[i])
            last_end_time = activities[i][1]
    
    return selected

activities = [(1, 3), (2, 5), (4, 6), (5, 7), (3, 4)]
print(activity_selection(activities))  # 输出: [(1, 3), (4, 6), (5, 7)]

3. 最小生成树（Kruskal算法）

最小生成树问题要求我们从一个带权图中选出边，使得所有顶点都被连通且边的权重和最小。Kruskal算法是一种实现方式，它采用贪心策略选择边。

解法

Kruskal算法的基本步骤包括：

1. 将所有边按权重排序。
2. 从权重最小的边开始选择，若选择的边不会形成回路，则将其加入结果中。

代码实现

class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))
    
    def find(self, p):
        if self.parent[p] != p:
            self.parent[p] = self.find(self.parent[p])
        return self.parent[p]
    
    def union(self, p, q):
        rootP = self.find(p)
        rootQ = self.find(q)
        if rootP != rootQ:
            self.parent[rootP] = rootQ

def kruskal(num_vertices, edges):
    edges.sort(key=lambda x: x[2])  # 按权重排序
    uf = UnionFind(num_vertices)
    mst = []
    
    for u, v, weight in edges:
        if uf.find(u) != uf.find(v):  # 不形成回路
            uf.union(u, v)
            mst.append((u, v, weight))
    
    return mst

edges = [(0, 1, 10), (0, 2, 6), (0, 3, 5), (1, 3, 15), (2, 3, 4)]
print(kruskal(4, edges))

总结

本文中，我们通过几个经典的案例深入探讨了贪心算法的应用。我们看到贪心算法在许多优化问题中表现出色，其核心在于如何定义“局部最优”和确保其能导致“全局最优”。贪心算法虽然简单，但在实际问题中应用时需要谨慎地验证其结果的有效性。

在下一篇文章中，我们将讨论复杂度分析与优化，尤其是如何计算时间复杂度。这也是编程中一个非常重要的方面，希望大家继续关注。