问题描述
有N多套，每套包含各种数量的整数，例如：
There is N number of sets, each containing various number of integers, e.g.:
(-2, -1, 0), (-1,4), (-2, 2, 3), (-3, -2, 4, 6), (-2)
如何挑选只有一个数字从每个组使这些N个整数总和为零？例如：
How to pick exactly one number from each set so that these N integers sum to zero? For example:
-1, -1, 2, -2, 4, -2
请注意有可能是无解或多（在这种情况下，它并不重要，我选择哪一个）。
Note there might be no solution or multiple (in which case it doesn't matter which one I choose).
我在想，我能做的呼吸一搜索，但不知道是否有任何其他的，preferably更快的方式来解决这个问题。
I was thinking that I can do breath-first search but was wondering if there are any other, preferably faster, ways to solve this.
推荐答案
让 DP [I，J] =真当且仅当我们可以做一笔 Ĵ用一个数字从每个组 1，2，...，I 。
Let dp[i, j] = true iff we can make sum j using one number from each of the sets 1, 2, ..., i.
dp[i, 0] = true for all i
for i = 1 to numSets do
for num = 1 to sets[i].Count do
for j = maxSum - sets[i, num] downto -maxSum do
dp[i, j + sets[i, num]] |= dp[i - 1, j]
您可以使用地图来处理负指数或加一个偏移量，使他们积极的。 maxSum 为最大值的总和可以采取（对所有套或最小值的绝对值，取较大者之和的最大值的例子总和）。有可能的方式来更新 maxSum ，当您去作为优化。
You can use a map to handle negative indexes or add an offset to make them positive. maxSum is the maximum value your sum can take (for example sum of maximums of all sets or sum of absolute values of minimums, whichever is larger). There might be ways to update maxSum as you go as an optimization.
有关你的榜样，这将运行像这样：
For your example, this will run like so:
(-2, -1, 0), (-1,4), (-2, 2, 3), (-3, -2, 4, 6), (-2)
迭代的第一组会给 DP [1，-2] = DP [1，-1] = DP [1,0] =真。
迭代在第二将给 DP [2 -3] =真（因为DP [2，-2 + -1] | = DP [1，-1] = TRUE），DP [2，-2] =真（因为DP [2，-1 + -1] | = DP [1，-1] =真）。等
如果 DP [numSets，0] =真，有一个解决方案，它可以通过保持跟踪这最后一个号码，你拿起为每<$ C $重构C> DP [I，J] 。
If dp[numSets, 0] = true, there is a solution, which you can reconstruct by keeping tracking of which last number you picked for each dp[i, j].
复杂度 0（numSets * K * maxSum），其中 K 是一个元素的数量组。这是伪多项式。这可能是速度不够快，如果你的值很小。如果你的价值观是很大，但你有几台有几个要素，你最好使用回溯暴力破解它。
The complexity is O(numSets * K * maxSum), where K is the number of elements of a set. This is pseudopolynomial. It might be fast enough if your values are small. If your values are large but you have few sets with few elements, you are better off bruteforcing it using backtracking.
这篇关于选择其中的数字之和为零的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！