分数背包问题贪心算法讲解

分数背包问题是指一个背包最多能装下 W 单位重量的物品，现在有 n 个物品，第 i 个物品的重量为 w[i]，价值为 v[i]，可以将该物品的一部分放入背包中，算法要求找到一种最优方案，使得背包中物品的总价值最大。

贪心算法思想是每次选择单位重量价值最大的物品放入背包中，直到背包放满为止。具体实现步骤如下：

1. 计算每个物品的单位重量价值，即 v[i]/w[i]。
2. 按照单位重量价值从大到小排序。
3. 依次将单位重量价值最大的物品放入背包中，直到背包放满或者所有物品都被放入背包为止。

以下是 Python 代码实现：

def fractional_knapsack(w, v, W):
    n = len(w)
    # 计算每个物品的单位重量价值
    unit_values = [(v[i] / w[i], i) for i in range(n)]
    # 按照单位重量价值从大到小排序
    unit_values.sort(reverse=True)
    # 初始化背包价值和重量
    total_value = 0
    total_weight = 0
    # 依次将单位重量价值最大的物品放入背包中
    for uv, i in unit_values:
        if total_weight + w[i] <= W:
            total_value += v[i]
            total_weight += w[i]
        else:
            # 背包放不下整个物品，只能装入一部分
            remain_weight = W - total_weight
            total_value += uv * remain_weight
            break
    return total_value

时间复杂度为 O(nlogn)，其中需要排序的时间复杂度为 O(nlogn)。