python - Python 列表中的一个或多个元素的总和或值等于给定条件
问题描述
我正在制作一种算法,该算法可以从列表中获取一个元素或元素列表,该列表等于或其总和等于给定数字。
list1 = [1,1, 1, 1,2,3,3,4,7,8,9, 45, 67, 98] (Sum up to 3)
list2 = [5,40, 70, 120, 150] (Sum up to 130)
从list1
想要总和为 3 的元素开始,但我的目标是找出像 3 这样的确切数字是否在列表中,然后选择它,否则选择其他总和为 3 的数字。
从list2
我需要一个等于 130 的值或总和为 130 的元素,如您所见,没有匹配的值,因此我需要选择一个与其最接近的匹配元素,例如 150,然后将其保存到另一个数组。注意:请不要说要组合的元素没有限制,只要元素总数达到所需的数量,但我更愿意先查看列表中是否有确切的数字匹配。
下面是我正在使用的代码,但我只能得到总结的值,我需要帮助来解决更复杂的解决方案。
class select_pair():
def __init__(self, l, target):
self.__l = l
self.__target = target
if not isinstance(l, list):
raise TypeError("it must be a list")
elif not isinstance(target, int):
raise TypeError("it must be an integer")
for i in range(len(l)-1):
if l[i] == target:
print("from 1st index1:{}".format(i))
break
elif l[i]+l[i+1] == target:
print("from second index1:{}, index2:{}".format(i+1, i+2))
break
p = select_pair(list1,3)
p = select_pair(list2,130)
解决方案
可能没有更好的方法来测试列表中 1、2、3、... 元素的所有组合是否与给定的目标总和匹配。但是,您可以通过使用元组(difference to target, number of element)
作为要最小化的键来组合您的三种情况(完全匹配、匹配和和最接近的和)。
from itertools import combinations
def combs(lst, n):
return (c for k in range(1, n+1) for c in combinations(lst, k))
def best_match(lst, target, n=3):
return min(combs(lst, n), key=lambda c: (abs(target - sum(c)), len(c)))
list1 = [1,1, 1, 1,2,3,3,4,7,8,9, 45, 67, 98]
list2 = [5,40, 70, 120, 150]
print(best_match(list1, 3)) # (3,)
print(best_match(list2, 130)) # (5, 120)
这里,n
是要组合的最大元素数。您当然也可以使用比 更高的值3
,但是对于更长的列表,这将意味着要比较的元素更多。另外,请注意,如果找到完美匹配,此函数不会提前停止,尽管可以使用常规循环而不是min
.
def best_match_stop_early(lst, target, n=3):
best = None
for c in combs(lst, n):
v = (abs(target - sum(c)), len(c), c)
if best is None or v < best:
best = v
if v[0] == 0:
return v[2]
return best[2]
同样,您可以调整combs
函数以不仅生成所有组合,还可以提前中止,例如,如果组合的总和已经大于目标总和,那么向该组合添加更多数字不会使其变得更好——但是其他更长的组合可能会更好。但是,这只适用于这个特定的目标函数,并且只有在列表中没有负数的情况下。
推荐阅读
- json - 如何使用 cURL 将多个 JSON 文件发布到服务器
- javascript - Fabric UI 组件未在 IE 中显示
- algorithm - 修改后的 baugh-wooley 算法相乘 verilog 代码不能正确相乘
- android - Android studio 3.3.1:一些断点显示没有打勾,也没有被命中
- c#-4.0 - 如何在表格之间切换
- javascript - 使用 1 个按钮显示 2 个画布图像
- amazon-web-services - EC2 公共 IP 地址与 Route 53 记录不匹配
- transactions - 是否可以通过 gremlin 服务器在 OrientDB 中打开事务?
- arrays - 使用“ls”并保留结果数组中的空格
- javascript - 当我使用 GET 时,Ajax If else not workign