第十天——贪心算法——深度总结

文章目录

贪心算法深度解析：原理与应用

1. 贪心算法的基本原理

1.1 贪心选择性质

1.2 最优子结构

1.3 贪心算法与动态规划的对比

2. 贪心算法的应用场景

3. 具体应用案例

3.1 分配饼干 (Assign Cookies)

3.2 分糖果 (Candy Distribution)

3.3 种花问题 (Can Place Flowers)

3.4 区间问题 (Non-overlapping Intervals)

3.5 射气球 (Minimum Number of Arrows to Burst Balloons)

3.6 广播台覆盖问题 (Set Covering Problem)

3.7 硬币找零问题 (Coin Change - Greedy Approach)

3.8 股票买卖问题 (Best Time to Buy and Sell Stock II)

3.9 分数背包问题 (Fractional Knapsack)

3.10 字符串分割 (Partition Labels)

3.11 队列重构问题 (Queue Reconstruction by Height)

3.12 非递减数组 (Non-decreasing Array)

3.13 迪克斯特拉算法 (Dijkstra’s Algorithm)

3.14 霍夫曼编码 (Huffman Coding)

4. 总结

---

贪心算法深度解析：原理与应用

贪心算法（Greedy Algorithm）是一种简单而高效的算法设计策略，其核心思想是在每一步决策中选择当前最优解，期望通过一系列局部最优选择最终获得全局最优解。相比动态规划等方法，贪心算法通常更高效，但适用范围有限，需要问题具备特定的性质。本报告将系统介绍贪心算法的原理、应用场景，并通过14个由易到难的案例深入剖析其应用，帮助读者掌握其精髓并在实践中灵活运用。

---

1. 贪心算法的基本原理

1.1 贪心选择性质

贪心选择性质是贪心算法的核心，指每一步的局部最优选择能够逐步构建全局最优解。这种性质要求问题具有“无后效性”，即当前选择不会影响后续决策的正确性。例如，在活动选择问题中，选择结束时间最早的活动不会限制后续选择。

1.2 最优子结构

最优子结构是指问题的最优解由子问题的最优解组成。在贪心算法中，通过不断缩小问题规模，最终能够得到全局最优解。例如，最小生成树问题中，每一步选择的边都会成为最终解的一部分。

1.3 贪心算法与动态规划的对比

• 动态规划：通过记录所有子问题的解来构建全局最优解，时间复杂度较高（如 O(n²) 或更高）。
• 贪心算法：直接选择当前最优解，不回溯，时间复杂度通常较低（如 O(n log n) 或 O(n)）。
• 局限性：贪心算法要求问题满足贪心选择性质，否则可能无法得到最优解。

---

2. 贪心算法的应用场景

贪心算法适用于以下常见领域：

• 调度问题：如活动选择、任务调度。
• 背包问题：如分数背包问题。
• 图论问题：如最小生成树（Kruskal、Prim）、单源最短路径（Dijkstra）。
• 编码与压缩：如霍夫曼编码。
• 资源分配：如分配饼干、种花问题。

这些问题通常具备贪心选择性质和最优子结构，使得局部最优选择能够逐步逼近全局最优解。

---

3. 具体应用案例

以下是14个由易到难的贪心算法应用案例，每个案例包含问题描述、贪心策略、代码实现和分析，代码以 Python 实现并附有注释。

3.1 分配饼干 (Assign Cookies)

问题描述：
有一群孩子和一堆饼干，每个孩子有饥饿度，每个饼干有饱腹度。每个孩子只能吃一个饼干，且饼干饱腹度需不小于孩子饥饿度。求最多有多少孩子能吃饱。

贪心策略：
优先为饥饿度最小的孩子分配刚好能满足的最小饼干，最大化利用饼干资源。

代码实现：

def findContentChildren(children: list[int], cookies: list[int]):children.sort()  # 按饥饿度升序cookies.sort()   # 按饱腹度升序child_i, cookie_i = 0, 0while child_i < len(children) and cookie_i < len(cookies):if children[child_i] <= cookies[cookie_i]:  # 饼干能满足孩子child_i += 1  # 下一个孩子cookie_i += 1  # 下一块饼干return child_i# 示例
print(findContentChildren([1, 2], [1, 2, 3]))  # 输出: 2

分析：
通过对孩子和饼干排序，使用双指针技术从小到大分配，确保饼干资源高效利用。时间复杂度 O(n log n)，空间复杂度 O(1)。

---

3.2 分糖果 (Candy Distribution)

问题描述：
一群孩子站成一排，每个孩子有评分，评分高的孩子需比相邻孩子多糖果，每人至少一个，求最少糖果数。

贪心策略：
两次遍历，从左到右和从右到左调整糖果数，满足相邻约束。

代码实现：

def candy(ratings: list[int]):n = len(ratings)candies = [1] * n  # 初始每人一个for i in range(1, n):  # 从左到右if ratings[i] > ratings[i - 1]:candies[i] = candies[i - 1] + 1for i in range(n - 1, 0, -1):  # 从右到左if ratings[i] < ratings[i - 1]:candies[i - 1] = max(candies[i - 1], candies[i] + 1)return sum(candies)# 示例
print(candy([1, 0, 2]))  # 输出: 5

分析：
两次遍历确保评分高的孩子糖果多，最小化总糖果数。时间复杂度 O(n)，空间复杂度 O(n)。

---

3.3 种花问题 (Can Place Flowers)

问题描述：
给定花坛数组 flowerbed（0 表示空，1 表示有花）和整数 n，判断能否种下 n 朵花，新种的花不能相邻。

贪心策略：
尽可能早地在满足条件的位置种花，确保左右两侧为空（或在边界）。

代码实现：

def canPlaceFlowers(flowerbed, n):count = 0length = len(flowerbed)for i in range(length):if flowerbed[i] == 0:left_empty = (i == 0) or (flowerbed[i - 1] == 0)right_empty = (i == length - 1) or (flowerbed[i + 1] == 0)if left_empty and right_empty:flowerbed[i] = 1  # 种花count += 1if count >= n:return Truereturn count >= n# 示例
print(canPlaceFlowers([1, 0, 0, 0, 1], 1))  # 输出: True

分析：
通过线性扫描并在满足条件时种花，贪心策略最大化种植数量。时间复杂度 O(n)，空间复杂度 O(1)。

---

3.4 区间问题 (Non-overlapping Intervals)

问题描述：
给定多个区间，计算让它们互不重叠（起止相连不算重叠）所需移除的最少区间数。

贪心策略：
按结束时间排序，优先保留结束最早的区间，为后续区间留出更多空间。

代码实现：

def eraseOverlapIntervals(intervals: list[list[int]]):intervals.sort(key=lambda x: x[1])  # 按结束时间排序removed, prev_end = 0, intervals[0][1]for i in range(1, len(intervals)):if prev_end > intervals[i][0]:  # 重叠，移除当前区间removed += 1else:prev_end = intervals[i][1]  # 更新结束时间return removed# 示例
print(eraseOverlapIntervals([[1, 2], [2, 4], [1, 3]]))  # 输出: 1

分析：
按结束时间排序后，选择不重叠的区间，贪心策略最小化移除数量。时间复杂度 O(n log n)，空间复杂度 O(1)。

---

3.5 射气球 (Minimum Number of Arrows to Burst Balloons)

问题描述：
给定气球的水平直径区间 points，求最少需要多少支箭射爆所有气球。

贪心策略：
按结束位置排序，在最早结束的气球右端点射箭，覆盖尽可能多的气球。

代码实现：

def findMinArrowShots(points):if not points:return 0points.sort(key=lambda x: x[1])  # 按结束位置排序count = 1last_shot = points[0][1]for start, end in points:if start > last_shot:  # 不重叠，需新箭count += 1last_shot = endreturn count# 示例
print(findMinArrowShots([[10, 16], [2, 8], [1, 6], [7, 12]]))  # 输出: 2

分析：
通过在重叠区间的公共点射箭，贪心策略最小化箭数。时间复杂度 O(n log n)，空间复杂度 O(1)。

---

3.6 广播台覆盖问题 (Set Covering Problem)

问题描述：
给定需要覆盖的州和广播台覆盖范围，求覆盖所有州的最小广播台集合。

贪心策略：
每次选择覆盖最多未覆盖州的广播台。

代码实现：

states_needed = set(["mt", "wa", "or", "id", "nv", "ut", "ca", "az"])
stations = {"kone": set(["id", "nv", "ut"]),"ktwo": set(["wa", "id", "mt"]),"kthree": set(["or", "nv", "ca"]),"kfour": set(["nv", "ut"]),"kfive": set(["ca", "az"])
}final_stations = set()
while states_needed:best_station = Nonestates_covered = set()for station, states in stations.items():covered = states_needed & statesif len(covered) > len(states_covered):best_station = stationstates_covered = coveredstates_needed -= states_coveredfinal_stations.add(best_station)# 示例
print(final_stations)  # 输出: {'kone', 'ktwo', 'kthree', 'kfive'}

分析：
通过贪心选择覆盖最多新州的广播台，近似求解最小覆盖问题。时间复杂度 O(nm)，n 为广播台数，m 为州数。

---

3.7 硬币找零问题 (Coin Change - Greedy Approach)

问题描述：
给定硬币面值 coins 和金额 amt，求凑出 amt 的最少硬币数，无法凑出返回 -1。

贪心策略：
优先使用面值最大的硬币。

代码实现：

def coin_change_greedy(coins: list[int], amt: int) -> int:coins.sort(reverse=True)  # 按面值降序count = 0for coin in coins:while amt >= coin:amt -= coincount += 1return count if amt == 0 else -1# 示例
print(coin_change_greedy([1, 3, 4], 6))  # 输出: 2 (但注意：并非总是最优)

分析：
贪心策略在特定面值组合下有效，但如 [1, 3, 4] 和金额 6，贪心得 3（4+1+1），而最优为 2（3+3）。时间复杂度 O(n + k)，k 为金额除以最小面值的次数。

---

3.8 股票买卖问题 (Best Time to Buy and Sell Stock II)

问题描述：
给定每日股票价格，可多次买卖但不能同时持有多支股票，求最大利润。

贪心策略：
在每个价格上涨期间买入并卖出，累加所有正收益。

代码实现：

def maxProfit(prices):max_profit = 0for i in range(1, len(prices)):if prices[i] > prices[i - 1]:  # 价格上涨max_profit += prices[i] - prices[i - 1]  # 累加利润return max_profit# 示例
print(maxProfit([7, 1, 5, 3, 6, 4]))  # 输出: 7

分析：
通过捕获所有正价格差，贪心策略确保最大利润。时间复杂度 O(n)，空间复杂度 O(1)。

---

3.9 分数背包问题 (Fractional Knapsack)

问题描述：
给定物品重量 wgt、价值 val 和背包容量 cap，可选择物品的一部分，求最大价值。

贪心策略：
按单位重量价值排序，优先选择单位价值最高的物品。

代码实现：

class Item:def __init__(self, w: int, v: int):self.w = wself.v = vdef fractional_knapsack(wgt: list[int], val: list[int], cap: int) -> int:items = [Item(w, v) for w, v in zip(wgt, val)]items.sort(key=lambda x: x.v / x.w, reverse=True)  # 按单位价值降序res = 0for item in items:if item.w <= cap:  # 整件放入res += item.vcap -= item.welse:  # 部分放入res += (item.v / item.w) * capbreakreturn res# 示例
print(fractional_knapsack([10, 20, 30], [60, 100, 120], 50))  # 输出: 240

分析：
通过优先选择高单位价值的物品，贪心策略最大化背包价值。时间复杂度 O(n log n)，空间复杂度 O(n)。

---

3.10 字符串分割 (Partition Labels)

问题描述：
将字符串 s 分割成尽可能多的部分，每个字母只出现在一个部分中。

贪心策略：
记录每个字母的最后位置，扩展当前部分至其中字母的最远位置。

代码实现：

def partition_labels(s):last_occurrence = {char: idx for idx, char in enumerate(s)}  # 字母最后位置start = end = 0result = []for i, char in enumerate(s):end = max(end, last_occurrence[char])  # 更新当前部分结束位置if i == end:  # 当前部分结束result.append(end - start + 1)start = end + 1return result# 示例
print(partition_labels("ababcbacadefegdehijhklij"))  # 输出: [9, 7, 8]

分析：
通过跟踪字母的最远位置，贪心策略最大化分割数量。时间复杂度 O(n)，空间复杂度 O(k)（k 为字符集大小）。

---

3.11 队列重构问题 (Queue Reconstruction by Height)

问题描述：
给定人群数组 people，每个元素为 [h, k]（身高 h，前面有 k 个身高≥h 的人），重构队列。

贪心策略：
按身高降序、k 升序排序，再按 k 值插入。

代码实现：

def reconstructQueue(people):people.sort(key=lambda x: (-x[0], x[1]))  # 身高降序，k 升序queue = []for p in people:queue.insert(p[1], p)  # 插入到 k 位置return queue# 示例
print(reconstructQueue([[7, 0], [4, 4], [7, 1], [5, 0], [6, 1], [5, 2]]))  
# 输出: [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]

分析：
先安排高个子再插入矮个子，确保 k 值正确。时间复杂度 O(n²)，空间复杂度 O(n)。

---

3.12 非递减数组 (Non-decreasing Array)

问题描述：
判断数组是否可通过最多修改一个元素变为非递减数组。

贪心策略：
遇到逆序时，优先调整当前元素以保持单调性。

代码实现：

def checkPossibility(nums):corrections = 0for i in range(len(nums) - 1):if nums[i] > nums[i + 1]:if i == 0 or nums[i - 1] <= nums[i + 1]:nums[i] = nums[i + 1]  # 降低当前值else:nums[i + 1] = nums[i]  # 提高后值corrections += 1if corrections > 1:return Falsereturn True# 示例
print(checkPossibility([3, 4, 2, 3]))  # 输出: False

分析：
通过局部调整，贪心策略以最小代价维持非递减性。时间复杂度 O(n)，空间复杂度 O(1)。

---

3.13 迪克斯特拉算法 (Dijkstra’s Algorithm)

问题描述：
在带权有向图中，求从源点到所有顶点的最短路径。

贪心策略：
每次选择当前距离最小的顶点，更新邻接顶点距离。

代码实现：

graph = {"start": {"a": 6, "b": 2},"a": {"fin": 1},"b": {"a": 3, "fin": 5},"fin": {}
}
infinity = float("inf")
costs = {"a": 6, "b": 2, "fin": infinity}
parents = {"a": "start", "b": "start", "fin": None}
processed = []def find_lowest_cost_node(costs):lowest_cost = infinitylowest_cost_node = Nonefor node in costs:cost = costs[node]if cost < lowest_cost and node not in processed:lowest_cost = costlowest_cost_node = nodereturn lowest_cost_nodenode = find_lowest_cost_node(costs)
while node is not None:cost = costs[node]neighbors = graph[node]for n in neighbors.keys():new_cost = cost + neighbors[n]if costs[n] > new_cost:costs[n] = new_costparents[n] = nodeprocessed.append(node)node = find_lowest_cost_node(costs)# 示例
print(costs)  # 输出: {'a': 5, 'b': 2, 'fin': 6}

分析：
通过贪心选择最小距离顶点，适用于无负权图。时间复杂度 O(V²)，使用堆可优化至 O(E + V log V)。

---

3.14 霍夫曼编码 (Huffman Coding)

问题描述：
构建最优前缀编码，实现数据压缩。

贪心策略：
每次合并频率最低的两个节点，构建霍夫曼树。

代码实现：

import heapq
from collections import defaultdictclass HuffmanNode:def __init__(self, char=None, freq=0, left=None, right=None):self.char = charself.freq = freqself.left = leftself.right = rightdef __lt__(self, other):return self.freq < other.freqdef build_frequency_table(text):frequency = defaultdict(int)for char in text:frequency[char] += 1return frequencydef build_huffman_tree(frequency):heap = []for char, freq in frequency.items():heapq.heappush(heap, HuffmanNode(char, freq))while len(heap) > 1:left = heapq.heappop(heap)right = heapq.heappop(heap)merged = HuffmanNode(freq=left.freq + right.freq, left=left, right=right)heapq.heappush(heap, merged)return heapq.heappop(heap)def build_code_dict(root, current_code, code_dict):if root is None:returnif root.char is not None:code_dict[root.char] = current_codereturnbuild_code_dict(root.left, current_code + '0', code_dict)build_code_dict(root.right, current_code + '1', code_dict)def huffman_encoding(text):if not text:return {}, Nonefrequency = build_frequency_table(text)huffman_tree = build_huffman_tree(frequency)code_dict = {}build_code_dict(huffman_tree, '', code_dict)encoded_text = ''.join(code_dict[char] for char in text)return encoded_text, code_dict# 示例
text = "huffman"
encoded_text, code_dict = huffman_encoding(text)
print(f"编码字典: {code_dict}")
print(f"编码结果: {encoded_text}")

分析：
通过贪心合并低频节点，确保高频字符编码短，优化压缩率。时间复杂度 O(n log n)，空间复杂度 O(n)。

---

4. 总结

贪心算法通过局部最优选择逼近全局最优解，适用于具备贪心选择性质和最优子结构的问题。其高效性和简洁性使其在调度、图论、资源分配等领域大放异彩。然而，其局限性在于并非所有问题都适用，使用前需验证问题性质。上述14个案例从简单到复杂，涵盖了贪心算法的多种应用场景，通过学习和实践，读者可深入理解其思想并灵活运用于实际问题。