我有两组变量,一个静态段长度数组和一个由用户指定的动态最终总长度。
例如,数组 lengths = [50,40,80,30,108,25]
、 total = 150
。
我将如何计算长度数组值的最佳组合以尽可能接近指定的总数?仅使用加法。因为我们使用具有指定长度的段来尽可能接近目标长度。
并非所有数组值都必须使用。每个数组元素都可以无限次使用,但我们希望使用尽可能少的数学来获得最终结果(即不想做 25+25 ,而不是只使用 50)
最佳答案
使用 itertools.combinations_with_replacement
的蛮力方式:
from itertools import combinations_with_replacement
def get_comb(A, N):
out = []
for i in range(1, N//min(A)):
for j in combinations_with_replacement(A, i):
out.append((list(j), abs(sum(j) - N)))
return min(out, key=lambda x: (x[1], len(x[0])))[0]
说明:首先存储所有组合及其与所需总和的绝对差。然后根据元组值取最小值,其中第一个元素是上面计算的差异,第二个元素是组合的长度。这样,它将优先考虑最小差异,当差异相同时,它将采用元素较少的那个。
应用:
In [15]: get_comb(a, 50)
Out[15]: [50]
In [16]: get_comb(a, 100)
Out[16]: [50, 50]
In [22]: get_comb(a, 60)
Out[22]: [30, 30]
In [24]: get_comb(a, 730)
Out[24]: [80, 80, 30, 108, 108, 108, 108, 108]
In [25]: get_comb(a, 73)
Out[25]: [50, 25]
关于python - 给定一个长度数组,找到最接近总长度的组合,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/59206012/