背包问题贪心算法python

背包问题是经典的动态规划问题，但也可以使用贪心算法来解决。具体实现如下：

def knapsack_greedy(weights, values, capacity):
    n = len(weights)
    if n == 0:
        return 0

    # 计算每个物品的性价比
    value_density = [(values[i] / weights[i], i) for i in range(n)]
    # 按性价比从大到小排序
    value_density.sort(reverse=True)

    # 总价值、当前背包容量
    total_value = 0
    current_capacity = capacity

    # 逐个考虑物品
    for vd, i in value_density:
        if current_capacity >= weights[i]:
            # 如果当前物品可以全部装入背包
            total_value += values[i]
            current_capacity -= weights[i]
        else:
            # 否则，只能装入一部分
            total_value += vd * current_capacity
            break

    return total_value

其中，`weights`、`values` 分别表示物品的重量和价值，`capacity` 表示背包的容量。函数返回背包能够装下的最大价值。

该算法的时间复杂度为 $O(n \log n)$，其中 $n$ 是物品的数量。