查找列表中哪个数字加起来等于某个数字的算法

Question

我有一个数字清单。我也有一定数目
该总和由我列表中的几个数字得出（我可能/可能不知道它是由多少个数字组成的）。是否有一种快速算法来获取可能的数字列表？用Python编写会很棒，但是伪代码也很好。（除Python：P之外，我什么都看不到）

例

list = [1,2,3,10]
sum = 12
result = [2,10]

注意：
我确实知道算法，可以从大小为n的列表中找到哪些数字总和为另一个数字（但是我无法读取C＃，也无法检查它是否满足我的需求。我在Linux上，尝试使用单声道，但我遇到错误，我不知道如何工作C＃:(而且

Answer 1

该问题简化为0-1背包问题，您尝试在其中找到具有精确总和的集合。解决方案取决于约束条件，一般情况下，此问题是NP-
Complete。

但是，如果最大搜索总和（称为S）不太高，则可以使用动态编程解决问题。我将使用递归函数和备忘录对其进行解释，这比自下而上的方法更容易理解。

让我们对一个函数进行编码f(v, i, S)，以使其返回v[i:]恰好等于的子集数S。为了递归地解决它，首先我们必须分析基数（即：v[i:]为空）：

• S == 0：的唯一子集的[]总和为0，因此它是有效子集。因此，该函数应返回1。

• S！= 0：由于的唯一子集的[]总和为0，因此没有有效的子集。因此，该函数应返回0。

然后，让我们分析递归情况（即：v[i:]不为空）。有两种选择：将数字包括v[i]在当前子集中，或不包括。如果包含v[i]，那么我们正在寻找具有sum的子集S - v[i]，否则，我们仍在寻找具有sum的子集S。该功能f可以通过以下方式实现：

def f(v, i, S):
  if i >= len(v): return 1 if S == 0 else 0
  count = f(v, i + 1, S)
  count += f(v, i + 1, S - v[i])
  return count

v = [1, 2, 3, 10]
sum = 12
print(f(v, 0, sum))

通过检查f(v, 0, S) > 0，您可以知道是否有解决问题的方法。但是，此代码太慢，每个递归调用都产生两个新的调用，从而导致O（2 ^
n）算法。现在，我们可以应用备忘录以使其在时间O（n * S）中运行，如果S不是太大，它将更快：

def f(v, i, S, memo):
  if i >= len(v): return 1 if S == 0 else 0
  if (i, S) not in memo:  # <-- Check if value has not been calculated.
    count = f(v, i + 1, S, memo)
    count += f(v, i + 1, S - v[i], memo)
    memo[(i, S)] = count  # <-- Memoize calculated result.
  return memo[(i, S)]     # <-- Return memoized value.

v = [1, 2, 3, 10]
sum = 12
memo = dict()
print(f(v, 0, sum, memo))

现在，可以对g返回一个总和的子集的函数进行编码S。为此，仅在至少有一个包含元素的解决方案时才添加元素就足够了：

def f(v, i, S, memo):
  # ... same as before ...

def g(v, S, memo):
  subset = []
  for i, x in enumerate(v):
    # Check if there is still a solution if we include v[i]
    if f(v, i + 1, S - x, memo) > 0:
      subset.append(x)
      S -= x
  return subset

v = [1, 2, 3, 10]
sum = 12
memo = dict()
if f(v, 0, sum, memo) == 0: print("There are no valid subsets.")
else: print(g(v, sum, memo))

免责声明：此解决方案表示[10，10]有两个子集，总和为10。这是因为它假定前十个与后十个不同。可以将算法固定为假定两个十个相等（并因此回答一个），但这有点复杂。