时间戳

首页 > 解决方案 > 我无法在 python 中使用贪心算法解决分数背包问题

python - 我无法在 python 中使用贪心算法解决分数背包问题

问题描述

问题描述： - 最大化战利品问题的价值找到适合背包的物品的最大值。

输入：背包的容量 W 以及 n 个不同化合物的重量（w 1 ，...，wn ）和每磅价格（p 1 ，...，pn ）。

输出：给定容量的背包中物品的最大总价格：即 p 1 · u 1 + · · · + pn · un 的最大值，使得 u 1 + · · · + un ≤ W 和 0 ≤ ui ≤ wi 对于所有 i。

输入格式 - 输入的第一行包含化合物的数量 n 和背包的容量 W。接下来的 n 行定义了化合物的价格和重量。第 i 行包含每磅 pi 的价格和第 i 个化合物的重量 wi。

输出格式 - 输出适合背包的化合物的最高价格。

这是我的代码：-

b = []                              # list
n = input().split()                 # number of elements here
total_weight = int(n[1])            # total_weight
times = int(n[0])                   # No of things
for i in range(times):
    item = [int(x) for x in input().split()]          # 10 50   - price weight
    per  = float(item[0])/float(item[1])              # per = 10/50 
    item.insert(0,per)
    b.append(item)                                    # list
b.sort(reverse = True)                            # sort on the basis of per
value = 0
for i in range(times):
    if b[i][2] >= total_weight:     # b[i] = [2,100,50]  total_weight = 20
        value = value + (b[i][0] * total_weight) # 2 * 20 = 40
    if b[i][2] < total_weight:
        value = value + (b[i][0] * b[i][2])    #b[i] = [5,50,10] total_weight = 20   5*10     
    if value == total_weight:
        break
    total_weight = total_weight - b[i][2]
print(round(value,4))

在某些情况下，我无法得到正确的答案。如果有任何逻辑错误，请检查我的代码

标签： pythonalgorithmdata-structuresknapsack-problemgreedy

解决方案

输入值price per pound p i已经是排序键，所以引入per变量和对应的字段item / b[]似乎是错误的。

另请注意，这里

if value == total_weight:

27.000000000001您比较浮点值是否完全相等 - 它并不完全正确，因为由于精度有限，您可以获得结果。

值得使用math.isclose函数与一些容差水平进行比较。你可以删除这个比较，在第一个 if 块中添加 break

推荐阅读