分数背包问题[编辑 | 编辑源代码]

分数背包问题（Fractional Knapsack Problem）是贪心算法中的一个经典问题，它允许物品被分割成任意部分装入背包，以最大化背包中物品的总价值。与0-1背包问题不同，分数背包问题可以通过贪心策略找到最优解。

问题描述[编辑 | 编辑源代码]

给定一个容量为 $W$ 的背包和 $n$ 个物品，每个物品有一个重量 $w_{i}$ 和一个价值 $v_{i}$ 。目标是选择物品（或物品的一部分）装入背包，使得总重量不超过 $W$ ，同时总价值最大化。

数学表达式： $最大化 \sum_{i = 1}^{n} x_{i} v_{i} 满足 \sum_{i = 1}^{n} x_{i} w_{i} \leq W 且 0 \leq x_{i} \leq 1$ 其中， $x_{i}$ 表示物品 $i$ 被装入背包的比例。

贪心算法解决思路[编辑 | 编辑源代码]

贪心算法的核心思想是每次选择当前最优的局部解。对于分数背包问题，最优策略是优先选择单位重量价值最高的物品。具体步骤如下： 1. 计算每个物品的单位重量价值： $\frac{v_{i}}{w_{i}}$ 。 2. 按单位重量价值从高到低排序。 3. 依次将物品装入背包，若当前物品可以完整装入，则全部装入；否则装入部分，直到背包装满。

算法伪代码[编辑 | 编辑源代码]

def fractional_knapsack(W, weights, values):
    n = len(weights)
    # 计算单位重量价值并排序
    items = sorted(zip(weights, values, [v/w for v, w in zip(values, weights)]), 
                   key=lambda x: x[2], reverse=True)
    total_value = 0.0
    remaining_capacity = W

    for w, v, ratio in items:
        if remaining_capacity <= 0:
            break
        # 尽可能多地装入当前物品
        amount = min(w, remaining_capacity)
        total_value += amount * ratio
        remaining_capacity -= amount

    return total_value

示例[编辑 | 编辑源代码]

假设背包容量 $W = 50$ ，物品如下：

物品列表
物品	重量 ( $w_{i}$ )	价值 ( $v_{i}$ )	单位重量价值 ( $\frac{v_{i}}{w_{i}}$ )
1	10	60	6.0
2	20	100	5.0
3	30	120	4.0

贪心策略的执行过程： 1. 装入物品1（全部），剩余容量 = 50 - 10 = 40，总价值 = 60。 2. 装入物品2（全部），剩余容量 = 40 - 20 = 20，总价值 = 60 + 100 = 160。 3. 装入物品3（部分，20/30），剩余容量 = 0，总价值 = 160 + (20 * 4) = 240。

最终总价值为240。

时间复杂度分析[编辑 | 编辑源代码]

排序： $O (n \log n)$ （主导步骤）。
遍历物品： $O (n)$ 。

总时间复杂度为 $O (n \log n)$ 。

实际应用[编辑 | 编辑源代码]

分数背包问题的贪心策略在以下场景中有实际应用： 1. 资源分配：如云计算中分配计算资源以最大化收益。 2. 投资组合优化：选择高回报率的资产优先投资。 3. 物流装载：在运输中优先装载高价值密度的货物。

与0-1背包问题的区别[编辑 | 编辑源代码]

分数背包问题：允许分割物品，贪心算法可求得最优解。
0-1背包问题：物品不可分割，贪心算法无法保证最优解，需用动态规划。

可视化示例[编辑 | 编辑源代码]

总结[编辑 | 编辑源代码]

分数背包问题是贪心算法的典型应用，通过优先选择高单位价值物品，可以在多项式时间内求得最优解。理解此问题有助于掌握贪心算法的核心思想：局部最优导致全局最优。