分数背包(Fractional Knapsack)算法实现遇List index out of range问题求助

问题根源 #

你的代码存在两个关键问题导致索引相关错误：

1. best_item未初始化：当所有物品的价值密度（value/weight）都不大于0时（比如存在价值为0的物品），maxval初始值为0，循环中if prices[i] > maxval的条件永远不满足，best_item从未被赋值，后续访问weights[best_item]会触发错误。
2. 输入类型不统一：压力测试返回的weights和values是numpy数组，虽然代码中会逐步转为列表，但初始循环时可能引发隐性的索引行为差异问题。

修复后的代码 #

def optimal_value(capacity, weights, values):
    value = 0.0
    # 统一转为Python列表，避免numpy数组的隐性问题
    weights = list(weights)
    values = list(values)

    while capacity > 1e-9 and len(values) > 0:  # 用极小值替代0，避免浮点数精度问题
        # 初始化最大价值密度和对应物品索引
        max_val_per_weight = values[0] / weights[0]
        best_item = 0

        # 遍历寻找价值密度最高的物品
        for i in range(1, len(values)):
            current_val_per_weight = values[i] / weights[i]
            if current_val_per_weight > max_val_per_weight:
                max_val_per_weight = current_val_per_weight
                best_item = i

        # 计算可装入的物品重量
        added = min(capacity, weights[best_item])
        value += (added / weights[best_item]) * values[best_item]
        capacity -= added

        # 移除已完全装入的物品（加精度容错）
        if added >= weights[best_item] - 1e-9:
            del values[best_item]
            del weights[best_item]

    return value

关键优化点 #

• 提前初始化best_item和max_val_per_weight，确保无论物品价值密度如何，都有合法的初始索引。
• 将输入的numpy数组转为Python列表，统一数据类型避免隐性问题。
• 用极小值（1e-9）替代0判断容量，避免浮点数运算导致的精度误差。
• 使用del直接删除元素，比列表推导式更高效且逻辑清晰。

覆盖的边界情况 #

修改后的代码可处理以下场景：

• 容量为0的情况
• 所有物品价值为0的情况
• 单个物品的情况
• 物品总重量小于等于容量的情况

内容的提问来源于stack exchange，提问作者Erol Can Akbaba