背包问题贪心算法python

背包问题是经典的动态规划问题，但是也可以使用贪心算法来解决。具体做法是将物品按照单位重量的价值从大到小排序，然后依次将物品放入背包中，直到背包装满为止。以下是背包问题贪心算法的Python代码实现：

def knapsackGreedy(capacity, weights, values):
    n = len(weights)
    items = []
    for i in range(n):
        items.append((values[i]/weights[i], weights[i], values[i]))
    items.sort(reverse=True) #按照单位重量价值从大到小排序
    result = 0
    for item in items:
        if capacity == 0:
            break
        elif capacity >= item[1]:
            result += item[2]
            capacity -= item[1]
        else:
            result += capacity * item[0]
            capacity = 0
    return result

其中，capacity表示背包的容量，weights表示物品的重量列表，values表示物品的价值列表。函数返回背包能够装载的最大价值。