组合 2 个数组，其中结果总和尽可能接近

Question

我希望有人能帮助我解决这个问题或指出正确的方向。我想要做的是在仅从数组 2 中取 1 个值并将它们相加时，让数组 1 中的所有值尽可能彼此相等。数组 1 比数组 2 短得多。我将在下面举一个例子，其中包含我正在使用的一些实数。

例如：

array1 = [458.6,458.5,458.4,457.1,455] 和 array2=[5.6,5.6,5.7,5.8,5.8,5.9,5.9,5.9,5.9,6,6,6.1,6.1,6.2,6.2]

如果我将 array1[0] 和 array2[0] 相加，则等于 464.2。

如果我一直这样通过 array1 和 array2 那么生成的数组将是 [464.2,464.1,464.1,462.9,460.9]

您可以看到数组中的前 3 个数字彼此非常接近，仅相差 .1，但后几个相差更多。

而如果它知道使用 'array2' 末尾的数字，那么结果数组中的最后两个值将更接近前 3 个值。

这是我卡住的地方，不确定如何继续。我知道这很难，因为每次代码为运行时，值都可能不同，并且没有要查找的设定值。它只是开始以一种模式出现。

感谢您抽出宝贵时间，非常感谢您提供的任何帮助。

Answer 1

我的第一个想法是贪心算法，但这也可能适用于一些随机优化算法，例如遗传算法、进化策略或简单的 hill-climb。这是非常中的一个简单示例 Python:

import random

def score(a1, a2):
    # sum of squared error from average
    a3 = [a+b for a, b in zip(a1, a2)]
    s = sum(a3)/len(a3)
    return sum(abs(s - x)**2 for x in a3)

def opt(a1, a2):
    cur = list(a2)
    for i in range(1000):
        new = list(cur)
        # random mutation
        a, b = random.randrange(len(cur)), random.randrange(len(cur))
        new[a], new[b] = new[b], new[a]
        # better than current -> keep
        if score(a1, new) < score(a1, cur):
            cur = new
    return cur[:len(a1)]

这里，cur是当前解，只是对array2中的元素（包括不需要的元素）进行排列，随机交换，如果“得分”更好。

对于您的样本数据，这始终会产生这样的结果，虽然看起来不太好，但实际上似乎已经差不多了。

result: [5.6, 5.6, 5.7, 6.2, 6.2]
sums:   [464.2 464.1, 464.1 463.3, 461.2]

如果这看起来可行，可以进一步改进算法，例如保留不止一个parent，或者每代创造更多的后代，确保交换中至少有一个元素实际上是相关的，缓存当前最好的分数，或者允许连续发生一个以上的突变。

组合 2 个数组，其中结果总和尽可能接近

Combining 2 arrays where the resulting sums are as close as possible

arrays

sorting

algorithm

equality

filter