用于查找列表中的哪个数字总和为特定数字的算法

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)不是太高,那么您可以使用动态编程解决问题.我将使用递归函数和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.这是因为它假设前十个与后十个不同.可以固定算法以假设两个十位相等(因此回答一个),但这有点复杂.

Answer 2

我知道自从你问这个问题 10 年后我才给出答案，但我真的需要知道如何做到这一点，而 jbernadas 的做法对我来说太难了，所以我用谷歌搜索了一个小时，我找到了一条蟒蛇itertools完成工作的图书馆！

我希望这对未来的新手程序员有所帮助。您只需要导入库并使用该.combinations()方法，就这么简单，它按顺序返回集合中的所有子集，我的意思是：

对于集合[1, 2, 3, 4]和长度为 3 的子集，它不会返回[1, 2, 3][1, 3, 2][2, 3, 1]它只会返回 [1, 2, 3]

如果你想要一个集合的所有子集，你可以迭代它：

import itertools

sequence = [1, 2, 3, 4]
for i in range(len(sequence)):
    for j in itertools.combinations(sequence, i):
        print(j)

输出将是

() (1,) (​​2,) (3,) (4,) (1, 2) (1, 3) (1, 4) (2, 3) (2, 4) (3, 4) (1) , 2, 3) (1, 2, 4) (1, 3, 4) (2, 3, 4)

希望这有帮助！