编辑“︁分数背包问题”︁（章节）

== 贪心算法解决思路 ==
贪心算法的核心思想是每次选择当前最优的局部解。对于分数背包问题，最优策略是优先选择'''单位重量价值最高'''的物品。具体步骤如下：
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'''。