python - 查找列表中哪个数字总和等于某个数字的算法

Question

我有一个数字列表。我也有一定数额。总和是由我列表中的几个数字组成的(我可能/可能不知道它是由多少个数字组成的)。是否有一种快速算法来获取可能的数字列表？用 Python 编写会很棒，但伪代码也很好。 (除了 Python 之外，我还无法阅读任何内容:P)

例子

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

注意:我知道 Algorithm to find which numbers from a list of size n sum to another number (但我无法阅读 C#，也无法检查它是否满足我的需要。我在 Linux 上尝试使用 Mono，但出现错误，我不知道如何使用 C# :(
AND 我知道 algorithm to sum up a list of numbers for all combinations (但它似乎效率很低。我不需要所有组合。)

Answer 1

这个问题简化为 0-1 Knapsack Problem ，您试图找到一个具有精确总和的集合。解决方案取决于约束条件，一般情况下这个问题是 NP-Complete。

但是，如果最大搜索和(我们称之为S)不是太高，那么你可以使用动态规划来解决这个问题。我将使用递归函数和 memoization 来解释它。 ，这比自下而上的方法更容易理解。

让我们编写一个函数 f(v, i, S)，使其返回 v[i:] 中的子集数，该数与 相加>S。要递归求解，首先我们要分析基数(即:v[i:] 为空):

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

• S != 0:由于 [] 的唯一子集总和为 0，因此不存在有效子集。因此，该函数应返回 0。

那么，我们来分析递归的情况(即:v[i:]不为空)。有两种选择:在当前子集中包含数字 v[i]，或者不包含它。如果我们包含 v[i]，那么我们正在寻找总和为 S - v[i] 的子集，否则，我们仍在寻找总和为 的子集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) 算法。现在，我们可以申请memoization使其运行时间为 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。这是因为它假设前十个与后十个不同。该算法可以固定为假设两个十位相等(因此回答一个)，但这有点复杂。