贪心算法

def coin_change_greedy(amount, coins):
    """
    找零钱问题的贪心算法实现
    :param amount: 需要找零的金额
    :param coins: 可用硬币面值列表（降序排列）
    :return: 每种硬币的数量字典
    """
    coins.sort(reverse=True)  # 按面值从大到小排序
    result = {}
    
    for coin in coins:
        if amount >= coin:
            count = amount // coin
            result[coin] = count
            amount -= coin * count
    
    if amount > 0:
        print(f"无法完全找零，剩余金额: {amount}")
    
    return result

# 示例
coins = [100, 50, 20, 10, 5, 1]  # 可用硬币面值
amount = 176
change = coin_change_greedy(amount, coins)
print(f"找零 {amount} 元的结果: {change}")

def activity_selection(activities):
    """
    活动选择问题的贪心算法实现
    :param activities: 活动列表，每个活动为(start, end)元组
    :return: 选择的活动列表
    """
    # 按结束时间排序
    activities.sort(key=lambda x: x[1])
    
    selected = []
    last_end = 0
    
    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), (8, 12), (2, 14), (12, 16)]

selected = activity_selection(activities)
print("选择的活动:")
for i, (start, end) in enumerate(selected, 1):
    print(f"活动{i}: {start} - {end}")

def fractional_knapsack(capacity, items):
    """
    分数背包问题的贪心算法实现
    :param capacity: 背包容量
    :param items: 物品列表，每个物品为(weight, value)元组
    :return: 最大价值和物品选择方案
    """
    # 计算单位价值并排序
    items_with_ratio = [(weight, value, value/weight) for weight, value in items]
    items_with_ratio.sort(key=lambda x: x[2], reverse=True)
    
    total_value = 0
    selected = []
    
    for weight, value, ratio in items_with_ratio:
        if capacity >= weight:
            # 可以完整放入
            total_value += value
            capacity -= weight
            selected.append((weight, value, 1.0))  # 完整放入
        else:
            # 只能放入一部分
            fraction = capacity / weight
            total_value += value * fraction
            selected.append((weight, value, fraction))
            break
    
    return total_value, selected

# 示例
capacity = 50
items = [(10, 60), (20, 100), (30, 120)]  # (重量, 价值)

max_value, selection = fractional_knapsack(capacity, items)
print(f"最大价值: {max_value}")
print("选择的物品:")
for weight, value, fraction in selection:
    print(f"  重量{weight}, 价值{value}, 放入比例: {fraction:.2f}")