努力发现分数背包问题(战利品的最大值)逻辑中的缺陷

问题描述 投票:0回答:0

之前有人问过这个问题:问题但是我已经苦苦挣扎了一段时间来调试我的逻辑错误的地方,因为我的算法在这个未知的测试用例上失败了:

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

任何关于为什么我的逻辑有缺陷的建议将不胜感激。

python python-3.x algorithm knapsack-problem
© www.soinside.com 2019 - 2024. All rights reserved.