我有两组变量,一个静态段长度数组和一个由用户指定的动态最终总长度。

例如,数组 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/

10-11 22:34
查看更多