从给定数字中找到一个序列，使得其总和为给定值？

Question

给定一组整数（正数或负数），如何找到一个数字序列，使其总和为给定值？

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

这类似于 Subset Sum Problem（http://en.wikipedia.org/wiki/Subset_sum），但在我的情况下，数字可以重复使用。

这也有点像 Partition problem（Find all possible subsets that sum up to a given number），但在我的情况下有负值。

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

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)

- yegle

---

看起来你已经有一个解决方案了。你是在尝试达到某种复杂度或减少需求或其他什么吗？ - Waleed Khan

@WaleedKhan 这是一种贪心算法，因此可能无法给出最优解。我希望有人能给我一个更好的解决方案，可以更快（我的解决方案相当慢）或提供最优解。 - yegle

我认为当前的算法没有考虑到所有可能性。 - Abhishek Bansal

你需要暴力破解它……据我所知，这方面没有什么简单的算法。 - Joran Beasley

@AbhishekBansal 不是的。它只是一种贪心算法，根据当前情况做出选择。 - yegle

Answer 1

很可能没有快速算法可以给出最优解。子集和问题是NP完全问题，而该问题比您的问题更容易（因为您允许重复使用数字）。

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

- Simeon Visser

---

谢谢您的建议。我会尝试使用 Cython 来提高性能。 - yegle

Answer 2

由于显然至少是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 }

您可以使用任何求解器来解决它。

- Abhishek Bansal

---

谢谢您的回答。除了“整数规划”的维基页面外，我对混合整数线性规划并不熟悉。您能否提供一些适合新手的页面？ - yegle

证明NP难度并不是显而易见的。请参考https://math.stackexchange.com/questions/12273。您是否有这个问题的证明草图或一些参考文献？ - phs