最佳旅游Python

Question

https://www.codewars.com/kata/best-travel/train/python

我的代码超时了，我还能做得更好吗？

def choose_best_sum(t, k, ls):
import itertools
values=list(itertools.combinations(ls,k))
distances=[]
for row in values:
    dis=0
    for i in range(k):
        dis+=row[i]
    distances.append(dis)
while len(distances)!=0 and max(distances)>t:
    #print("max:",max(distances),"min:",min(distances))
    distances.pop(distances.index(max(distances)))
if len(distances)==0:
    result="None"
else:
    result=max(distances)
return result

xs = [100, 76, 56, 44, 89, 73, 68, 56, 64, 123, 2333, 144, 50, 132, 123, 34, 89]
choose_best_sum(230, 4, xs)#, 230)
choose_best_sum(430, 5, xs)#, 430)
choose_best_sum(430, 8, xs)#, None)

Answer 1

类似于@aron的答案，但没有对列表进行排序。只需记录最棒的跑步记录。在

import itertools

def choose_best_sum(t, k, ls):
    best_sum = 0
    best_set = None
    combinations = itertools.combinations(ls, k)
    for combination in combinations:
        combi_sum = sum(combination)
        if combi_sum <= t and combi_sum > best_sum:
             best_set = combination
             best_sum = combi_sum
    return (best_set, best_sum)

xs = [100, 76, 56, 44, 89, 73, 68, 56, 64, 123, 2333, 144, 50, 132, 123, 34, 89]
xs = [item for item in xs if item < 430]
choose_best_sum(230, 4, xs)#, 230)
choose_best_sum(430, 5, xs)#, 430)
choose_best_sum(430, 8, xs)#, None)

您可以做的第一件事就是从xs中删除2333，因为它永远不能组合在一起。我不知道为什么，除了创建自己的sum之外，还有while len(distances)!=0 and max(distances)>t:和这么多列表操作（追加和弹出）。%timeit结果：

^{pr2}$

Answer 2

写你自己的^{}可能会让你慢很多。使用内置函数几乎总是更快：

def choose_best_sum(t, k, ls):
    import itertools
    values=list(itertools.combinations(ls,k))
    distances= [sum(row) for row in values]
    #...

当您找到小于t的最大值时，在得到结果之前，您需要对列表进行一系列修改。Python列表在变长或变短方面效率不高，所以最好对列表进行排序，或者迭代，直到找到大于t的边，或者可以使用binary search。在

^{pr2}$