贪婪算法python实现

贪婪算法是一种启发式算法，它在每一步选择当前看起来最优的解决方案，而不考虑整体最优解。下面是一个用Python实现的贪婪算法示例：

def greedy_algorithm(items, capacity):
    # 按照性价比排序，性价比 = 价值 / 重量
    items.sort(key=lambda x: x[1] / x[2], reverse=True)
    
    total_value = 0
    total_weight = 0
    selected_items = []
    
    for item in items:
        if total_weight + item[2] <= capacity:
            selected_items.append(item[0])
            total_value += item[1]
            total_weight += item[2]
    
    return selected_items, total_value

# 测试
items = [('item1', 60, 10), ('item2', 100, 20), ('item3', 120, 30)]
capacity = 50

selected_items, total_value = greedy_algorithm(items, capacity)
print("Selected items:", selected_items)
print("Total value:", total_value)

在这个示例中，我们有一个物品列表，每个物品都有一个名称、价值和重量。我们希望通过贪婪算法选择一些物品，使得它们的总重量不超过给定的容量，并且总价值最大化。

在这个实现中，我们首先按照性价比（即价值除以重量）对物品列表进行排序。然后，我们逐个考虑每个物品，如果将该物品加入选择列表后总重量仍然不超过容量，我们就将该物品加入选择列表，并更新总价值和总重量。

最后，我们返回选择的物品列表和总价值。

注意：贪婪算法并不一定能得到最优解，它只能得到一个近似解。所以在使用贪婪算法时需要根据具体问题进行评估和调整。