编辑“︁分数背包问题”︁

= 分数背包问题 =

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

== 问题描述 ==
给定一个容量为<math>W</math>的背包和<math>n</math>个物品，每个物品有一个重量<math>w_i</math>和一个价值<math>v_i</math>。目标是选择物品（或物品的一部分）装入背包，使得总重量不超过<math>W</math>，同时总价值最大化。

数学表达式：
<math>
\text{最大化} \sum_{i=1}^{n} x_i v_i \quad \text{满足} \quad \sum_{i=1}^{n} x_i w_i \leq W \quad \text{且} \quad 0 \leq x_i \leq 1
</math>
其中，<math>x_i</math>表示物品<math>i</math>被装入背包的比例。

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

=== 算法伪代码 ===
<syntaxhighlight lang="python">
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
</syntaxhighlight>

=== 示例 ===
假设背包容量<math>W = 50</math>，物品如下：

{| class="wikitable"
|+ 物品列表
! 物品 !! 重量 (<math>w_i</math>) !! 价值 (<math>v_i</math>) !! 单位重量价值 (<math>\frac{v_i}{w_i}</math>)
|-
| 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'''。

== 时间复杂度分析 ==
* 排序：<math>O(n \log n)</math>（主导步骤）。
* 遍历物品：<math>O(n)</math>。
总时间复杂度为<math>O(n \log n)</math>。

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

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

== 可视化示例 ==
<mermaid>
pie
    title 背包装入比例（示例）
    "物品1 (10/10)" : 20
    "物品2 (20/20)" : 40
    "物品3 (20/30)" : 40
</mermaid>

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

[[Category:计算机科学]]
[[Category:数据结构与算法]]
[[Category:贪心算法]]