曲靖市网站建设_网站建设公司_前端工程师_seo优化

贪心算法是一种在每一步选择中都采取当前状态下最优选择的算法策略，期望通过局部最优解达到全局最优解。

🎯 贪心算法的核心思想

基本概念

贪心算法在每个决策点都做出在当前看来最好的选择，不考虑未来后果。这种"短视"的策略在某些情况下能得到全局最优解。

贪心算法三要素

class GreedyAlgorithm: def __init__(self): pass def greedy_framework(self, problem): """ 贪心算法通用框架 1. 确定候选集合 2. 确定贪心选择策略 3. 证明贪心选择的正确性 4. 求解最优子结构 """ solution = [] candidates = self.get_candidates(problem) while candidates and not self.is_solution_complete(solution, problem): # 贪心选择：选择当前最优的候选 best_candidate = self.select_best_candidate(candidates, solution, problem) solution.append(best_candidate) candidates = self.update_candidates(candidates, best_candidate, problem) return solution def get_candidates(self, problem): """获取候选集合""" pass def select_best_candidate(self, candidates, solution, problem): """选择最优候选（贪心策略）""" pass def update_candidates(self, candidates, chosen, problem): """更新候选集合""" pass def is_solution_complete(self, solution, problem): """检查是否得到完整解""" pass

🔍 经典贪心算法案例

1.活动选择问题​ (Activity Selection)

问题描述：给定一组活动，每个活动有开始时间和结束时间，选择最多的互不重叠的活动。

def activity_selection(activities): """ 活动选择问题 - 经典贪心算法 贪心策略：每次选择结束时间最早且与已选活动不冲突的活动 """ # 按结束时间排序 activities.sort(key=lambda x: x[1]) # x[1]是结束时间 selected = [] last_end_time = -1 for activity in activities: start, end = activity if start >= last_end_time: # 不冲突 selected.append(activity) last_end_time = end return selected # 测试示例 activities = [ (1, 4), (3, 5), (0, 6), (5, 7), (3, 8), (5, 9), (6, 10), (8, 11), (8, 12), (2, 13), (12, 14) ] selected = activity_selection(activities) print("选择的活动:", selected) print("最多可选择", len(selected), "个活动")

2.霍夫曼编码​ (Huffman Coding)

问题描述：构建最优前缀编码，使总编码长度最小。

import heapq class HuffmanNode: def __init__(self, char=None, freq=0): self.char = char self.freq = freq self.left = None self.right = None def __lt__(self, other): return self.freq < other.freq def huffman_encoding(freq_dict): """ 霍夫曼编码 - 贪心构建最优前缀码 贪心策略：每次合并频率最小的两棵树 """ # 创建最小堆 heap = [] for char, freq in freq_dict.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) merged.left = left merged.right = right heapq.heappush(heap, merged) return heap[0] if heap else None def generate_codes(root, current_code="", codes={}): """生成霍夫曼编码""" if root is None: return if root.char is not None: codes[root.char] = current_code return generate_codes(root.left, current_code + "0", codes) generate_codes(root.right, current_code + "1", codes) return codes # 测试示例 freq_dict = {'a': 5, 'b': 9, 'c': 12, 'd': 13, 'e': 16, 'f': 45} huffman_tree = huffman_encoding(freq_dict) codes = generate_codes(huffman_tree) print("霍夫曼编码:") for char, code in sorted(codes.items()): print(f"'{char}': {code}")

3.分数背包问题​ (Fractional Knapsack)

问题描述：物品可以分割，在容量限制下最大化价值。

def fractional_knapsack(items, capacity): """ 分数背包问题 - 贪心算法 贪心策略：按价值密度（价值/重量）降序排列，优先装价值密度高的 """ # 计算价值密度并排序 items_with_ratio = [(value / weight, value, weight, idx) for idx, (value, weight) in enumerate(items)] items_with_ratio.sort(reverse=True) # 按价值密度降序 total_value = 0 remaining_capacity = capacity taken = [0] * len(items) for ratio, value, weight, idx in items_with_ratio: if remaining_capacity >= weight: # 可以拿整个物品 taken[idx] = 1 total_value += value remaining_capacity -= weight else: # 只能拿部分物品 taken[idx] = remaining_capacity / weight total_value += value * (remaining_capacity / weight) break return total_value, taken # 测试示例 items = [(60, 10), (100, 20), (120, 30)] # (价值, 重量) capacity = 50 max_value, taken = fractional_knapsack(items, capacity) print(f"最大价值: {max_value}") print("选取方案:", taken)

4.区间覆盖问题​ (Interval Covering)

问题描述：用最少的点覆盖所有区间。

def min_points_to_cover(intervals): """ 最小点覆盖 - 贪心算法 贪心策略：按右端点排序，每次选择右端点作为覆盖点 """ if not intervals: return 0, [] # 按右端点排序 intervals.sort(key=lambda x: x[1]) points = [] current_point = -float('inf') for interval in intervals: start, end = interval if start > current_point: # 当前点不能覆盖这个区间 current_point = end # 在新区间的右端点放一个点 points.append(current_point) return len(points), points # 测试示例 intervals = [[1, 4], [2, 5], [7, 9], [6, 10]] num_points, points = min_points_to_cover(intervals) print(f"最少需要 {num_points} 个点: {points}")

⚖️ 贪心算法的正确性证明

贪心选择性质

要证明贪心选择不会导致丢失最优解。

def prove_greedy_choice(): """ 贪心选择性质的证明思路： 1. 存在一个最优解包含贪心选择 2. 贪心选择与最优解的第一个选择相同 3. 原问题简化为更小的子问题 """ proof_steps = [ "步骤1: 假设存在一个最优解S", "步骤2: 将S的第一个选择与贪心选择g交换", "步骤3: 证明交换后的解仍然是最优的", "步骤4: 归纳地证明后续选择也保持最优性" ] return proof_steps

最优子结构

问题的最优解包含子问题的最优解。

🚫 贪心算法不适用的情况

反例：0-1背包问题

def knapsack_01_greedy(items, capacity): """ 0-1背包问题的贪心解法（不正确！） 说明：贪心策略在这里不能得到最优解 """ # 按价值密度排序 items_with_ratio = [(value / weight, value, weight, idx) for idx, (value, weight) in enumerate(items)] items_with_ratio.sort(reverse=True) total_value = 0 remaining_capacity = capacity taken = [0] * len(items) for ratio, value, weight, idx in items_with_ratio: if remaining_capacity >= weight: taken[idx] = 1 total_value += value remaining_capacity -= weight return total_value, taken # 对比：正确的动态规划解法 def knapsack_01_dp(items, capacity): """0-1背包问题的动态规划解法""" n = len(items) dp = [[0] * (capacity + 1) for _ in range(n + 1)] for i in range(1, n + 1): value, weight = items[i-1] for w in range(1, capacity + 1): if weight <= w: dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight] + value) else: dp[i][w] = dp[i-1][w] return dp[n][capacity] # 测试对比 items = [(60, 10), (100, 20), (120, 30)] capacity = 50 greedy_value, _ = knapsack_01_greedy(items, capacity) dp_value = knapsack_01_dp(items, capacity) print(f"贪心解法: {greedy_value}") print(f"动态规划: {dp_value}") print("贪心解法不等于最优解！")

🎮 实际应用案例

1.任务调度问题

def task_scheduling(tasks): """ 任务调度：每个任务有截止时间和惩罚 贪心策略：按惩罚降序排列，尽量安排截止时间早的任务 """ # 按惩罚降序排列 tasks.sort(key=lambda x: x[2], reverse=True) # x[2]是惩罚 max_deadline = max(task[1] for task in tasks) schedule = [-1] * (max_deadline + 1) # 时间表 total_penalty = 0 for task in tasks: deadline, duration, penalty = task # 从截止时间往前找空闲时段 for time_slot in range(min(deadline, max_deadline), 0, -1): if schedule[time_slot] == -1 and time_slot >= duration: # 可以安排这个任务 for t in range(time_slot - duration + 1, time_slot + 1): schedule[t] = task[0] # 标记时间段被占用 break else: # 无法安排，累加惩罚 total_penalty += penalty return schedule, total_penalty # 测试示例 tasks = [ ('A', 2, 100), # (任务名, 截止时间, 惩罚) ('B', 1, 19), ('C', 2, 27), ('D', 1, 25), ('E', 3, 15) ] schedule, penalty = task_scheduling(tasks) print(f"总惩罚: {penalty}") print("时间安排:", schedule)

2.硬币找零问题

def coin_change_greedy(coins, amount): """ 硬币找零 - 贪心算法 注意：这只在特定硬币系统下有效（如美国硬币系统） """ coins.sort(reverse=True) # 按面额降序 result = [] remaining = amount for coin in coins: while remaining >= coin: result.append(coin) remaining -= coin return result if remaining == 0 else None # 测试（美国硬币系统有效） us_coins = [25, 10, 5, 1] amount = 67 change = coin_change_greedy(us_coins, amount) print(f"找零 {amount} 美分: {change}") # 反例：某些硬币系统贪心无效 weird_coins = [25, 15, 1] amount = 30 change = coin_change_greedy(weird_coins, amount) print(f"找零 {amount} (特殊硬币): {change} (可能不是最优)")

📊 贪心算法总结

适用场景

算法模板

def greedy_template(problem): """ 贪心算法通用模板 """ # 1. 问题建模 candidates = initialize_candidates(problem) # 2. 定义贪心策略 def greedy_choice(candidates, current_solution): # 根据具体问题实现贪心选择逻辑 pass # 3. 迭代求解 solution = [] while candidates and not is_complete(solution, problem): # 贪心选择 best = greedy_choice(candidates, solution) solution.append(best) # 更新候选集 candidates = update_candidates(candidates, best, problem) return solution

优缺点分析

优点：

• ✅ 算法简单直观

• ✅ 时间复杂度通常较低

• ✅ 空间效率高

• ✅ 易于实现和调试

缺点：

• ❌ 不一定得到全局最优解

• ❌ 需要严格的数学证明

• ❌ 适用范围有限

• ❌ 错误的贪心策略会导致很差的结果

🎯 学习建议

1. 理解贪心本质：局部最优 ≠ 全局最优

2. 掌握证明方法：学会证明贪心选择性质

3. 识别适用场景：判断问题是否具有贪心选择性质

4. 对比其他方法：与动态规划、回溯法等对比

5. 大量练习：通过经典题目加深理解

贪心算法虽然简单，但在合适的场景下能带来非常高效的解决方案。关键是识别出哪些问题适合用贪心策略！