python - 查找总和大于 50 的最短子列表

Question

我有一个列表，我想找到总和大于 50 的最短子列表。 例如我的列表是

[8.4 , 10.3 , 12.9 , 8.2 , 13.7 , 11.2 , 11.3 ,10.4 , 4.2 , 3.3 , 4.0 , 2.1]

我想找到最短的子列表，使其总和大于 50。

输出应类似于[12.9、13.7、11.2、11.3、10.4]

Answer 1

这是一个糟糕的解决方案(就没有进行所有图形搜索并找到最佳值而言)，但解决方案是正确的

lis =[8.4 , 10.3 , 12.9 , 8.2 , 13.7 , 11.2 , 11.3 ,10.4 , 4.2 , 3.3 , 4.0 , 2.1] 


from collections import defaultdict
dic = defaultdict(list)

for i in range(len(lis)):
    dic[lis[i]]+=[i]

tmp_lis = lis.copy()
tmp_lis.sort(reverse=True)

res =[]
for  i in tmp_lis:
    if sum(res)>50 :
        break
    else:
        res.append(i)

res1 = [(i,dic[i]) for i in res]

res1.sort(key=lambda x:x[1])
solution =[i[0] for i in res1]

输出

[12.9, 13.7, 11.2, 11.3, 10.4]