ExcelHome技术论坛

 找回密码
 免费注册

QQ登录

只需一步,快速开始

EH搜索     
EH云课堂-专业的职场技能充电站 妙哉!函数段子手趣味讲函数 Excel服务器-会Excel,做管理系统 Excel Home精品图文教程库
Excel不给力? 何不试试FoxTable! Excel 2016函数公式学习大典 EH云课堂直播课程免费学 打造核心竞争力的职场宝典
300集Office 2010微视频教程 Tableau-数据可视化工具 精品推荐-800套精选PPT模板,点击获取 ExcelHome出品 - VBA代码宝免费下载
你的Excel 2010实战技巧学习锦囊 欲罢不能, 过目难忘的 Office 新界面 Excel VBA经典代码实践指南
查看: 47053|回复: 85

[原创] 一堆数字凑金额(凑数值) - 一个求解子集和问题的高速算法(有条件限制)

  [复制链接]

TA的精华主题

TA的得分主题

发表于 2011-3-3 19:13 | 显示全部楼层 |阅读模式
本帖已被收录到知识树中,索引项:
本帖最后由 灰袍法师 于 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

VBA - 子集和 - 求指定和值的所有组合总数 - long版本.rar

60.98 KB, 下载次数: 3519

评分

参与人数 2鲜花 +4 收起 理由
ravinn + 2 感谢帮助
人森叶 + 2 高山仰止!学习Excel更有动力鸟

查看全部评分

TA的精华主题

TA的得分主题

发表于 2011-3-3 19:30 | 显示全部楼层
法师发贴了,沙发一下。

TA的精华主题

TA的得分主题

发表于 2011-3-3 19:37 | 显示全部楼层

TA的精华主题

TA的得分主题

发表于 2011-5-28 18:58 | 显示全部楼层

TA的精华主题

TA的得分主题

发表于 2011-8-5 23:34 | 显示全部楼层

TA的精华主题

TA的得分主题

发表于 2011-8-6 00:35 | 显示全部楼层

TA的精华主题

TA的得分主题

发表于 2011-8-6 08:28 | 显示全部楼层
那么,法师,用这个算法来算24,应该也很快吧?

TA的精华主题

TA的得分主题

 楼主| 发表于 2011-8-6 18:05 | 显示全部楼层
原帖由 香川群子 于 2011-8-6 08:28 发表
那么,法师,用这个算法来算24,应该也很快吧?


算24本来就很简单吖,穷举全部也就一瞬间。

TA的精华主题

TA的得分主题

发表于 2011-10-1 11:01 | 显示全部楼层
你好,十一期间不知道你上网吧?我有个同样的问题想解决,可本人很笨,麻烦你给解决一下,可以吗?

TA的精华主题

TA的得分主题

发表于 2011-10-1 11:02 | 显示全部楼层
这个问题就是要开发票,必须得开总额为110840,怎么办啊

常春林发票.rar

13.52 KB, 下载次数: 540

您需要登录后才可以回帖 登录 | 免费注册

本版积分规则

关闭

最新热点上一条 /1 下一条

关注官方微信,每天学会一个新技能

手机版|关于我们|联系我们|ExcelHome

GMT+8, 2020-2-26 09:54 , Processed in 0.464034 second(s), 19 queries , Gzip On, MemCache On.

Powered by Discuz! X3.4

© 1999-2020 Wooffice Inc.

   

沪公网安备 31011702000001号 沪ICP备11019229号

本论坛言论纯属发表者个人意见,任何违反国家相关法律的言论,本站将协助国家相关部门追究发言者责任!     本站特聘法律顾问:徐怀玉律师 李志群律师

快速回复 返回顶部 返回列表