python - 寻找 8 个元素的最佳可能组合，8 个列表中的每一个

Question

我的问题是我有 8 个大小列表(10、10、10、10、10、50、50、50)。每个列表中的每个元素都有一个必需的成本和一个值。我想要做的是找到 8 个元素(每个列表中有 1 个)的组合，该组合具有最高的组合值，同时不超过成本上限。我想出的是蛮力，因为我认为在完成前 1 小时后内存不足。是否值得尝试实现类似先验算法的东西，或者是否有更好的方法。到目前为止我所拥有的:

import itertools

foo = open("test.txt", "r")

L1 = []
L2 = []
L3 = []
L4 = []
L5 = []
L6 = []
L7 = []
L8 = []

costCap = 10000 #max cost allowed
perfValue = 0 #
final = []

for line in foo:
    line = ','.join(line.split())
    line2 = line.split(",")[1] #values

    if(line2 == "A1"):
        L3.append(line)
    elif(line2 == "A2"):
        L2.append(line)
    elif(line2 == "A3"):
        L5.append(line)
    elif(line2 == "A4"):
        L1.append(line)
    elif(line2 == "A5"):
        L4.append(line)

    L6.append(line)
    L7.append(line)
    L8.append(line)


l1 = list(itertools.product(L1, L2, L5, L4, L3, L6, L7, L8))
for k in range(len(l1)):
    s1 = l1[k][0].split(",")[5]
    s2 = l1[k][1].split(",")[5]
    s3 = l1[k][2].split(",")[5]
    s4 = l1[k][3].split(",")[5]
    s5 = l1[k][4].split(",")[5]
    s6 = l1[k][5].split(",")[5]
    s7 = l1[k][6].split(",")[5]
    s8 = l1[k][7].split(",")[5]
    temp = int(s1[1:]) + int(s2[1:]) + int(s3[1:]) + int(s4[1:]) + int(s5[1:]) + int(s6[1:]) + int(s7[1:]) + int(s8[1:])
    if ((temp > perfValue) and (temp < costCap)):
        perfRating = temp
        final = l1[k]

print(final)

Edit1:抱歉，大部分是文本文件解析。真正发生的是 l1 = list(itertools.product(L1, L2, L5, L4, L3, L6, L7, L8)) 找到所有可能的组合，然后 for 循环只检查查看哪些组合在低于上限时具有最高值(value)。

Answer 1

您遇到的内存限制是由于您的循环是如何编写的，它应该迭代产品的生成器而不是从该生成器创建列表:

for k in itertools.product(L1, L2, L5, L4, L3, L6, L7, L8):
    s1 = k[0].split(",")[5]
    s2 = k[1].split(",")[5]
    s3 = k[2].split(",")[5]
    s4 = k[3].split(",")[5]
    s5 = k[4].split(",")[5]
    s6 = k[5].split(",")[5]
    s7 = k[6].split(",")[5]
    s8 = k[7].split(",")[5]
    temp = int(s1[1:]) + int(s2[1:]) + int(s3[1:]) + int(s4[1:]) + int(s5[1:]) + int(s6[1:]) + int(s7[1:]) + int(s8[1:])
    if ((temp > perfValue) and (temp < costCap)):
        perfRating = temp
        final = k