题目:
John and Mary want to travel between a few towns A, B, C … Mary has on a sheet of paper a list of distances between these towns. ls = [50, 55, 57, 58, 60]. John is tired of driving and he says to Mary that he doesn’t want to drive more than t = 174 miles and he will visit only 3 towns.
Which distances, hence which towns, they will choose so that the sum of the distances is the biggest possible to please Mary and John?
Example:
With list ls and 3 towns to visit they can make a choice between: [50,55,57],[50,55,58],[50,55,60],[50,57,58],[50,57,60],[50,58,60],[55,57,58],[55,57,60],[55,58,60],[57,58,60].
The sums of distances are then: 162, 163, 165, 165, 167, 168, 170, 172, 173, 175.
The biggest possible sum taking a limit of 174 into account is then 173 and the distances of the 3 corresponding towns is [55, 58, 60].
The function chooseBestSum (or choose_best_sum or … depending on the language) will take as parameters t (maximum sum of distances, integer >= 0), k (number of towns to visit, k >= 1) and ls (list of distances, all distances are positive or null integers and this list has at least one element). The function returns the “best” sum ie the biggest possible sum of k distances less than or equal to the given limit t, if that sum exists, or otherwise nil, null, None, Nothing, depending on the language. With C++, C, Rust, Swift, Go, Kotlin return -1.
Examples:
ts = [50, 55, 56, 57, 58] choose_best_sum(163, 3, ts) -> 163
xs = [50] choose_best_sum(163, 3, xs) -> nil (or null or … or -1 (C++, C, Rust, Swift, Go)
ys = [91, 74, 73, 85, 73, 81, 87] choose_best_sum(230, 3, ys) -> 228
Note: don’t modify the input list ls.
大概的意思就是从一个列表(各旅行地点之间的距离)中找出一组数字(几个距离),使这组数字的和最接近给定的总和距离。
我的思路就是比较传统的方法:
1.组合数字
2.每组加和
3.每组的和 - 给定的距离的绝对值的最小值的组就是最接近的组,和就是答案。
开始编码:
第一版:
def choose_best_sum(t, k, ls):
if ls==[]:
return None
else:
s=list(permutations(ls,k))
su=[sum(x) for x in s]
mino=10000
res=0
for i in su:
if abs(i-t)<mino:
mino=abs(i-t)
res=i
return res
这个解法通过了两个基础测试,然后没有通过attempt。错误是:
第二版:
大致思路与第一版相同,不过方法改成了combinations。另外把加和放在了里面,这个约束比较好。
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_sum
但是和前面的情况一样,还是出现了0 should equal None.
搜了很多地方也没有找出哪里的问题,于是觉得看答案。
答案:
第一名的答案:
import itertools
def choose_best_sum(t, k, ls):
try:
return max(sum(i) for i in itertools.combinations(ls,k) if sum(i)<=t)
except:
return None
简单评述下:这里用了try except,就。。。
第二个答案:
from itertools import combinations
def choose_best_sum(t, k, ls):
return max((s for s in (sum(dists) for dists in combinations(ls, k)) if s <= t), default=None)
这个答案,一句default=None
所以,你会了吗。。。