所以,逻辑是对数字进行反向排序,假设数字列表是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。有两种可能的情况,我是否是 sum 的一部分。因此,我们假设i是解决方案的一部分,然后问题简化为l存在l[l.index(i+1):]
且s存在si所以,如果我们的函数是 a(l,s),那么我们调用a(l[l.index(i+1):] ,s-i)
。如果i不是s的一部分,那么我们必须从列表中形成s 。l[l.index(i+1):]
所以在这两种情况下都是相似的,唯一的变化是如果 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]
和
s=2000
我的循环运行了 1018 次和 31 毫秒。
之前的代码循环运行了 3415587 次,耗时近 16 秒。
但是,如果解决方案不存在,我的代码运行了几分钟以上,所以我停止了它,之前的代码仅在 17 毫秒左右运行,并且之前的代码也适用于负数。
所以我觉得可以做一些改进。