从给定的数字求和到给定值的序列？

Question

给定一组整数（正数或负数），我怎样才能找到一个和给定值相加的数字序列？

示例：给定一个数字列表[4，-16，9，33]，我需要求和17。我可以选择序列[4,4,9]（数字可以重复使用）或[-16,33]。我正试图找到一种有效的方法来缩短序列的长度。

这就像子集和问题(http://en.wikipedia.org/wiki/Subset_sum)但就我而言，数字可以重复使用。

这也有点像分区问题（找到所有可能的子集，求和到一个给定的数字），但在我的例子中有负值。

我目前的贪婪算法如下。在每个循环中，我将尝试找到一个使当前和与目标和之间的差异最小化的数字。

integers = [-2298478782, 1527301251, 4, 4078748803, 3388759435,
        1583071281, 2214591602, 1528349827, -12, 59460983,
        -939524100, -1, 2315255807]
target_sum = 1997393191

difference = target_sum
chain = list()
while difference != 0:
    min_abs_difference = abs(difference)
    next_int = 0
    found = False
    for i in integers:
        new_abs_diff = abs(i+difference)
        if new_abs_diff < min_abs_difference:
            found = True
            next_int = i
            min_abs_difference = new_abs_diff
    if not found:
        print(difference)
        print(chain)
        print("Cannot find an integer that makes difference smaller")
        break
    difference += next_int
    chain.append(next_int)
print(chain)

Answer 1

因为它显然至少是NP完全问题，所以你可以把它描述成一个混合整数线性规划问题。

Minimize summation( Xi ) // Xi = number of times the array element Ai is used.
Subject To
     summation( Ai*Xi ) = S.
     Xi >= 0 { Xi are all integers }

你可以用任何解算器来解。

Answer 2

最有可能的是，没有一种快速算法可以给出最优解。子集和问题是NP完全问题，这个问题比你的问题简单（因为你允许重复使用数字）。

考虑到这个问题是NP完全问题，我认为您应该专注于改进当前的算法，或者用更快的语言（如C）重写它。然后您可以从Python调用您的C代码。