Итак, логика заключается в обратной сортировке чисел, и предположим, что список чисел равен 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 .
Есть 2 возможных случая: либо i является частью суммы, либо нет.
Итак, мы предполагаем, что i является частью решения, и тогда проблема сводится к l , равному l[l.index(i+1):], и s , равному si , поэтому , если наша функция - (l, s), то мы вызываем a(l[l.index(i+1):] ,s-i). и если i не является частью s , тогда мы должны сформировать s из списка l[l.index(i+1):].
Таким образом, в обоих случаях это похоже, только изменение состоит в том, что если i является частью 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 мс, а предыдущий код также работает с отрицательными числами.
Так что я могу сделать некоторые улучшения.