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

codexq

香川群子 发表于 2014-7-5 10:14
我的程序是实用化的，并不是你想象的那么简单。

如果只需要得到1个解，那么设置求解个数=1即可。

其实根本就没必要求出所有解，假设现在有50个数据，他们的排列组合是2^50（不剔除重复），也就是1千万亿个。面对这么庞大的数字，只要你用的是搜索算法（你现在是深度优先搜索），即使你剪枝多么厉害，程序的复杂度肯定上万亿。目前的技术根本就不可以实现。事实上你用CNT和解的数目了限制了复杂度。试想对于50个数字，他们的和最多就1亿，算上2个小数位我就当他100亿，但现在你有2^50个排列，也就是说现在随便举一个数，平均就有上十万个解。把所有解算出来一方面是不可能的（搜索算法是不行的，除非你用数论），另外一方面也不太实际（你把上几十万个解扔给人家也没意义）。

我看了一下彭版的算法，没仔细研究估计是用while循环的广搜。其实在复杂度一样的情况下，广搜是优于深搜的，毕竟递归这东西会影响效率的。

codexq

codexq 发表于 2014-7-7 13:49
其实根本就没必要求出所有解，假设现在有50个数据，他们的排列组合是2^50（不剔除重复），也就是1千万亿个 ...

嘛，其实我想说的是，这个程序如果数据量超过20那就没什么意义了。2^30都已经上百亿了，肯定会产生一大堆解的，实务中没有意义。

香川群子

codexq 发表于 2014-7-7 14:10
嘛，其实我想说的是，这个程序如果数据量超过20那就没什么意义了。2^30都已经上百亿了，肯定会产生一大堆 ...

我想说的是，你对我本帖的程序功能和用处一点也不了解……

你所说的一切我都明白，不需要你来再告诉我一遍……以为我是小学生什么都不懂么，呵呵。

香川群子

codexq 发表于 2014-7-7 14:10
嘛，其实我想说的是，这个程序如果数据量超过20那就没什么意义了。2^30都已经上百亿了，肯定会产生一大堆 ...

我想说的是，你对我本帖的程序功能和用处一点也不了解……

你所说的一切我都明白，不需要你来再告诉我一遍……以为我是小学生什么都不懂么，呵呵。

ghostjiao

支持，前来来学习一下。我递归一直都学不明白...
大爱香川老师，嘿嘿

Blenderama

香川老师，目前我看到的算法，在小数凑大数的时候都会死机，比如这个程序我用0.1到9.5步长0.1的一列数字来凑70……有没有能够解这种极端问题的算法呢？或者至少不要嵌套这么多循环导致死机？

香川群子

Blenderama 发表于 2014-7-15 13:26
香川老师，目前我看到的算法，在小数凑大数的时候都会死机，比如这个程序我用0.1到9.5步长0.1的一列数字来凑 ...

你的问题【0.1到9.5步长0.1的一列数字来凑70】
完全等效于【1到95  凑700】

计算耗时很长，疑似死机，是因为组合结果数太多、太多：

m = 1 - 95 組合計算 s = 0
求和範囲 h = 700 to 700
n= 8     cnt=3,319
n= 9     cnt=10,601,408
n= 10     cnt=1,304,868,206
n= 11     cnt=50,208,946,674
n= 12     cnt=950,551,914,512
n= 13     cnt=10,768,434,422,248
n= 14     cnt=81,235,145,098,915
n= 15     cnt=435,953,534,475,846
n= 16     cnt=1,739,080,829,837,507
n= 17     cnt=5,316,822,227,264,900
n= 18     cnt=12,732,011,998,801,758
n= 19     cnt=24,257,300,177,172,513
n= 20     cnt=37,178,100,997,971,440
n= 21     cnt=46,180,754,854,047,954
n= 22     cnt=46,696,145,344,726,659
n= 23     cnt=38,503,136,475,068,361
n= 24     cnt=25,866,994,813,121,985
n= 25     cnt=14,110,588,955,181,914
n= 26     cnt=6,211,399,974,681,113
n= 27     cnt=2,185,596,197,169,039
n= 28     cnt=606,539,216,665,453
n= 29     cnt=130,318,229,978,298
n= 30     cnt=21,130,713,135,218
n= 31     cnt=2,494,997,260,931
n= 32     cnt=203,741,548,568
n= 33     cnt=10,638,857,983
n= 34     cnt=312,082,732
n= 35     cnt=4,021,598
n= 36     cnt=12,310
全部 262,267,589,888,939,362 個解。

即超过26亿亿个组合解。
……

解决办法是，你如果只需要其中一些解，那么直接输入求解个数 例如=1000个，那结果很快就出来了。

或者指定元素个数=8 To 12 ，并指定计算深度=128(2^7)，那样的话部分结果=3080组解，只要0.02秒就出来了。

lolmuta

完全看不懂，

不过要是有一个已取过的数字即不能再取的功能就更好了…

Blenderama

香川群子 发表于 2014-7-15 15:25
你的问题【0.1到9.5步长0.1的一列数字来凑70】
完全等效于【1到95  凑700】

大谢！实际应用中确实应该这样做～

香川群子

lolmuta 发表于 2014-7-15 17:29
完全看不懂，

不过要是有一个已取过的数字即不能再取的功能就更好了…

这个问题我也已经研究过了……但是不太容易得到最优解。

即不容易找到剩余个数最少的方案。

但是一般的应用应该没问题。如果你有实际例子，我可以帮你单独写个应用程序，
而通用的程序，要等我有时间整理好以后再发表。