第 65 课 - 分数背包

学习目标

理解分数背包问题（Fractional Knapsack Problem）与0-1背包问题的区别。
掌握贪心算法在分数背包问题中的应用策略及其正确性。
能够根据物品的“性价比”（单位重量价值）制定贪心策略。
能够独立编写代码解决分数背包问题。

核心概念

想象你是一个小偷，面前有一堆不同重量和价值的宝物，你有一个最大承重的背包。不同的是，这次宝物像金砂、水银一样，你可以只拿走一部分。你的目标是：在不超重的前提下，让带走的宝物总价值最大。

这就是分数背包问题。它与上一课“活动选择”的贪心逻辑一脉相承，但更具体。

贪心策略： 为了最大化价值，我们不能只看物品本身的价值，也不能只看重量。关键指标是 “性价比”，即单位重量的价值（价值/重量）。

策略：优先将“性价比”最高的物品尽可能多地装入背包。如果该物品已全部装入且背包还有剩余空间，再继续装性价比次高的物品，直到背包装满。
为什么有效？ 因为物品可以任意分割。假如你为了价值更高但性价比更低的大件物品，而舍弃了部分性价比高的小件物品，你一定能通过交换（用高性价比物品的微小部分，换回大件物品的更小部分）来提升总价值或腾出空间。贪心策略能确保每一步的局部最优，最终导向全局最优。

代码示例

下面是一个完整的Python代码示例。我们定义一个Item类来表示物品，并实现贪心算法。

class Item:
    """物品类，包含重量、价值和名称"""
    def __init__(self, weight, value, name=""):
        self.weight = weight
        self.value = value
        self.name = name
        self.ratio = value / weight if weight > 0 else 0  # 计算性价比

def fractional_knapsack(items, capacity):
    """
    分数背包的贪心算法
    :param items: 物品列表，元素为Item对象
    :param capacity: 背包容量
    :return: 最大总价值
    """
    # 1. 按性价比降序排序
    items_sorted = sorted(items, key=lambda x: x.ratio, reverse=True)
    
    total_value = 0.0  # 总价值
    remaining_capacity = capacity  # 剩余容量

    # 2. 遍历排序后的物品
    for item in items_sorted:
        if remaining_capacity <= 0:
            break  # 背包已满

        # 3. 计算该物品最多能取多少（全部或部分）
        take_weight = min(item.weight, remaining_capacity)
        # 4. 计算这部分物品的价值
        take_value = take_weight * item.ratio
        # 5. 更新总价值和剩余容量
        total_value += take_value
        remaining_capacity -= take_weight
        
        # 打印装入过程（可选）
        print(f"装入 {item.name} {take_weight:.2f} 单位, 价值 {take_value:.2f}")

    return total_value

# 主函数
if __name__ == "__main__":
    # 定义物品
    items = [
        Item(10, 60, "物品A"),  # 性价比 6.0
        Item(20, 100, "物品B"), # 性价比 5.0
        Item(30, 120, "物品C")  # 性价比 4.0
    ]
    knapsack_capacity = 50

    print(f"背包容量: {knapsack_capacity}")
    print("物品信息:")
    for item in items:
        print(f"  {item.name}: 重量={item.weight}, 价值={item.value}, 性价比={item.ratio:.2f}")
    print("-" * 30)

    max_value = fractional_knapsack(items, knapsack_capacity)
    print("-" * 30)
    print(f"能装入的最大总价值为: {max_value:.2f}")

输出结果：

背包容量: 50
物品信息:
  物品A: 重量=10, 价值=60, 性价比=6.00
  物品B: 重量=20, 价值=100, 性价比=5.00
  物品C: 重量=30, 价值=120, 性价比=4.00
------------------------------
装入 物品A 10.00 单位, 价值 60.00
装入 物品B 20.00 单位, 价值 100.00
装入 物品C 20.00 单位, 价值 80.00
------------------------------
能装入的最大总价值为: 240.00

解释：首先全部装入性价比最高的A(10)和B(20)，剩余20单位容量，再从性价比第三的C中取出20单位，总价值达到最大。

实践练习

基础应用：有3种珠宝：钻石(重量2, 价值1000)，红宝石(重量3, 价值1200)，蓝宝石(重量5, 价值1300)。背包容量为7。请计算最大总价值并说明装入方案。
- 预期思路：计算性价比 -> 排序 -> 贪心装入。
代码修改：修改上面的代码，使其在返回最大价值的同时，返回一个字典，记录每种物品实际被装入的重量。
- 要求输出示例：{'物品A': 10.0, '物品B': 20.0, '物品C': 20.0}
策略对比：假设所有物品必须完整装入或不装（即0-1背包问题），其他条件与代码示例相同（容量50，物品A/B/C）。请手动计算在这种限制下，最大总价值是多少？并与分数背包的结果进行对比，思考贪心策略是否仍然最优。

常见错误

排序依据错误：按总价值 value 或按总重量 weight 排序，而不是按性价比 value/weight 排序。这是最常见的错误，会导致结果不是最优。
忽略物品可分割：在代码逻辑中，当背包剩余空间不足时直接跳过该物品，而没有取其一部分。正确做法是计算能取多少就取多少 (take_weight = min(...))。
整数除法陷阱：在计算性价比 ratio 时，如果使用整数除法 value // weight，会丢失精度。务必使用浮点数除法 /。
背包容量为零：没有处理 capacity 为0的特殊情况，虽然简单，但完整的代码应考虑边界条件。

小结

问题本质：分数背包是允许物品任意分割的背包问题，目标是价值最大化。
贪心核心：贪心策略的关键是按单位重量的价值（性价比）降序排序，并优先装入性价比最高的物品。
策略正确性：该贪心策略对分数背包问题是最优的，因为总可以通过微调高性价比物品的取用量来替换低性价比物品，从而提升总价值。
与0-1背包的区别：对于物品不可分割的0-1背包问题，简单的贪心（按性价比排序后顺序装入）不一定能得到最优解，通常需要使用动态规划。分数背包的贪心策略是其特有且高效的解法。
应用场景：该问题模型常用于资源分配、投资组合优化等场景，其中“资源”可以按比例分配。

练习编辑器

rust