查找列表中哪个数字和某个数字相加的算法 [英] Algorithm to find which number in a list sum up to a certain number

问题描述

我有一个数字列表.我也有一定的数目.总和是由我列表中的几个数字组成的(我可能/可能不知道它是由多少个数字组成的).是否有一种快速算法来获取可能的数字列表?用 Python 编写会很棒，但伪代码也很好.(除了 Python 之外，我什么都读不懂:P)

I have a list of numbers. I also have a certain sum. The sum is made from a few numbers from my list (I may/may not know how many numbers it's made from). Is there a fast algorithm to get a list of possible numbers? Written in Python would be great, but pseudo-code's good too. (I can't yet read anything other than Python :P )

示例

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

注意:我知道 从大小为 n 的列表中找出哪些数字与另一个数字相加的算法(但我无法阅读 C#，也无法检查它是否适用于我的需要.我在 Linux 上，我尝试使用 Mono，但出现错误，我无法弄清楚如何使用 C# :(
和我确实知道总结所有组合的数字列表的算法(但似乎效率相当低.我不需要所有组合.)

NOTE: I do know of Algorithm to find which numbers from a list of size n sum to another number (but I cannot read C# and I'm unable to check if it works for my needs. I'm on Linux and I tried using Mono but I get errors and I can't figure out how to work C# :(
AND I do know of algorithm to sum up a list of numbers for all combinations (but it seems to be fairly inefficient. I don't need all combinations.)

推荐答案

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

This problem reduces to the 0-1 Knapsack Problem, where you are trying to find a set with an exact sum. The solution depends on the constraints, in the general case this problem is NP-Complete.

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

However, if the maximum search sum (let's call it S) is not too high, then you can solve the problem using dynamic programming. I will explain it using a recursive function and memoization, which is easier to understand than a bottom-up approach.

让我们编写一个函数 f(v, i, S)，这样它就会返回 v[i:] 中子集的数量，正好等于 >S.要递归求解，首先我们要分析基数(即:v[i:] 为空):

Let's code a function f(v, i, S), such that it returns the number of subsets in v[i:] that sums exactly to S. To solve it recursively, first we have to analyze the base (i.e.: v[i:] is empty):

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

• S == 0: The only subset of [] has sum 0, so it is a valid subset. Because of this, the function should return 1.

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

S != 0: As the only subset of [] has sum 0, there is not a valid subset. Because of this, the function should return 0.

那么，我们来分析递归情况(即:v[i:] 不为空).有两种选择:在当前子集中包含数字v[i]，或者不包含它.如果我们包含 v[i]，那么我们正在寻找具有和 S - v[i] 的子集，否则，我们仍然在寻找具有 sum 的子集S.函数 f 可以通过以下方式实现:

Then, let's analyze the recursive case (i.e.: v[i:] is not empty). There are two choices: include the number v[i] in the current subset, or not include it. If we include v[i], then we are looking subsets that have sum S - v[i], otherwise, we are still looking for subsets with sum S. The function f might be implemented in the following way:

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 不是太大，则更快:

By checking f(v, 0, S) > 0, you can know if there is a solution to your problem. However, this code is too slow, each recursive call spawns two new calls, which leads to an O(2^n) algorithm. Now, we can apply memoization to make it run in time O(n*S), which is faster if S is not too big:

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 求和的子集.为此，仅当存在至少一种包含元素的解决方案时才添加元素就足够了:

Now, it is possible to code a function g that returns one subset that sums S. To do this, it is enough to add elements only if there is at least one solution including them:

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 的子集.这是因为它假设前十个与后十个不同.该算法可以固定为假设两个十位相等(因此回答一个)，但这有点复杂.

Disclaimer: This solution says there are two subsets of [10, 10] that sums 10. This is because it assumes that the first ten is different to the second ten. The algorithm can be fixed to assume that both tens are equal (and thus answer one), but that is a bit more complicated.

这篇关于查找列表中哪个数字和某个数字相加的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！