我是Python新手，我正在通过代码战慢慢学习我知道这可能违反规则，但我有一个效率问题。
给你一个整数列表
ls=[100，76，56，44，89，73，68，56，64，123，2333，144，50，132，123，34，89]
必须编写函数choose_best_sum（t，k，ls）
这样你就能从ls中找到k个整数的组合，使得这些k个整数的和接近或等于t。
我的最终解决方案通过了测试，但在更详细的测试中可能因为效率而失败。我在努力了解效率。这是我的密码
import itertools
def choose_best_sum(t, k, ls):
if sum(sorted(ls)[:k]) > t or len(ls) < k:
return None
else:
combos = itertools.permutations(ls, k)
return max([[sum(i)] for i in set(combos) if sum(i) <= t])[0]
有人能强调一下瓶颈在哪里吗（我假设是在排列调用中）以及如何使这个函数更快？
编辑：
上面所描述的解决方案给出了
1806730函数在0.458秒内调用
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 0.457 0.457 <string>:1(<module>)
1 0.000 0.000 0.457 0.457 exercises.py:14(choose_best_sum)
742561 0.174 0.000 0.305 0.000 exercises.py:19(<genexpr>)
321601 0.121 0.000 0.425 0.000 exercises.py:20(<genexpr>)
1 0.000 0.000 0.458 0.458 {built-in method builtins.exec}
1 0.000 0.000 0.000 0.000 {built-in method builtins.len}
1 0.032 0.032 0.457 0.457 {built-in method builtins.max}
1 0.000 0.000 0.000 0.000 {built-in method builtins.sorted}
742561 0.131 0.000 0.131 0.000 {built-in method builtins.sum}
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
我得到的最终解决办法是：
def choose_best_sum(t, k, ls):
ls = [i for i in ls if i < t and i < (t - sum(sorted(ls)[:k-1]))]
if sum(sorted(ls)[:k]) > t or len(ls) < k:
return None
else:
return max(s for s in (sum(i) for i in itertools.combinations(ls, k)) if s <= t)
订货人：标准名称
0.002秒内调用7090个函数
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 0.003 0.003 <string>:1(<module>)
2681 0.001 0.000 0.003 0.000 exercises.py:10(<genexpr>)
1 0.000 0.000 0.003 0.003 exercises.py:5(choose_best_sum)
1 0.000 0.000 0.000 0.000 exercises.py:6(<listcomp>)
1 0.000 0.000 0.003 0.003 {built-in method builtins.exec}
1 0.000 0.000 0.000 0.000 {built-in method builtins.len}
1 0.000 0.000 0.003 0.003 {built-in method builtins.max}
17 0.000 0.000 0.000 0.000 {built-in method builtins.sorted}
4385 0.001 0.000 0.001 0.000 {built-in method builtins.sum}
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
最佳答案
你的表达有几个明显的缺陷
max([[sum(i)] for i in set(combos) if sum(i) <= t])[0]
你无缘无故地跑了两次；
您正在将结果打包到列表（
sum(i)）中，然后将其解压缩（[sum(i)]）您无缘无故地将
[0]转换为集合试着用
sums = [sum(c) for c in combos]
return max(s for s in sums if s <= t)
编辑：好的，关于一个更好的算法的一些想法：
哦！首先，使用
combos而不是itertools.combinations你只是在计算总数，物品的顺序没有区别如果您在ie k=4上运行，itertools.permutations将返回4！==24倍于相同输入数据上的combinations。其次，我们希望在一开始就丢弃尽可能多的
permutations项显然，我们可以舍弃任何大于t的值；但我们可以得到一个更紧的界。如果将（k-1）最小值相加，则最大允许值必须（如果我们正在寻找一个精确的和，我们可以反向运行这个技巧-加上（k-1）最大值将给我们一个最小的允许值-我们可以反复应用这两个规则来丢弃更多的可能性。但这在这里并不适用。）第三，我们可以查看（k-1）值的所有组合，然后使用
ls直接跳到可能的最佳k'th值这有点复杂，因为您必须再次检查k'th值是否尚未被选为（k-1）值之一-您不能直接使用内置的bisect.bisect_left函数来执行此操作，但可以使用itertools.combinations code的修改副本（即itertools.combinations返回的索引高于当前使用的上一个索引的测试）。这些因素加在一起会使代码加速一个系数
bisect_left祝你好运！编辑2：
让我们来学习一下过度优化的危险：-）
from bisect import bisect_right
def choose_best_sum(t, k, ls):
"""
Find the highest sum of `k` values from `ls` such that sum <= `t`
"""
# enough values passed?
n = len(ls)
if n < k:
return None
# remove unusable values from consideration
ls = sorted(ls)
max_valid_value = t - sum(ls[:k - 1])
first_invalid_index = bisect_right(ls, max_valid_value)
if first_invalid_index < n:
ls = ls[:first_invalid_index]
# enough valid values remaining?
n = first_invalid_index # == len(ls)
if n < k:
return None
# can we still exceed t?
highest_sum = sum(ls[-k:])
if highest_sum <= t:
return highest_sum
# we have reduced the problem as much as possible
# and have not found a trivial solution;
# we will now brute-force search combinations of (k - 1) values
# and binary-search for the best kth value
best_found = 0
# n = len(ls) # already set above
r = k - 1
# itertools.combinations code copied from
# https://docs.python.org/3/library/itertools.html#itertools.combinations
indices = list(range(r))
# Inserted code - evaluate instead of yielding combo
prefix_sum = sum(ls[i] for i in indices) #
kth_index = bisect_right(ls, t - prefix_sum) - 1 # location of largest possible kth value
if kth_index > indices[-1]: # valid with rest of combination?
total = prefix_sum + ls[kth_index] #
if total > best_found: #
if total == t: #
return t #
else: #
best_found = total #
x = n - r - 1 # set back by one to leave room for the kth item
while True:
for i in reversed(range(r)):
if indices[i] != i + x:
break
else:
return
indices[i] += 1
for j in range(i+1, r):
indices[j] = indices[j-1] + 1
# Inserted code - evaluate instead of yielding combo
prefix_sum = sum(ls[i] for i in indices) #
kth_index = bisect_right(ls, t - prefix_sum) - 1 # location of largest possible kth value
if kth_index > indices[-1]: # valid with rest of combination?
total = prefix_sum + ls[kth_index] #
if total > best_found: #
if total == t: #
return t #
else: #
best_found = total #
else:
# short-circuit! skip ahead to next level of combinations
indices[r - 1] = n - 2
# highest sum found is < t
return best_found