一、贪心算法核心思想

贪心算法（Greedy Algorithm）是一种在每一步选择中都采取当前状态下最优或最有利的选择，从而希望导致结果是全局最优的算法策略。

贪心算法的基本特征：

• 局部最优选择：每一步都选择当前看起来最好的选项

• 不可回溯性：一旦做出选择，就不再重新考虑

• 高效性：通常时间复杂度较低，实现简单

二、贪心算法的优缺点分析

 优点：

1. 时间复杂度低：通常是O(n log n)或O(n)

2. 实现简单直观：代码通常简短易懂

3. 空间效率高：多数情况下只需要常数额外空间

4. 实时性好：适合在线处理和实时系统

 缺点：

1. 不保证全局最优：局部最优不一定导致全局最优

2. 适用范围有限：只适用于具有贪心选择性质的问题

3. 证明困难：需要严谨的数学证明

4. 对输入敏感：不同输入可能需要不同的贪心策略

三、贪心算法的证明方法

方法一：反证法 - 例1：部分背包问题

反证法证明思路：
1、假设存在最优解A与贪心解B不同
2、找到第一个选择不同的物品，证明贪心选择不会更差
3、逐步调整，最终证明贪心解B至少与A一样好

问题：n个物品，重量w和价值v，背包容量C，可分割物品

# 读取物品数量n和背包容量t
n, t = map(int, input().split())

# 存储物品信息：每个物品是(质量, 价值, 单位价值)
golds = []
for i in range(n):
    m, v = map(int, input().split())  # 读取物品的质量和价值
    p = v / m  # 计算单位价值（价值/质量比）
    golds.append((m, v, p))  # 将物品信息添加到列表

# 按照单位价值从高到低排序（贪心策略：优先选择性价比高的物品）
golds.sort(key=lambda x: x[2], reverse=True)

# 初始化总价值和剩余容量
total_value = 0.0
remaining = t  # 背包剩余容量

# 遍历排序后的物品
for m, v, p in golds:
    if remaining <= 0:  # 如果背包已满，结束
        break
    
    if m <= remaining:  # 如果当前物品可以完整放入背包
        total_value += v  # 获得完整价值
        remaining -= m   # 减少剩余容量
    else:  # 如果只能放入部分
        total_value += p * remaining  # 按比例获得部分价值
        remaining = 0  # 背包容量用完

# 输出结果，保留两位小数
print(f'{total_value:.2f}')

方法二：归纳法 - 例2：活动选择问题（凌乱的yyy）

归纳法证明：
1、基础：只有一个活动时，贪心选择最优
2、归纳：假设前k个活动的选择是最优的
3、递推：第k+1个活动选择结束最早的，证明仍然最优

问题：选择最大数量的互不重叠活动

# 读取活动数量
n = int(input())

# 存储活动信息：每个活动是(开始时间, 结束时间)
contest = []
for i in range(n):
    a, b = map(int, input().split())  # 读取活动的开始时间和结束时间
    contest.append((a, b))  # 将活动添加到列表

# 按照结束时间升序排序
# 贪心策略：优先选择结束时间早的活动，给后面的活动留下更多时间
contest.sort(key=lambda x: x[1])

# 初始化计数和上一个选择的活动的结束时间
count = 0  # 最多能选择的活动数量
last_end = -1  # 上一个选择的活动的结束时间，初始化为-1确保第一个活动可以被选择

# 遍历排序后的活动
for start, end in contest:
    # 如果当前活动的开始时间不早于上一个选择的活动的结束时间
    # 说明两个活动不冲突，可以选择当前活动
    if start >= last_end:
        count += 1  # 选择当前活动
        last_end = end  # 更新上一个选择的活动的结束时间

# 输出最多能选择的活动数量
print(count)

方法三：交换论证法 - 例3：排队接水问题

交换论证证明：
假设最优解中有两个相邻的人i,j，且t_i > t_j，交换i和j的位置，总等待时间不会增加，因此升序排列是最优的。

问题：n个人排队接水，如何安排使总等待时间最小

# 读取排队人数
n = int(input())

# 读取每个人的接水时间
time = list(map(int, input().split()))

# 创建(编号, 时间)的元组列表
times = []
for i in range(n):
    t = time[i]
    times.append((i + 1, t))  # i+1作为编号（从1开始）

# 按照接水时间升序排序，如果时间相同则按编号升序排序
# 贪心策略：让接水时间短的人先接水，可以减少总等待时间
times.sort(key=lambda x: (x[1], x[0]))

# 输出接水顺序（编号）
for i, t in times:
    print(i, end=' ')
print()  # 换行

# 计算总等待时间
waits = 0.0  # 使用浮点数以确保除法精度
for i in range(n):
    wait = 0  # 第i个人的等待时间
    
    # 第i个人需要等待前面所有人的接水时间
    for j in range(i):
        wait += times[j][1]
    
    waits += wait  # 累加到总等待时间

# 计算平均等待时间
waits_mean = waits / n

# 输出结果，保留两位小数
print(f'{waits_mean:.2f}')

四、经典贪心问题详解

例4：分卷子问题（最小合并代价）

问题：合并多堆卷子，每次合并两堆，代价为两堆之和，求最小总代价

import heapq

def min_merge_cost_greedy(volumes):
    """
    分卷子问题贪心解法（哈夫曼树应用）
    贪心策略：总是合并最小的两堆
    
    参数：
        volumes: 各堆卷子的数量列表
    
    返回：
        total_cost: 最小合并总代价
        merge_sequence: 合并顺序记录
    """
    if len(volumes) <= 1:
        return 0, []
    
    # 使用最小堆
    min_heap = volumes[:]
    heapq.heapify(min_heap)
    
    total_cost = 0
    merge_sequence = []
    
    # 贪心合并：每次合并最小的两堆
    while len(min_heap) > 1:
        # 取出最小的两个元素
        first = heapq.heappop(min_heap)
        second = heapq.heappop(min_heap)
        
        # 合并代价
        merge_cost = first + second
        total_cost += merge_cost
        merge_sequence.append((first, second, merge_cost))
        
        # 将合并结果放回堆中
        heapq.heappush(min_heap, merge_cost)
    
    return total_cost, merge_sequence

# 示例使用
volumes = [3, 4, 2, 6, 1]
min_cost, sequence = min_merge_cost_greedy(volumes)
print(f"最小合并代价: {min_cost}")
print(f"合并顺序: {sequence}")

例5：合并果子问题

问题：类似分卷子，但可能有额外约束

import heapq  # 导入堆队列算法模块（最小堆）

# 读取水果数量
n = int(input())
# 读取每个水果的重量，转换为列表
fruits = list(map(int, input().split()))

# 将列表转换为最小堆（堆化）
# 堆是一种特殊的二叉树结构，最小堆的根节点总是最小的元素
heapq.heapify(fruits)  

# 初始化总消耗体力值
total_cost = 0

# 当堆中还有不止一个水果时继续合并
while len(fruits) > 1:
    # 取出堆中最小的两个水果（堆顶元素）
    a = heapq.heappop(fruits)  # 弹出并返回最小元素
    b = heapq.heappop(fruits)  # 弹出并返回次小元素
    
    # 合并这两个水果需要的体力值 = 它们的重量之和
    cost = a + b
    # 累加到总消耗体力值
    total_cost += cost
    
    # 将合并后的新水果（重量为cost）放回堆中
    heapq.heappush(fruits, cost)  # 将新元素推入堆，保持堆性质

# 输出合并所有水果需要的最小总体力值
print(total_cost)

例6：哈夫曼编码问题

问题：给定字符频率，设计最优二进制编码

class HuffmanNode:
    """哈夫曼树节点类"""
    def __init__(self, freq, char=None):
        self.freq = freq      # 频率
        self.char = char      # 字符（叶子节点才有）
        self.left = None      # 左子节点
        self.right = None     # 右子节点
    
    def __lt__(self, other):
        """用于堆比较：按频率比较"""
        return self.freq < other.freq

def build_huffman_tree(freq_dict):
    """
    构建哈夫曼树
    贪心策略：每次合并频率最小的两个节点
    
    参数：
        freq_dict: 字符频率字典 {字符: 频率}
    
    返回：
        root: 哈夫曼树的根节点
    """
    if not freq_dict:
        return None
    
    # 创建叶子节点并加入最小堆
    heap = []
    for char, freq in freq_dict.items():
        node = HuffmanNode(freq, char)
        heapq.heappush(heap, node)
    
    # 贪心构建哈夫曼树
    while len(heap) > 1:
        # 取出频率最小的两个节点
        left = heapq.heappop(heap)
        right = heapq.heappop(heap)
        
        # 创建新内部节点
        merged_freq = left.freq + right.freq
        merged_node = HuffmanNode(merged_freq)
        merged_node.left = left
        merged_node.right = right
        
        # 放回堆中
        heapq.heappush(heap, merged_node)
    
    return heap[0] if heap else None

def generate_huffman_codes(root, current_code="", codes={}):
    """
    生成哈夫曼编码
    
    参数：
        root: 哈夫曼树根节点
        current_code: 当前路径编码
        codes: 存储编码的字典
    
    返回：
        codes: 字符到编码的映射
    """
    if root is None:
        return codes
    
    # 如果是叶子节点，记录编码
    if root.char is not None:
        codes[root.char] = current_code if current_code else "0"
    else:
        # 递归遍历左子树（编码加'0'）
        generate_huffman_codes(root.left, current_code + "0", codes)
        # 递归遍历右子树（编码加'1'）
        generate_huffman_codes(root.right, current_code + "1", codes)
    
    return codes

def calculate_compression_rate(original_text, freq_dict, huffman_codes):
    """
    计算哈夫曼编码的压缩率
    
    参数：
        original_text: 原始文本
        freq_dict: 字符频率
        huffman_codes: 哈夫曼编码
    
    返回：
        compression_rate: 压缩率
    """
    # 原始比特数（假设8-bit ASCII）
    original_bits = len(original_text) * 8 if original_text else 0
    
    # 编码后比特数
    encoded_bits = 0
    for char, freq in freq_dict.items():
        code_length = len(huffman_codes.get(char, ""))
        encoded_bits += freq * code_length
    
    if original_bits == 0:
        return 0
    
    compression_rate = 1 - (encoded_bits / original_bits)
    return compression_rate

# 完整示例
def huffman_coding_example(text):
    """哈夫曼编码完整示例"""
    if not text:
        return None
    
    # 1. 统计字符频率
    freq_dict = {}
    for char in text:
        freq_dict[char] = freq_dict.get(char, 0) + 1
    
    # 2. 构建哈夫曼树
    root = build_huffman_tree(freq_dict)
    
    # 3. 生成编码
    codes = generate_huffman_codes(root)
    
    # 4. 计算压缩率
    compression_rate = calculate_compression_rate(text, freq_dict, codes)
    
    # 5. 编码文本
    encoded_text = ''.join(codes[char] for char in text)
    
    return {
        'frequency': freq_dict,
        'huffman_tree': root,
        'codes': codes,
        'encoded_text': encoded_text,
        'compression_rate': compression_rate,
        'original_length': len(text) * 8,
        'encoded_length': len(encoded_text)
    }

# 使用示例
text = "this is an example for huffman encoding"
result = huffman_coding_example(text)
print(f"字符频率: {result['frequency']}")
print(f"哈夫曼编码: {result['codes']}")
print(f"压缩率: {result['compression_rate']:.2%}")

五、贪心算法的适用条件与判断

适用条件：

1、贪心选择性质 

1）局部最优选择能导致全局最优解

2）可以通过数学证明验证

2、最优子结构

1）问题的最优解包含子问题的最优解 

2）子问题独立且可递归求解

3、无后效性 

1）当前决策不影响后续决策的最优性

2）决策序列的代价可加性

贪心算法选择决策树：

开始
  ↓
问题是否可分解为子问题？ → No → 不适合贪心
  ↓ Yes
子问题是否具有最优子结构？ → No → 考虑动态规划
  ↓ Yes  
能否做出局部最优选择？ → No → 考虑回溯/分支限界
  ↓ Yes
局部最优是否保证全局最优？ → No → 可能需要其他方法
  ↓ Yes
✓ 适合使用贪心算法

六、贪心 vs 动态规划对比

对比维度	贪心算法	动态规划
决策方式	局部最优，不可回溯	考虑所有可能，可回溯
时间复杂度	通常O(n log n)或O(n)	通常O(n²)或更高
空间复杂度	通常O(1)或O(n)	通常O(n²)需要存储状态
解的质量	可能不是全局最优	保证全局最优
适用问题	活动选择、哈夫曼编码、最小生成树	0-1背包、最长公共子序列
实现难度	相对简单	相对复杂

七、贪心算法的实战技巧

技巧1：预处理排序

def greedy_with_sorting(data):
    """大多数贪心算法需要先排序"""
    # 关键：确定正确的排序标准
    sorted_data = sorted(data, key=custom_key_function)
    # ... 贪心处理逻辑

技巧2：使用优先队列

def greedy_with_heap(data):
    """需要频繁获取最小/最大值时使用堆"""
    import heapq
    heapq.heapify(data)
    
    while condition:
        current = heapq.heappop(data)  # 获取当前最优
        # ... 处理逻辑
        heapq.heappush(data, new_item)  # 更新堆

技巧3：边界条件处理

def robust_greedy(data):
    """健壮的贪心算法实现"""
    if not data:  # 空输入处理
        return default_value
    
    # 特殊输入处理
    if len(data) == 1:
        return handle_single_case(data[0])
    
    # 正常贪心逻辑
    try:
        result = greedy_logic(data)
    except Exception as e:
        # 异常处理
        return fallback_solution(data)
    
    return result

八、常见陷阱与避免方法

陷阱1：错误的贪心策略

# 错误示例：0-1背包问题用贪心（单位价值排序）
def wrong_knapsack_greedy(weights, values, capacity):
    items = sorted(zip(weights, values), 
                   key=lambda x: x[1]/x[0], 
                   reverse=True)
    total_value = 0
    for w, v in items:
        if capacity >= w:
            capacity -= w
            total_value += v
    return total_value  # 可能不是最优解！

# 正确：0-1背包应用动态规划

陷阱2：忽略证明

• ❌ 直接实现看似合理的贪心策略

• ✅ 先用数学证明或构造反例验证

陷阱3：过度优化

• ❌ 追求过于复杂的贪心策略

• ✅ 保持简单，必要时用其他算法补充

九、总结与最佳实践

贪心算法是算法工具箱中的重要工具。正确使用时，它能提供高效的解决方案。总结关键点：

1. 先证明后实现：确保问题具有贪心选择性质

2. 从简单开始：先实现基础版本，再优化

3. 充分测试：用边界用例和随机数据测试

4. 保持灵活性：当贪心失败时，考虑动态规划等其他方法

总结：

• 掌握经典的贪心问题模板

• 理解各种证明方法的适用场景

• 在实际问题中积累经验，培养对贪心适用性的直觉

（本文例题来自洛谷）