求一个列表中哪一个数字和某个数字的算法

这个问题归结为 0-1 Knapsack Problem ,试图找到一个具有精确和的集合。解取决于约束条件,在一般情况下,这个问题是NP完全问题。

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

让我们编写一个函数的代码 f(v, i, S) ,以便返回 v[i:] 这就等于 S . 为了递归地解决它,首先我们必须分析基(即: V〔I:〕 是空的):

• S==0:唯一的子集 [] 有和0,所以它是有效的子集。因此,函数应返回1。

• S!=0:作为 [] 有SUM 0,没有有效的子集。因此,函数应返回0。

然后,让我们分析递归情况(即: V〔I:〕 不是空的)。有两种选择:包括数字 v[i] 在当前子集中,或不包括它。如果我们包括 V[I] ,那么我们要查找具有和的子集 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 count

v = [1, 2, 3, 10]
sum = 12
print(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 = 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。这是因为它假定前十个不同于后十个。该算法可以固定为假定两个十位数相等(因此回答一个十位数),但这有点复杂。

所以,逻辑是对数字进行反向排序,假设数字列表是 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 有条不紊地说是 我 . 可能有两种情况 我 是不是和的一部分。 所以,我们假设 我 是解决方案的一部分,然后问题减少到 L 存在 l[l.index(i+1):] 和 S 存在 S-Ⅰ 所以,如果我们的函数是a(l,s),那么我们调用 a(l[l.index(i+1):] ,s-i) . 如果 我 不属于 S 那我们就得组成 S 从 L[L.指数(I+1):] 名单。 所以这两种情况都很相似,唯一的变化是,如果我是s的一部分,那么s=s-i,否则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]

和

S=2000

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

之前的代码循环运行了3415587次,大约需要16秒。

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

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

#!/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

我找到了一个答案,其中运行时复杂度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的dict中。 请注意,需要指定键(k-iter1),例如,如果列表包含1但不包含4,并且总和为5。然后,当我们看1时,我们想知道我们有多少4个,但是如果4不在口述中,那么它将产生一个错误。
2. 再次遍历列表,并计算每个整数发生的次数,并将结果存储到dict。

3. 重复一遍dict,这次是为了找出我们有多少对。我们需要考虑3个条件:

   3.1键仅为和的一半,并且该键在列表中出现多次,例如,列表为[1,1,1],和为2。我们将这个特殊条件视为代码的作用。

   3.2键只是和的一半,这个键在列表中只出现一次,我们跳过这个条件。

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

最复杂的步骤是步骤3,它涉及到搜索字典,但是由于搜索字典通常很快,几乎是恒定的复杂性。(尽管最坏的情况是O(n),但对于整数键不应该发生。)因此,假设搜索是恒定的复杂性,总的复杂性是O(n),因为我们只分别迭代列表多次。

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