2014新年元旦第一强帖：实用凑数凑金额高效递归剪枝算法

nikky

香川裙子，高手啊，这个算法太强悍了！

hrbxpj

香川裙子老师，您太让我崇拜了，我心中的伟人。

zfq2100

厉害了，下载来试试看

lby0712

  2014-1-2 10:28
Чн

м1-100= ...

It takes several hours without solutions?

香川群子

lby0712 发表于 2017-4-15 07:10
It takes several hours without solutions?

你造出来的这个例子，有点离谱了。

事实上，你的原始数据，是从10-71的61个连续整数，意味着几乎所有的计算都是可行的。
所以，程序无法进行有效剪枝，所以计算量会超级大。

如果计算21个数总和=590的话，那么理论上组合解有36,035,846,198个。
即有360亿之多。

由于之前的所有计算也都需要遍历进行，所以你的结果，普通计算机大概要计算一个月。哈哈哈。

香川群子

lby0712 发表于 2017-4-15 07:10
It takes several hours without solutions?

全部连续整数的话，求和只需用随机程序计算，大约平均17万次计算可以得到一组解。

1. Sub test()
   
2.     Dim a&(), h&, i&, j&, k&, m&, n&, r&, s&, t&, tms#
   
3.     tms = Timer
   
4.    
   
5.     h = 590 '设定求和目标值
   
6.    
   
7.     m = 61  '设定数据个数
   
8.     ReDim a(m - 1)
   
9.     For i = 0 To m - 1
   
10.         a(i) = i + 10
    
11.     Next
    
12.     '以上生成10-70的61个连续整数作为原始数据   
    
13. 
    
14.     n = 21 '设定求和个数n
    
15.     Do
    
16.         k = k + 1
    
17.         Randomize
    
18.         s = 0
    
19.         For i = 0 To n - 1
    
20.             r = Int(Rnd * (m - i)) + i
    
21.             t = a(r): a(r) = a(i): a(i) = t: s = s + t
    
22.         Next
    
23.         If s = h Then Exit Do
    
24.     Loop
    
25.     '以上随机乱序并求前n个数的总和s 满足=目标值h 时结束
    
26. 
    
27.     MsgBox Format(Timer - tms, "0.000s ") & k
    
28.    
    
29.     For i = 0 To n - 1
    
30.         Cells(i + 1, 1) = a(i) '在A列输出结果
    
31.     Next
    
32. End Sub

复制代码

这样大约1秒左右有一组解。

香川群子

lby0712 发表于 2017-4-15 07:10
It takes several hours without solutions?

你的例子，全部组合=Combin(61,21)=12176310231149300 相当于1亿亿个组合。

我用随机算法得到一组解：
10,11,13,14,15,17,18,19,20,22,24,27,33,34,38,39,40,42,47,52,55

这个组合是第 458662650820521 个组合。需要计算到460万亿次才会得到结果。

lby0712

香川群子 发表于 2017-4-15 10:43
全部连续整数的话，求和只需用随机程序计算，大约平均17万次计算可以得到一组解。

I think your program is the best!........!

lby0712

香川群子 发表于 2017-4-15 10:51
你的例子，全部组合=Combin(61,21)=12176310231149300 相当于1亿亿个组合。

我用随机算法得到一组解： ...

I think the members =21 can save a lot of time

香川群子

lby0712 发表于 2017-4-15 10:52
I think your program is the best!........!

直接凑数更简单，5秒钟

10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,36,67,68,69,70

首先填写：
10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30=420...还差-170

然后依次倒序把最后一个数改成最大值
10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,70=460...还差-130
10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,69,70=500...还差-90
10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,68,69,70=540...还差-50
10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,67,68,69,70=580...还差-10

所以把最后的26改为36即可：
10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,36,67,68,69,70=590...满足总和=590

以上。