贪心算法题实战详解

文章目录

- - 例题1：活动安排问题
  - 例题2：货币找零问题
  - 例题3：分数背包问题（部分背包问题）
  - 例题4：最小生成树问题（Prim算法）
  - 例题5：哈夫曼编码
  - 例题6：活动选择问题
  - 例题7：硬币找零问题

贪心算法是一种在每一步选择中都采取在当前状态下最好或最优（局部最优）的选择，以期望通过一系列局部最优决策达到全局最优解的算法。请注意，贪心算法并不总是能得到全局最优解，但在某些特定问题上非常有效。下面通过几个实战例题来详细解析贪心算法的应用。

例题1：活动安排问题

问题描述：
给定一系列会议的时间段，包括每个会议的开始时间和结束时间，要求计算出最多能参加多少个会议，且这些会议之间不能重叠。

解题思路：
按照会议结束时间的先后顺序对所有会议进行排序。每次选择结束时间最早的会议参加，并移除所有与之冲突的会议（即开始时间小于等于该会议结束时间的会议）。重复此过程，直到没有会议可选。

代码示例（伪代码）:

sort(会议列表, 按结束时间升序)
已安排会议数 = 0
结束时间 = -∞

for 会议 in 会议列表:
    if 会议开始时间 > 结束时间:
        已安排会议数 += 1
        结束时间 = 会议结束时间

return 已安排会议数

例题2：货币找零问题

问题描述：
给定不同面额的硬币和一个总金额，计算最少需要多少枚硬币凑成这个总金额。

解题思路：
从最大面额的硬币开始考虑，尽可能多地使用大面额的硬币，然后逐步减小面额直到凑够总金额。这是一种典型的贪心策略。

代码示例（伪代码）:

硬币数量 = 0
剩余金额 = 总金额

sort(硬币列表, 降序)

for 硬币面额 in 硬币列表:
    while 剩余金额 >= 硬币面额:
        硬币数量 += 1
        剩余金额 -= 硬币面额

return 硬币数量

例题3：分数背包问题（部分背包问题）

问题描述：
给定一组物品，每个物品有一定的价值和体积，以及一个背包的最大承载量，要求在不超过背包容量的情况下，使装入背包的物品总价值最大。

解题思路：
与0-1背包不同，分数背包允许物品分割，可以取物品的一部分。这里可以按单位体积价值从大到小排序，优先选择单位体积价值高的物品尽可能多地装入背包。

代码示例（伪代码）:

sort(物品列表, 按单位体积价值降序)

总价值 = 0

for 物品 in 物品列表:
    可以取的数量 = 背包当前剩余容量 / 物品体积
    取的数量 = min(可以取的数量, 物品总量)
    总价值 += 取的数量 * 物品价值
    背包当前剩余容量 -= 取的数量 * 物品体积

return 总价值

以上实例展示了贪心算法在不同场景下的应用，关键在于识别问题是否适合贪心策略，即局部最优解能否导致全局最优解。在实际应用中，还需要注意贪心算法的局限性，并非所有问题都能通过贪心策略获得最优解。

例题4：最小生成树问题（Prim算法）

问题描述：
在一个带权无向图中，找到一棵包括所有顶点的树，使得树的所有边的权重之和尽可能小。

解题思路：
Prim算法是解决最小生成树问题的一种贪心策略。算法开始时，任选一个顶点加入到树中，之后每次从未加入到树中的顶点中选择一个与当前树相连的边权值最小的顶点加入树中，直到所有顶点都被加入到树中。

代码示例（伪代码）:

初始化已选择顶点集合为任意一个顶点，未选择顶点集合为其余顶点
初始化最小生成树的边集为空

while 未选择顶点集合非空:
    找到连接已选择顶点集合和未选择顶点集合的最小权重边 (u, v)
    将边 (u, v) 加入最小生成树的边集中
    将顶点 v 从未选择顶点集合移到已选择顶点集合

返回最小生成树的边集

例题5：哈夫曼编码

问题描述：
给定一串字符及其出现频率，设计一种编码方式使得编码后的字符串总长度最短。

解题思路：
哈夫曼编码是一种构造前缀编码的方法，通过构建一棵哈夫曼树来实现。首先将所有字符看作叶子节点，根据频率构建最小二叉堆，每次从堆中取出两个频率最小的节点合并成一个新的节点（新节点的频率为两个子节点之和），并放回堆中。重复这一过程直到堆中只剩下一个节点（树的根）。从根到叶子的路径即为该字符的编码。

代码示例（伪代码）:

将所有字符及其频率构造成节点，并放入最小堆中

while 堆中节点数量 > 1:
    取出频率最小的两个节点
    创建一个新的内部节点，其频率为两个子节点频率之和
    将新节点加入堆中，同时删除那两个频率最小的节点

从根节点出发，遍历哈夫曼树，生成每个字符的编码

贪心算法以其直观和效率在许多问题中展现出独特的优势，但其适用范围有限，主要适用于能够通过局部最优直接推导出全局最优的问题。在设计贪心算法时，关键在于正确识别问题的贪心性质，并巧妙地定义“贪婪准则”。上述例题展示了贪心算法在不同场景下的灵活应用，希望对你有所帮助。

例题6：活动选择问题

问题描述：
给定一系列活动，每个活动都有一个开始时间和结束时间。选择最多的活动数量，使得这些活动之间互不冲突，即任意两个活动不能同时进行。

解题思路：
这是一个典型的贪心问题，可以按照活动的结束时间对所有活动进行排序。选择活动时，总是选择结束时间最早的活动，这样能保证后续有更多的机会选择其他不冲突的活动。

代码示例（Python）:

def activitySelection(startTimes, endTimes):
    # 按照结束时间对活动进行排序
    activities = sorted(zip(startTimes, endTimes), key=lambda x: x[1])
    
    # 初始化第一个活动
    lastEnd = activities[0][1]
    selectedActivities = [activities[0]]
    
    for start, end in activities[1:]:
        # 如果当前活动的开始时间大于上一个选择活动的结束时间，则选择此活动
        if start >= lastEnd:
            selectedActivities.append((start, end))
            lastEnd = end
            
    return selectedActivities

# 示例输入
startTimes = [1, 3, 0, 5, 8, 5]
endTimes = [2, 4, 6, 7, 9, 9]

# 调用函数
selected = activitySelection(startTimes, endTimes)
print("Selected Activities:", selected)

例题7：硬币找零问题

问题描述：
给定不同面额的硬币和一个总金额，计算最少需要多少枚硬币凑出这个总金额。

解题思路：
对于每一种面额的硬币，尽可能多地使用它，直到不足以再使用为止，然后转向下一个较小面额的硬币。这是一种贪心策略，因为它在每一步都做出了局部最优的选择。

代码示例（Python）:

def coinChange(coins, amount):
    coins.sort(reverse=True)  # 从大到小排序硬币面额
    count = 0
    for coin in coins:
        while amount >= coin:
            amount -= coin
            count += 1
        if amount == 0:
            break
            
    return count if amount == 0 else -1  # 如果无法凑出总金额，返回-1

# 示例输入
coins = [1, 2, 5]
amount = 11

# 调用函数
minCoins = coinChange(coins, amount)
print("Minimum Coins Needed:", minCoins)