用PQ来解决凑数问题。

questionsome

渡渡orz 发表于 2021-10-21 20:49
水一题

最难的几个函数基本都汇集在了这个例子

大公驴

楼主，错误提示:5参数传递到了一个函数，该函数应介于2和4之间。

weiyt307

渡渡orz 发表于 2021-10-21 20:49
水一题

表1的内容是什么?20089吗?但是好像又不对

14820103

渡渡orz 发表于 2021-10-21 20:49
水一题

大神出手

luzwales

这个数据多了，超级慢，如果是有序列表，算法上会不会优化？

踏破拖鞋

看起来好复杂，EXCEL自带的 规划求解可以完成，或者E灵的 智能凑数  也可完成。

luzwales

这是个算法题，如果数据多了， 你这种算法慢的一比！
算法中的动态规划 专门解决此类问题的！

luzwales

用python自己的方法 写了一个通过列表，和需要得到的数据，性能比一般的是要快点，数字越大几乎成指数增加，不知道有没有更改的方法，动态规划除外。

1. import time
   
2. global prelst
   
3. global prelst
   
4. reslst = []
   
5. prelst = []
   
6. 
   
7. def seachbi(li, val):
   
8.     left = 0
   
9.     right = len(li)-1
   
10.     maxli = li[-1]
    
11.     minli = li[0]
    
12.     if val>maxli or val<minli:
    
13.         return None
    
14.     else:
    
15.         while left<=right:
    
16.             mid = left+(right-left)//2
    
17.             if li[mid]==val:
    
18.                 return mid
    
19.             elif li[mid]>val:
    
20.                 right = mid-1
    
21.             else:
    
22.                 left = mid+1
    
23.         else:
    
24.             return None         
    
25.         
    
26. 
    
27. def listSumEqual(prelst, lst, equalsum,num):
    
28.     if num ==1:
    
29.         if seachbi(lst,equalsum) != None:
    
30.             templst = prelst.copy()
    
31.             new = lst[seachbi(lst,equalsum)]            
    
32.             templst.append(new)
    
33.             reslst.append(templst)
    
34.     elif num == 2:
    
35.         for i in range(len(lst)-1):
    
36.             templst = prelst.copy()
    
37.             templst.append(lst[i])
    
38.             equalsuma = equalsum - sum(templst)            
    
39.             seresult = seachbi(lst[i+1:],equalsuma)
    
40.             if seresult != None:
    
41.                 new = lst[i+1:][seachbi(lst[i+1:],equalsuma)]
    
42.                 templst.append(new)
    
43.                 reslst.append(templst)
    
44.             else:
    
45.                 break
    
46.     else:
    
47.         for i in range(len(lst)-num+1):
    
48.             prelst.append(lst[i])
    
49.             listSumEqual(prelst, lst[i+1:], equalsum, num-1)
    
50.             prelst.pop()
    
51.     # return reslst
    
52. 
    
53. def filterlst(lst,sum):
    
54.     for i in range(len(lst)):
    
55.         if lst[i] > sum:
    
56.             return lst[:i]
    
57. 
    
58. if __name__ == "__main__":   
    
59.     lst = list(range(1,100,1))   
    
60.     equalsum = int(input("Please input Sum Number:"))
    
61.     t1 = time.time()
    
62.     lst = filterlst(lst,equalsum)
    
63.     length = len(lst)
    
64.     for num in range(1,length):
    
65.         if sum(lst[:num]) > equalsum:
    
66.             print("no match data")
    
67.             break
    
68.         else:
    
69.             prelst = []
    
70.             listSumEqual(prelst, lst, equalsum, num)  
    
71.     t2 = time.time()
    
72.     print("It cost %s second time!"%(t2-t1))
    
73.    

复制代码

但这个比使用intertools.combinations 是要快100倍以上！

1. from time import time
   
2. from  itertools import combinations
   
3. lst = list(range(1,100))
   
4. num = int(input("Please input sum data:"))
   
5. lstfilter = list(filter(lambda x:x<=num,lst))
   
6. t1 = time()
   
7. res = []
   
8. for r in range(len(lstfilter)):
   
9.     bn = combinations(lst, r)
   
10.     for b in bn:
    
11.         if sum(b)==30:
    
12.             if b not in res:
    
13.                 res.append(b)
    
14. t2 = time()
    
15. print("it cost %s time"%(t2-t1))

复制代码

加菲猫是笨蛋

楼主，你的公式有没有优化版本啊？
如果将数据源更改到40行，刷新后pq直接崩溃。。。
谢了

加菲猫是笨蛋

weiyt307 发表于 2021-12-20 16:50
表1的内容是什么?20089吗?但是好像又不对

即使表1是 20089
我按他的代码在pq里尝试运行，不过一直卡。