|
|
本帖最后由 灰袍法师 于 2012-10-17 23:36 编辑
好吧，这是个月经问题，不过此帖的算法虽然很简单，但是却貌似没有人在这里发表过。
先定义问题：
n个无记认的数字，以及一个和值X，要求选择若干个数字，其和等于X。
适用于无头账目的对账啦，凑发票去定额报销啦，似乎一直有财务人员深受困扰。
可惜的是，这属于NP完全问题，全世界都没有保证找到解的快速算法。
幸运的是，对于一些有利的情况，却可以快速找到解。
有利的意思是：
1 n很小，如不到25个，显然穷举全部可能性也就几秒钟不到。
2 等于指定和值的解非常非常多，几乎随便找25个数字都可以凑出来，显然这时候也就等于第一种情况。
3 只需要很少的几个数字就能凑出一个解，比如说，存在某一个解只是由3个数值相加，这时候显然只需要搜索 combin(n,3)
4 X很小 (本算法就是钻这个空子的，往下看吧)
先给出一个论坛以前的解决帖。
[开_86] 比速度,看谁的程序更快. by 彭希仁 顶以及 香川群子 94楼（更好的附件）
http://club.excelhome.net/thread-151178-1-1.html
此帖的算法是剪枝法，不断地搜索n个数字的所有和值，如果某个和值已经超过X，或者即使加上剩余的所有数值都不可能等于X，那么就不再搜索下去。
HHAAMM版主也做过一个一样算法的VBA，貌似山菊花，北方之狼都有做过，不一一给出连接了。
此算法的内存耗用是非常低的，因为只保存了n个数字的选择状态，可以忽略不计。
但是时间耗用却有可能非常高，一般而言是 combin(n,m)，m是相加等于X的数字个数，钻的是第2，3种有利情况的空子。
例如用25个10作为可选数值，那么
求解X=50 则相当于搜索 combin(25,5) 个组合
求解X=60 则相当于搜索 combin(25,6) 个组合
求解X=70 则相当于搜索 combin(25,7) 个组合
如果是25个随机数，而X的值大概等于随机数平均值的7倍，那么搜索全部解的运算时间也大概是 combin(25,7)
当然，如果不需要搜索全部解,而是找到一个解就算完成，那么碰到上述的第2，3种有利情况，就极有可能非常快找到解。
实际需要计算的数字也不会是均匀随机数，所以相当多的情况下(个人估计是90%)，此算法可以在十分钟甚至零点几秒就找到解。
需要特别指出的是，在以下三种情况同时存在的时候，此算法必定无效，运行时间等于死机。
首先，存在大量数值接近的可选数字，如1001,1005,1023等等几十个数字，在此情况下，会导致无法剪枝。
其次，X的值平均需要5个以上的数字相加才能得到(最坏情况是X接近可选数字的总和的一半)，这时候也无法剪枝，而 combin(n,5) 也是很大的组合，遍历一次的耗时是无法接受的。
最后，不属于第2种有利情况，也就是说，解的密度很低（最坏情况下是根本没有解，这时候必然遍历所有不能剪枝的组合）
举例来说，如果给出25个随机整数，然后指定X = 任意12个随机整数的和 + 0.1 (保证不存在解)
那么此算法就大概需要搜索 combin(25,12) = 5百多万个组合，而随着n的增加，此数字将大概等于 combin(n,12)，n=30 的时候就已经是无法接受了。
因此，此算法的速度跟X的大小，可选数字的均匀程度，以及可选数字的平均值，可选数值的数量都有关系。
一般来说，很适合用于计算 50-200个可选数字，而且X不算很大的情况。
.......................................唉，说清楚一样东西真要花不少力气，以下接着说我在这里的算法和附件
这个算法一点都不高明，一些算法入门书都会简单介绍，因为实在是非常简单。
不过要做成实用的VBA程序，也花了我不少时间，主要是设计一个高速的哈希查找实在不容易，这算法要对千万级别的数值进行数亿次查询。
本附件算法根据是： 虽然n个可选数值的所有组合数是 2^n, 但是，和值的可能组合只有 0 到 n个数值的总和
如25个1求X=12，虽然组合总数是2^25，而且等于12的组合总数是combin(25,12)，但是所有可能的和值只有26个！！！
也就是 0,1,2,3,4,5,6,7......23,24,25
因此，只需要从所有已知的和值出发去搜索，而不需要从所有可选数字的组合去搜索
算法如下:
1 设置已知和值的数组 =[0]
2 把第一个可选数字加到已知和值的每一个元素上，形成新的已知和值数组 [0,1]
3 把剩下的所有可选数字，如同第2步逐一加到此数组，如果生成的和值已经存在，那么就合并为一个，那么依次会得到以下数组
[0,1,2]
[0,1,2,3]
[0,1,2,3,4]
......
[0,1,2,3,4,5......25]
我们把等于12的数组的合并次数拿出来，就是25个数字选取若干个，等于12的所有组合总数了！
很显然，此算法的时间耗用是O(n * c )， c = 已知的最大和值
因为对于每一个可选数字，都需要跟已知的所有和值相加，然后和并，然后剪掉超过X的和值
如 1,2,3,4,......100 这100个数字，求X＝2025.01 (无解)
那么此算法的时间耗用最多是 100 * 2026 = 202600 非常快就可以找到解
对比上面剪枝算法的 combin(100,30) 的时间耗用，快了无数倍
但是，这个合并算法缺点是内存占用非常高，因为需要在内存保留所有的和值
最坏情况下，假如可选数字是 1,2,4,8,16.....2^n，那么就需要保存 2^(n+1)个数值
按n=25，long类型4字节来算，需要 2^26 * 4 / 1048576 = 512MB内存
如果再多几个这样不断翻倍的数字，那么内存耗用也不断翻倍,30个数字将占用8GB内存。
幸好，一般需要计算的数字范围不会有2^30次方这么大，而不幸的是，一般需要计算的数字都带两位小数
所以，要保存1000万大小的数字，带两位小数，需要10亿个数组元素，这已经是1GB内存了。
因此，在最多耗用1GB内存的前提下，这个算法几乎是不能计算超过1000万大小的数字，除非可选数字的数目同时低于28个
即最多只有 2^28个和值，2^28 * 4 / 1048576 = 1GB
实际上由于，合并和值的时候，需要快速查询已有的和值是哪些，所以1GB内存还要分作两块用
在最坏的情况下，此算法只能计算大概25个任意可选数字。
最好的情况下，指定的和值X很小，如不到1万，那么即使是1000个可选数值，也很容易算完。
总而言之：
此算法最大问题是内存，因为几乎必定需要保存数组 [0,1,2,.....X]，X太大就会不够内存。
而对于X很小的情况，此算法速度非常快。非常适合计算X的值小于100万的情况。
说完了算法的优缺点，下面说一下具体的VBA实现
附件的VBA先检测电脑的连续内存有多大，以此决定最多可以保存多少个已知和值
然后逐一生成所有的可能和值，并且把可能的和值保存为哈希表，以便合并的时候快速查找（用VBA字典的话，代码会简单得多，但是速度太慢无法接受）
最后，把符合指定和值范围的计算结果，按从大到小的顺序输出到工作表。
进一步简单地举例，已知可选数字 2,2,4，求X=6
这个VBA程序把计算过程看作是展开多项式 (1+x^2)*(1+x^2)*(1+x^4) (注释：展开多项式后，每一项的次数就是和值，系数就是和值的组合总数)
然后看 x^6这一个项的系数是多少，这个系数就是所有等于6的组合的总数了。
(1+x^2) 等价于 把2加到已知和值数组 [0] 得到 [0,2]，对应的系数数组 [1,1]
乘以(1+x^2) 得到 1+2*x^2+x^4，等价于 把2加到上面的已知和值数组得到 [0,2,4]，对应的系数数组 [1,2,1]
乘以(1+x^4) 得到 1+2*x^2+2*x^4+2*x^6+x^8 等价于 把4加到已知和值数组得到 [0,2,4,6,8],，对应的系数数组 [1,2,2,2,1]
所以 2,2,4求相加=6，组合数一共有2种。(同理可以看出相加=4的组合数也是2种，等于8的组合数是1种)
附件是我随便找的一组数据，特别偏心这个算法，用剪枝算法的耗时和Lingo软件求解，都会大大超过合并算法。
当然，这只能说明不同的算法有不同的弱点，一般来说，
Lingo求解都是最快的，缺点是安装Lingo麻烦，而碰到不利情况(<0.1%)也会耗费几个小时
其次是彭希仁版主 和 香川群子的剪枝法，缺点是碰到不利情况(<10%)等于死机，根本无法知道最后能不能解出来。
而这个合并算法由于内存容量限制，反倒一定可以在十分钟计算完毕，而且X不超过10万的时候必定找到解，X太大则很可能找不到解。
最后，附件的求组合总数，很有力地说明了这一类问题要列举全部组合几乎是不可能的
一般随便指定一个和值，都有几万个组合，有时候甚至会达到几万亿，这时候很容易找到解，但是很难列出全部解
而解的数目少到可以全部列出的时候，解的密度就会太低，结果就是找一个解都很困难。
[ 本帖最后由 灰袍法师 于 2011-5-19 23:13 编辑 ]
补充内容 (2013-11-30 18:36):
本帖第 54 楼，有香川群子 女侠最新的VBA，速度非常快，强烈推荐。
补充内容 (2014-1-1 20:19):
再次强烈推荐，香川群子女侠最新贴：2014新年元旦第一强帖：实用凑数凑金额高效递归剪枝算法
http://club.excelhome.net/thread-1085112-1-1.html
|
评分
-
3
查看全部评分
-
|
[复制链接]
沪公网安备 31011702000001号 沪ICP备11019229号-2
发表于 2011-3-3 19:13
楼主
