在小于某个数字的列表中查找最大组合时效率低下的代码

Question

我正在尝试代码战争问题，但出现超时错误，这表明我的代码执行时间太长并且效率低下。老实说，我不明白如何调整我当前的代码以使其更快，但希望得到一些帮助。该代码的目的是在列表ls中找到k元素的组合，从而得出低于t的最高总和。我的代码如下：

def choose_best_sum(t, k, ls):
    from itertools import product
    lists = [(s, sum(s)) for s in product(ls, repeat=k)]
    highest_sum = 0
    res = None
    for i in range(len(lists)):
        if lists[i][1]<t and lists[i][1]>highest_sum:
            highest_sum = lists[i][1]
            res = lists[i][0]
    return res

例如，choose_best_sum(174, 3, [50, 55, 57, 58, 60])应返回 (55,58,60(

Answer 1

性能更高的版本：

import timeit
def find_best_sum(threshold, k, ls):
    from itertools import combinations
    highest_sum = 0
    res = None
    for t in combinations(ls, r=k):
        s = sum(t)
        if s < threshold and s > highest_sum:
            highest_sum = s
            res = t
    return res

print(find_best_sum(174, 3, [50, 55, 57, 58, 60]))   # (55, 58, 60)

---

比较：

print('choose_best_sum', timeit.timeit('choose_best_sum(174, 3, [50, 55, 57, 58, 60])',
                    setup='from __main__ import choose_best_sum', number=1000))
print('find_best_sum', timeit.timeit('find_best_sum(174, 3, [50, 55, 57, 58, 60])',
                    setup='from __main__ import find_best_sum', number=1000))

输出(连续(：

choose_best_sum 0.053198210999999995
find_best_sum 0.004936765999999981