查找列表中哪个数字总和达到某个数字的算法

Question

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

示例

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

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

Answer 1

这个问题简化为0-1背包问题，您试图找到一个带有确切的总和。解决方案取决于约束条件，一般情况下该问题是 NP 完全问题。

但是，如果最大搜索和（我们称之为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。这是因为它假设前 10 个是与后十不同。该算法可以固定为假设两个十都相等（因此答案为一），但这有点复杂。

Answer 2

我知道自从你问这个问题以来我会在 10 年后给出答案，但我真的需要知道如何做到这一点，而 jbernadas 的方式对我来说太难了，所以我用谷歌搜索了一个小时，我找到了一个 python库 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)

希望对您有所帮助！

Answer 3

所以，逻辑是对数字进行反向排序，假设数字列表是l，要形成的和是s。

   for i in b:
            if(a(round(n-i,2),b[b.index(i)+1:])):
                r.append(i)    
                return True
        return False

然后，我们经历这个循环，并按顺序从 l 中选择一个数字，假设它是 i 。
有两种可能的情况：i 是 sum 的一部分，或者不是 sum 的一部分。
因此，我们假设 i 是解决方案的一部分，然后问题简化为 l 为 l[l.index(i+1):] 和 s 是 si 所以，如果我们的函数是 a(l,s) 那么我们调用 a(l[l.index(i+1))： ] ,si)。如果 i 不是 s 的一部分，那么我们必须从 l[l.index(i+1) 形成 s :] 列表。
所以这两种情况都是相似的，唯一的变化是如果 i 是 s 的一部分，则 s=si ，否则仅 s=s 。

现在为了减少问题，如果 l 中的数字大于 s，我们将删除它们以降低复杂性，直到 l 为空，在这种情况下，选择的数字不是我们解决方案的一部分，我们返回 false。

if(len(b)==0):
    return False    
while(b[0]>n):
    b.remove(b[0])
    if(len(b)==0):
        return False    

如果 l 只剩下 1 个元素，那么它要么可以是 s 的一部分，然后我们返回 true，要么不是，然后我们返回 false，循环将遍历其他数字。

if(b[0]==n):
    r.append(b[0])
    return True
if(len(b)==1):
    return False

请注意循环中是否使用了b..但b只是我们的列表。并且我已经在可能的地方进行了四舍五入，这样我们就不会因为python中的浮点计算而得到错误的答案。

r=[]
list_of_numbers=[61.12,13.11,100.12,12.32,200,60.00,145.34,14.22,100.21,14.77,214.35,200.32,65.43,0.49,132.13,143.21,156.34,11.32,12.34,15.67,17.89,21.23,14.21,12,122,134]
list_of_numbers=sorted(list_of_numbers)
list_of_numbers.reverse()
sum_to_be_formed=401.54
def a(n,b):
    global r
    if(len(b)==0):
        return False    
    while(b[0]>n):
        b.remove(b[0])
        if(len(b)==0):
            return False    
    if(b[0]==n):
        r.append(b[0])
        return True
    if(len(b)==1):
        return False
    for i in b:
        if(a(round(n-i,2),b[b.index(i)+1:])):
            r.append(i)    
            return True
    return False
if(a(sum_to_be_formed,list_of_numbers)):
    print(r)

该解决方案工作速度很快。比上面解释的解决方案更快。
然而，这仅适用于正数。
然而，如果只有一个解决方案，它也能很好地工作，否则需要很长时间才能摆脱循环。

一个运行的例子是这样的，我们

    l=[1,6,7,8,10]

and s=22 i.e. s=1+6+7+8
so it goes through like this 

1.) [10, 8, 7, 6, 1] 22
i.e. 10  is selected to be part of 22..so s=22-10=12 and l=l.remove(10)
2.) [8, 7, 6, 1] 12
i.e. 8  is selected to be part of 12..so s=12-8=4 and l=l.remove(8)
3.) [7, 6, 1] 4  
now 7,6 are removed and 1!=4 so it will return false for this execution where 8 is selected.
4.)[6, 1] 5
i.e. 7  is selected to be part of 12..so s=12-7=5 and l=l.remove(7)
now 6 are removed and 1!=5 so it will return false for this execution where 7 is selected.
5.)[1] 6
i.e. 6  is selected to be part of 12..so s=12-6=6 and l=l.remove(6)
now 1!=6 so it will return false for this execution where 6 is selected.
6.)[] 11
i.e. 1 is selected to be part of 12..so s=12-1=1 and l=l.remove(1)
now l is empty so all the cases for which 10 was a part of s are false and so 10 is not a part of s and we now start with 8 and same cases follow.
7.)[7, 6, 1] 14
8.)[6, 1] 7
9.)[1] 1

只是为了进行比较，我在我的计算机上运行的结果不太好。
使用

l=[61.12,13.11,100.12,12.32,200,60.00,145.34,14.22,100.21,14.77,214.35,145.21,123.56,11.90,200.32,65.43,0.49,132.13,143.21,156.34,11.32,12.34,15.67,17.89,21.23,14.21,12,122,134]

and

s=2000

我的循环运行了 1018 次，耗时 31 毫秒。

之前的代码循环运行了 3415587 次，花费了近 16 秒。

但是，如果不存在解决方案，我的代码运行了超过几分钟，所以我停止了它，之前的代码只运行了大约 17 毫秒，之前的代码也适用于负数。

所以我认为可以做一些改进。

Answer 4

#!/usr/bin/python2

ylist = [1, 2, 3, 4, 5, 6, 7, 9, 2, 5, 3, -1]
print ylist 
target = int(raw_input("enter the target number")) 
for i in xrange(len(ylist)):
    sno = target-ylist[i]
    for j in xrange(i+1, len(ylist)):
        if ylist[j] == sno:
            print ylist[i], ylist[j]

这个Python代码按照你的要求执行，它将打印唯一的数字对，其总和等于目标变量。

if target number is 8, it will print: 
1 7
2 6
3 5
3 5
5 3
6 2
9 -1
5 3

Answer 5

我找到了一个答案，其运行时复杂度为 O(n)，空间复杂度约为 O(2n)，其中 n 是列表的长度。

答案满足以下约束：

1. 列表可以包含重复项，例如 [1,1,1,2,3] 并且您想要查找总和为 2 的对

2. 列表可以包含正整数和负整数

代码如下，后面是解释：

def countPairs(k, a):
    # List a, sum is k
    temp = dict()
    count = 0
    for iter1 in a:
        temp[iter1] = 0
        temp[k-iter1] = 0
    for iter2 in a:
        temp[iter2] += 1
    for iter3 in list(temp.keys()):
        if iter3 == k / 2 and temp[iter3] > 1:
            count += temp[iter3] * (temp[k-iter3] - 1) / 2
        elif iter3 == k / 2 and temp[iter3] <= 1:
            continue
        else:
            count += temp[iter3] * temp[k-iter3] / 2
    return int(count)

1. 创建一个空字典，迭代列表并将所有可能的键放入字典中，初始值为0。
   请注意，键（k-iter1）是必须指定的，例如，如果列表包含1但不包含4，并且总和是5。那么当我们查看1时，我们想知道我们有多少个4，但如果 4 不在字典中，则会引发错误。
2. 再次遍历列表，计算每个整数出现的次数并将结果存储到字典中。

3. 迭代字典，这次是为了找出我们有多少对。我们需要考虑3个条件：

   3.1 key 只是 sum 的一半，并且该 key 在列表中出现多次，例如 list 是 [1,1,1]，sum 是 2。我们将这种特殊情况视为代码的作用。< /p>

   3.2 key只是总和的一半，并且这个key在列表中只出现一次，我们跳过这个条件。

   3.3 对于其他情况，键不是总和的一半，只需将其值与另一个键的值相乘，其中这两个键的总和为给定值。例如，如果 sum 是 6，我们将 temp[1] 和 temp[5]、temp[2] 和 temp[4] 相乘，等等...（我没有列出数字为负数的情况，但想法是相同的。 )

最复杂的步骤是步骤 3，其中涉及搜索字典，但由于搜索字典通常很快，因此复杂性几乎恒定。 （虽然最坏的情况是 O(n)，但对于整数键不应该发生。）因此，假设搜索的复杂度是恒定的，总复杂度是 O(n)，因为我们只单独迭代列表多次。

欢迎提出更好的解决方案的建议:)