当前位置：首页 > web >正文

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

web 2025/5/17 6:56:34

文章目录

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

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个案例从简单到复杂，涵盖了贪心算法的多种应用场景，通过学习和实践，读者可深入理解其思想并灵活运用于实际问题。

查看全文

http://www.xdnf.cn/news/6741.html