Python求解一个背包问题

这是一个普通的背包问题, 我们可以直接暴力求解。

N, M = map(int,input().split())
f = [] # 存放价值，重量，单价

# 价值和重量的输入
for i in range(N):
    t = []
    t = list(map(int,input().split()))
    t.append(t[0]/t[1]) # 计算每一个物品的单价
    f.append(t)

# 对所获得的列表进行单价排序
f.sort(key=lambda x:x[2], reverse = True)

max_value = 0
for i in range(len(f)):
    if M >= f[i][1]: # 如果背包空闲重量M大于第i个物品的重量
        M -= f[i][1]  # 拿第i个物品，背包空闲M减去第i个物品的重量
        max_value += f[i][0] # 加上第i个物品的价值
    else: # 空闲重量M比第i个物品的重量小，因为物品可分割，所以拿空闲重量 * 第i个物品的单价
        max_value += (M * f[i][2])
        break # 拿满了背包直接跳出循环即可

print("{:.2f}".format(max_value))