贪心算法实战陷阱，看似简单却坑杀无数开发者的4类问题（附避坑指南）

def greedy_activity_selector(activities):
    # 按开始时间排序
    activities.sort(key=lambda x: x[0])
    selected = []
    last_end = float('-inf')
    
    for start, end in activities:
        if start >= last_end:
            selected.append((start, end))
            last_end = end
    
    return selected

# 测试数据
activities = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11)]
print("错误策略选择结果:", greedy_activity_selector(activities))

错误策略选择结果: [(0, 6), (6, 10)]

def correct_activity_selector(activities):
    activities.sort(key=lambda x: x[1])  # 按结束时间排序
    selected = []
    last_end = float('-inf')
    
    for start, end in activities:
        if start >= last_end:
            selected.append((start, end))
            last_end = end
    
    return selected

print("正确策略选择结果:", correct_activity_selector(activities))

正确策略选择结果: [(1, 4), (5, 7), (8, 11)]

flowchart TD
    A[问题分析] --> B{是否满足贪心性质？}
    B -->|是| C[使用贪心算法]
    B -->|否| D[考虑动态规划]
    D --> E[设计状态转移方程]
    E --> F[实现并测试]

import heapq

def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    queue = [(0, start)]
    
    while queue:
        current_dist, current = heapq.heappop(queue)
        if current_dist > distances[current]:
            continue
        for neighbor, weight in graph[current].items():
            distance = current_dist + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(queue, (distance, neighbor))
    return distances

# 含负权边的图
graph = {
    'A': {'B': 2, 'C': 4},
    'B': {'C': -3, 'D': 1},
    'C': {'D': 2},
    'D': {}
}

print("Dijkstra结果:", dijkstra(graph, 'A'))

Dijkstra结果: {'A': 0, 'B': 2, 'C': -1, 'D': 1}

def bellman_ford(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    
    for _ in range(len(graph)-1):
        for node in graph:
            for neighbor, weight in graph[node].items():
                if distances[node] + weight < distances[neighbor]:
                    distances[neighbor] = distances[node] + weight
    return distances

print("Bellman-Ford结果:", bellman_ford(graph, 'A'))

Bellman-Ford结果: {'A': 0, 'B': 2, 'C': -1, 'D': 1}

def coin_change_greedy(coins, amount):
    coins.sort(reverse=True)  # 降序排列
    count = 0
    for coin in coins:
        while amount >= coin:
            amount -= coin
            count += 1
    return count if amount == 0 else -1

# 标准面额
print("标准案例:", coin_change_greedy([1, 5, 10, 25], 30))  # 25+5 → 2

# 非常规面额
print("陷阱案例:", coin_change_greedy([1, 3, 4], 6))  # 期望3+3=6 → 2枚

标准案例: 2
陷阱案例: 3  # 实际4+1+1 → 3枚，非最优

def coin_change_dp(coins, amount):
    dp = [float('inf')] * (amount+1)
    dp[0] = 0
    
    for coin in coins:
        for x in range(coin, amount+1):
            dp[x] = min(dp[x], dp[x-coin] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1

print("DP结果:", coin_change_dp([1, 3, 4], 6))

DP结果: 2

def knapsack_greedy(items, capacity):
    # 按价值/重量比降序排序
    items.sort(key=lambda x: x[1]/x[0], reverse=True)
    total_value = 0
    for weight, value in items:
        if capacity >= weight:
            capacity -= weight
            total_value += value
    return total_value

items = [(10, 60), (20, 100), (30, 120)]  # (重量, 价值)
capacity = 50
print("贪心结果:", knapsack_greedy(items, capacity))

贪心结果: 160  # 选择物品1和2：60+100=160

def knapsack_dp(items, capacity):
    n = len(items)
    dp = [[0]*(capacity+1) for _ in range(n+1)]
    
    for i in range(1, n+1):
        weight, value = 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]

print("DP结果:", knapsack_dp(items, capacity))

DP结果: 220