python - 请帮助我解决分数背包问题（战利品的最大值）

Question

战利品的最大值

问题介绍：

小偷发现的战利品比他的包装得下的多。假设战利品的任何一部分都可以放入他的包中，帮助他找到最有价值的物品组合。问题描述

任务：此代码问题的目标是实现分数背包问题的算法。
输入格式：输入的第一行包含物品的数量和背包的容量。下一行定义了项目的值和权重。第 - 行包含整数和 - 第 - 项的值和权重，分别。
约束条件：1≤≤103,0≤≤2·106；0≤≤2·106,0<≤2·106，所有1≤≤。所有数字均为整数。
输出格式输出适合背包的物品分数的最大值。程序的答案与最佳值之间的差值的绝对值最多应为 -3 您的答案，虽然计算正确，但由于舍入问题可能会出错）。

样品 1。

输入：
3 50
60 20
100 50
120 30

输出：
180.0000
为了达到 180 的值，我们将第一项和第三项放入包中。

样品 2。

输入：
1 10
500 30
输出：
166.6667

我的代码：

# Maximum Value of the Loot

def knapsack(n, capacity, value_list, weight_list):
    unitValues_list = []
    
    #First lets calculate the unitValues_list
    for i in range (n):
        unitValue = (value_list[i]/weight_list[i])
        unitValues_list.append(unitValue)
    
    #Now lets fill the knapsack, intake is how much is in the bag at the moment!
    intake = 0
    max_value = 0
    factor = True

    while(factor):
        max_index = unitValues_list.index(max(unitValues_list, default=0)) 
        # this gives the index of the max valued element
        
        if(weight_list[max_index] <= capacity):
            # In this case, full item is taken in
            intake = weight_list[max_index]
            capacity -= weight_list[max_index]
            max_value += value_list[max_index]
            
        else:
            # weight_list[max_index] > capacity
            # In this case, fraction to be taken
            intake += capacity
            capacity = 0
            max_value += unitValues_list[max_index]*intake
            
        weight_list.pop(max_index)
        value_list.pop(max_index)
        unitValues_list.pop(max_index)
        print(weight_list)

        n -= 1 #no. of items left
        factor = ((n != 0) if ((capacity != 0) if True else False) else False)

    return max_value

if __name__ == "__main__":
    value_list = []
    weight_list = []
    
    #The first line of the input contains the number  of items and the capacity  of a knapsack. 
    #The next  lines define the values and weights of the items. 
    
    n , capacity = map(int, input().split())
    
    for i in range (n):
        value , weight = map(int, input().split())
        value_list.append(value)
        weight_list.append(weight)
        
    #Output the maximal value of fractions of items that fit into the knapsack.
    print("{:.10f}".format(knapsack(n, capacity, value_list, weight_list)))

我不断收到错误消息：

失败案例 #6/13：得到错误答案
：预期 8740.3008948546：7777.731
（使用时间：0.00/5.00，使用内存：9191424/671088640。）

标签： pythonpython-3.xknapsack-problem

Answer 1

纠正错误答案

改正分数

intake += capacity
capacity = 0
max_value += unitValues_list[max_index]*intake

至

fraction = capacity / weight_list[max_index] 
max_value += value_list[max_index]*fraction
capacity = 0 

重构代码

def knapsack(n, capacity, value_list, weight_list):
    unitValues_list = []

    #First lets calculate the unitValues_list
    for i in range (n):
        unitValue = (value_list[i]/weight_list[i])
        unitValues_list.append(unitValue)

    #Now lets fill the knapsack, intake is how much is in the bag at the moment!
    intake = 0
    max_value = 0
    factor = True

    while(factor):
        max_index = unitValues_list.index(max(unitValues_list, default=0)) 
        # this gives the index of the max valued element

        if(weight_list[max_index] <= capacity):
            # In this case, full item is taken in
            intake = weight_list[max_index]
            capacity -= weight_list[max_index]
            max_value += value_list[max_index]

        else:
            # weight_list[max_index] > capacity
            # In this case, fraction to be taken
            fraction = capacity / weight_list[max_index] 
            max_value += value_list[max_index]*fraction
            capacity = int(capacity - (weight_list[max_index] * fraction))

        weight_list.pop(max_index)
        value_list.pop(max_index)
        unitValues_list.pop(max_index)
        print(weight_list)

        n -= 1 #no. of items left
        factor = ((n != 0) if ((capacity != 0) if True else False) else False)

    return max_value

if __name__ == "__main__":
    value_list = []
    weight_list = []

    #The first line of the input contains the number  of items and the capacity  of a knapsack. 
    #The next  lines define the values and weights of the items. 

    n , capacity = map(int, input('n, capacity: ').split())

    for i in range (n):
        value , weight = map(int, input('value, weight: ').split())
        value_list.append(value)
        weight_list.append(weight)

    #Output the maximal value of fractions of items that fit into the knapsack.
    print("{:.10f}".format(knapsack(n, capacity, value_list, weight_list)))

笔记

没有提到时间是一个问题。

通过对 unitValues_list 进行排序而不是每次都计算最大值，可以将复杂度从当前的 O(n^2) 算法更改为 O(n*log(n))。