从给定的数字中找到一个序列，该序列的总和是给定值？
提问于 2013-10-29 18:08:58
给定一组整数(正数或负数)，如何找到这些数字的和为给定值的序列？
示例:给定一个数字列表[4,-16, 9, 33]，我需要求和17。我可以选择sequence [4, 4, 9](数字可以重用)或[-16, 33]。我正在尝试找到一种有效的方法来减少序列的长度。
它类似于Subset Sum Problem (http://en.wikipedia.org/wiki/Subset_sum)，但在我的例子中，数字可以重用。
这也有点像分区问题(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)
回答 2
Stack Overflow用户
发布于 2013-10-29 18:18:11
很可能没有一个快速的算法可以给出一个最优的解决方案。子集求和问题是NP完全的，这个问题比你的问题容易(因为你允许重复使用数字)。
考虑到这个问题是NP完全的，我认为您应该专注于改进当前的算法，或者用更快的语言(如C )重写它，然后您就可以从Python中调用C代码了。
Stack Overflow用户
发布于 2013-10-29 18:25:24
因为它显然至少是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 }您可以使用任何求解器来求解它。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/19665962
复制相关文章
腾讯云开发者
