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

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

该问题简化为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 countv = [1, 2, 3, 10]sum = 12print(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 = 12memo = 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 subsetv = [1, 2, 3, 10]sum = 12memo = dict()if f(v, 0, sum, memo) == 0: print("There are no valid subsets.")else: print(g(v, sum, memo))

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