贪心算法（Greedy Algorithm）是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法策略 [ref_1][ref_2][ref_3][ref_4][ref_6]。它并不保证总能得到全局最优解，但对于许多问题（特别是具有“贪心选择性质”和“最优子结构”的问题）能产生最优解，且通常高效简单。在Python中实现贪心算法的核心步骤通常包括：**对输入数据进行排序**，然后基于排序结果进行贪心选择。下面将结合具体问题，展示贪心算法中排序的Python实现。 ### 1. 基于排序的贪心算法通用模式 大多数贪心算法遵循以下模式，其中排序是关键步骤： ```python def greedy_algorithm(data): """ 贪心算法通用模板 """ # 1. 根据某种贪心策略对数据进行排序 sorted_data = sorted(data, key=lambda x: x['some_criterion'], reverse=True) # 例如按单位价值降序 result = [] total_gain = 0 resource_constraint = 100 # 例如背包容量、时间限制等 # 2. 遍历排序后的数据，进行贪心选择 for item in sorted_data: if can_choose(item, resource_constraint): # 判断是否满足约束条件 result.append(item) total_gain += item['gain'] resource_constraint -= item['cost'] # 更新剩余资源 return result, total_gain ``` ### 2. 具体问题示例与代码实现 #### 示例1：完全背包问题（物品可分割） **问题**：给定背包容量`capacity`和一系列物品（重量`weight`，价值`value`），物品可以任意分割，求如何装包使总价值最大。 **贪心策略**：按**单位价值（价值/重量）** 降序排序，优先装入单位价值高的物品 [ref_1][ref_2][ref_5]。 ```python def fractional_knapsack(capacity, weights, values): """ 解决可分割背包问题的贪心算法 """ # 计算每个物品的单位价值，并存储为(单位价值, 重量, 价值)的元组列表 items = [(values[i] / weights[i], weights[i], values[i]) for i in range(len(weights))] # 关键步骤：按单位价值降序排序 items.sort(key=lambda x: x[0], reverse=True) total_value = 0.0 remaining_capacity = capacity for unit_value, weight, value in items: if remaining_capacity >= weight: # 如果背包容量足够，装入整个物品 total_value += value remaining_capacity -= weight else: # 如果容量不足，装入物品的一部分 total_value += unit_value * remaining_capacity break # 背包已满 return total_value # 示例输入与运行 capacity = 50 weights = [10, 20, 30] values = [60, 100, 120] max_value = fractional_knapsack(capacity, weights, values) print(f"背包能装的最大价值为: {max_value}") # 输出: 背包能装的最大价值为: 240.0 ``` * **排序作用**：通过`items.sort(key=lambda x: x[0], reverse=True)`，确保了算法总是优先考虑“性价比”最高的物品，这是获得全局最优解的关键 [ref_1][ref_2]。 #### 示例2：活动安排问题（区间调度） **问题**：给定一系列活动的开始和结束时间`[start, end]`，求在同一个场地不冲突的情况下最多能安排多少个活动。 **贪心策略**：按**活动结束时间**升序排序，优先选择结束早的活动，为后续活动留下更多时间 [ref_3]。 ```python def activity_selection(activities): """ 解决活动安排问题的贪心算法 activities: 列表，每个元素为(start_time, end_time)的元组 """ # 关键步骤：按结束时间升序排序 activities.sort(key=lambda x: x[1]) selected = [] last_end_time = 0 for start, end in activities: if start >= last_end_time: # 如果当前活动开始时间不早于上一个选中活动的结束时间，则选择它 selected.append((start, end)) last_end_time = end return selected # 示例输入与运行 activities = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11), (8, 12), (2, 14), (12, 16)] result = activity_selection(activities) print(f"最多可以安排 {len(result)} 个活动，具体安排为: {result}") # 输出: 最多可以安排 4 个活动，具体安排为: [(1, 4), (5, 7), (8, 11), (12, 16)] ``` * **排序作用**：`activities.sort(key=lambda x: x[1])`保证了算法每次都能选择最早结束且兼容的活动，从而最大化活动数量 [ref_3]。 #### 示例3：任务排序问题（利润与截止时间） **问题**：有`n`个任务，每个任务有利润`profit`和截止时间`deadline`，每个任务耗时1单位时间，求在截止时间前能完成的任务的最大总利润。 **贪心策略**：按**利润**降序排序，优先安排利润高的任务，同时尽量将其安排在靠近其截止时间的位置 [ref_4]。 ```python def task_scheduling(tasks): """ 解决带截止时间的任务调度问题的贪心算法 tasks: 列表，每个元素为(profit, deadline)的元组 """ # 关键步骤1：按利润降序排序 tasks.sort(key=lambda x: x[0], reverse=True) max_deadline = max(task[1] for task in tasks) # 初始化时间槽，False表示该时间槽空闲 time_slots = [False] * (max_deadline + 1) total_profit = 0 scheduled_tasks = [] for profit, deadline in tasks: # 从该任务的截止时间开始向前查找空闲时间槽 for t in range(deadline, 0, -1): if not time_slots[t]: time_slots[t] = True total_profit += profit scheduled_tasks.append((profit, deadline, t)) break return total_profit, scheduled_tasks # 示例输入与运行 tasks = [(100, 2), (50, 1), (20, 2), (30, 1)] max_profit, schedule = task_scheduling(tasks) print(f"最大总利润为: {max_profit}") print(f"任务安排详情 (利润, 截止时间, 执行时间): {schedule}") # 输出: 最大总利润为: 180 # 任务安排详情 (利润, 截止时间, 执行时间): [(100, 2, 2), (50, 1, 1), (30, 1, 0), (20, 2, 0)] # 注意：时间槽0通常表示一个虚拟位置，实际可能从1开始计数。 ``` * **排序作用**：`tasks.sort(key=lambda x: x[0], reverse=True)`确保了算法总是先尝试安排利润最高的任务，这是实现利润最大化的基础 [ref_4]。 #### 示例4：Kruskal算法求最小生成树（图论） **问题**：给定一个带权无向图，求连接所有顶点的最小权值和的边集合（最小生成树）。 **贪心策略**：将所有边按**权值**升序排序，从小到大选择边，如果加入该边不会形成环，则加入生成树 [ref_6]。 ```python class UnionFind: """并查集，用于检测环""" def __init__(self, n): self.parent = list(range(n)) self.rank = [0] * n def find(self, x): if self.parent[x] != x: self.parent[x] = self.find(self.parent[x]) return self.parent[x] def union(self, x, y): rootX = self.find(x) rootY = self.find(y) if rootX != rootY: if self.rank[rootX] < self.rank[rootY]: self.parent[rootX] = rootY elif self.rank[rootX] > self.rank[rootY]: self.parent[rootY] = rootX else: self.parent[rootY] = rootX self.rank[rootX] += 1 return True return False def kruskal(n, edges): """ 使用Kruskal算法寻找最小生成树 n: 顶点数 edges: 列表，每个元素为(u, v, weight)的元组 """ # 关键步骤：按边权值升序排序 edges.sort(key=lambda x: x[2]) uf = UnionFind(n) mst_edges = [] total_weight = 0 for u, v, w in edges: if uf.union(u, v): # 如果加入此边不形成环 mst_edges.append((u, v, w)) total_weight += w if len(mst_edges) == n - 1: # 生成树已有n-1条边，提前结束 break return total_weight, mst_edges # 示例输入与运行 n = 4 edges = [(0, 1, 10), (0, 2, 6), (0, 3, 5), (1, 3, 15), (2, 3, 4)] min_weight, mst = kruskal(n, edges) print(f"最小生成树的总权值为: {min_weight}") print(f"构成最小生成树的边为: {mst}") # 输出: 最小生成树的总权值为: 19 # 构成最小生成树的边为: [(2, 3, 4), (0, 3, 5), (0, 1, 10)] ``` * **排序作用**：`edges.sort(key=lambda x: x[2])`是Kruskal算法的核心，它保证了每次考虑的边都是当前未选择边中权值最小的，通过并查集避免环后，最终得到的就是全局最小生成树 [ref_6]。 ### 3. 贪心算法中排序策略总结 下表对比了上述不同问题中排序所依据的“贪心准则”： | 问题 | 排序依据（贪心准则） | 排序目的 | 能否得到全局最优解 | | :--- | :--- | :--- | :--- | | **完全背包（可分割）** | 单位价值（价值/重量）降序 | 优先装入“性价比”最高的物品 | **能** | | **活动安排** | 活动结束时间升序 | 优先选择结束早的活动，腾出更多时间 | **能** | | **任务排序** | 任务利润降序 | 优先安排利润高的任务 | **能**（需配合时间槽分配） | | **Kruskal算法** | 边权值升序 | 优先选择权值最小的安全边 | **能** | ### 4. 关键注意事项 1. **贪心算法的局限性**：贪心算法并非万能。例如，在经典的**0/1背包问题**（物品不可分割）中，使用按单位价值排序的贪心策略**不能保证**得到全局最优解，此时通常需要动态规划 [ref_5]。 2. **排序复杂度**：排序通常是贪心算法中时间复杂度最高的部分，一般为 O(n log n)，其中n为数据项数量。后续的贪心选择过程通常是 O(n)。 3. **Python实现技巧**： * 使用`sorted()`函数返回新列表，使用`list.sort()`方法进行原地排序。 * `key`参数是定义排序规则的核心，通常是一个lambda函数，用于提取排序依据的字段。 * `reverse`参数控制升序（False）或降序（True）。 总之，在Python中实现基于贪心算法的排序，关键是准确识别问题的**贪心选择性质**，并据此定义排序的`key`函数。正确的排序是贪心算法高效且（对于适用问题）获得最优解的基础 [ref_1][ref_2][ref_3][ref_4][ref_6]。