分数背包（Maximum Value of the Loot）算法逻辑错误排查求助

错误信息 #

Failed case #7/13: Wrong answer
got: 101649.0055882329 expected: 66152.572
 (Time used: 0.01/5.00, memory used: 11288576/2684354560.)

问题代码 #

def get_optimal_value(capacity, weights, values):
    value = 0.
    # Create a list of most efficient weight
    efficiency = [values[i] / weights[i] for i in range(len(values))] 

    while capacity > 0:

        # if capacity is greater than the amount of the most efficient weight
        if capacity >= weights[efficiency.index(max(efficiency))]: 
            value = value + max(efficiency) * weights[efficiency.index(max(efficiency))]
            capacity -= weights[efficiency.index(max(efficiency))]
            # weight of most efficient object should be 0
            weights[efficiency.index(max(efficiency))] -= weights[efficiency.index(max(efficiency))] 

        # if capacity is less than the amount of the most efficient weight
        elif capacity <= weights[efficiency.index(max(efficiency))]: 
            value = value + max(efficiency) * capacity
            return value

        # if weight of most efficient object is 0, then remove from 'efficiency' list
        if weights[efficiency.index(max(efficiency))] <= 0: 
            efficiency.pop(efficiency.index(max(efficiency)))
            if len(efficiency) == 0:
                return value
    return value

核心逻辑缺陷 #

• 索引同步错误：当你从efficiency列表中移除元素时，weights和values列表的对应元素并未同步删除，导致后续通过efficiency.index(max(efficiency))获取的索引，无法匹配到正确的物品。例如，移除efficiency[0]后，efficiency的新索引0对应原物品1，但你仍会用这个索引去访问weights[0]（原物品0，已被处理完毕），完全跳过了未处理的物品，或错误计算价值。
• 重复低效的查找操作：每次循环多次调用max(efficiency)和efficiency.index(max(efficiency))，不仅性能低下，还会在存在多个相同最高效率物品时，始终只处理第一个出现的元素（即使该物品已无重量），直到它被移除，导致无意义的循环，甚至跳过其他同效率物品。
• 冗余的已耗尽物品处理：将物品重量设为0后，要等到下一次循环才会从efficiency中移除该元素，期间会执行一次无意义的计算（累加0价值、容量无变化），虽不影响结果，但可能引发其他逻辑异常。

修复后的代码 #

def get_optimal_value(capacity, weights, values):
    value = 0.0
    # 将物品按效率降序排序，绑定效率与重量
    items = sorted([(values[i]/weights[i], weights[i]) for i in range(len(values))], reverse=True)
    
    for efficiency, weight in items:
        if capacity <= 0:
            break
        # 取当前物品重量与剩余容量的较小值
        take_weight = min(weight, capacity)
        value += efficiency * take_weight
        capacity -= take_weight
    
    return value

修复说明 #

• 将每个物品的效率与重量绑定，排序后确保每次优先处理效率最高的物品，从根源避免索引同步问题。
• 遍历一次即可完成处理，无需重复查找最大值，逻辑清晰且效率更高。
• 每次处理时直接取可拿取的最大重量，要么拿完整个物品，要么拿剩余容量的部分，不存在冗余操作。

内容的提问来源于stack exchange，提问作者codinator