时间戳

首页 > 解决方案 > Finding shortest sublist with sum greater than 50

python - Finding shortest sublist with sum greater than 50

问题描述

I have a list and I want to find shortest sublist with sum greater than 50. For example my list is 

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

and I want to find shortest sublist so that its sum is more than 50.

Output Should be like [12.9 , 13.7 , 11.2 , 11.3, 10.4]

标签： pythonlist

解决方案

这是一个糟糕的解决方案（就不做所有图形搜索并找到最佳值而言），但解决方案是正确的

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]

推荐阅读