贪心算法背包问题python

好的，背包问题可以使用贪心算法来解决，以下是Python实现：

def knapsack(capacity, weights, values):
    n = len(weights)
    ratio = [(values[i] / weights[i], i) for i in range(n)]
    ratio.sort(reverse=True)
    max_value = 0
    for r, i in ratio:
        if capacity >= weights[i]:
            max_value += values[i]
            capacity -= weights[i]
        else:
            max_value += r * capacity
            break
    return max_value

# 测试
capacity = 50
weights = [10, 20, 30]
values = [60, 100, 120]
print(knapsack(capacity, weights, values)) # 输出220

在代码中，我们首先计算每个物品的性价比，即价值除以重量，然后按照性价比从大到小排序。接着从性价比最大的物品开始，尽可能多地装入背包，直到背包装满为止。如果当前物品无法完全装入背包，则按照比例装入。最后返回背包中物品的总价值。