ExcelHome技术论坛

 找回密码
 免费注册

QQ登录

只需一步,快速开始

快捷登录

搜索
EH技术汇-专业的职场技能充电站 妙哉!函数段子手趣味讲函数 Excel服务器-会Excel,做管理系统 Excel Home精品图文教程库
HR薪酬管理数字化实战 Excel 2021函数公式学习大典 Excel数据透视表实战秘技 打造核心竞争力的职场宝典
300集Office 2010微视频教程 数据工作者的案头书 免费直播课集锦 ExcelHome出品 - VBA代码宝免费下载
用ChatGPT与VBA一键搞定Excel WPS表格从入门到精通 Excel VBA经典代码实践指南
楼主: 香川群子

[原创] 2014新年元旦第一强帖:实用凑数凑金额高效递归剪枝算法

  [复制链接]

TA的精华主题

TA的得分主题

发表于 2014-7-7 13:49 | 显示全部楼层
本帖已被收录到知识树中,索引项:递归
香川群子 发表于 2014-7-5 10:14
我的程序是实用化的,并不是你想象的那么简单。

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

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

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

TA的精华主题

TA的得分主题

发表于 2014-7-7 14:10 | 显示全部楼层
codexq 发表于 2014-7-7 13:49
其实根本就没必要求出所有解,假设现在有50个数据,他们的排列组合是2^50(不剔除重复),也就是1千万亿个 ...

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

TA的精华主题

TA的得分主题

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

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

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

TA的精华主题

TA的得分主题

 楼主| 发表于 2014-7-7 14:41 | 显示全部楼层
[广告] Excel易用宝 - 提升Excel的操作效率 · Excel / WPS表格插件       ★免费下载 ★       ★ 使用帮助
codexq 发表于 2014-7-7 14:10
嘛,其实我想说的是,这个程序如果数据量超过20那就没什么意义了。2^30都已经上百亿了,肯定会产生一大堆 ...

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

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

TA的精华主题

TA的得分主题

发表于 2014-7-15 09:57 | 显示全部楼层
支持,前来来学习一下。我递归一直都学不明白...
大爱香川老师,嘿嘿

TA的精华主题

TA的得分主题

发表于 2014-7-15 13:26 | 显示全部楼层
香川老师,目前我看到的算法,在小数凑大数的时候都会死机,比如这个程序我用0.1到9.5步长0.1的一列数字来凑70……有没有能够解这种极端问题的算法呢?或者至少不要嵌套这么多循环导致死机?

TA的精华主题

TA的得分主题

 楼主| 发表于 2014-7-15 15:25 | 显示全部楼层
本帖最后由 香川群子 于 2014-7-15 15:36 编辑
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秒就出来了。

评分

1

查看全部评分

TA的精华主题

TA的得分主题

发表于 2014-7-15 17:29 | 显示全部楼层
完全看不懂,

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

TA的精华主题

TA的得分主题

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

大谢!实际应用中确实应该这样做~

TA的精华主题

TA的得分主题

 楼主| 发表于 2014-7-15 19:20 | 显示全部楼层
lolmuta 发表于 2014-7-15 17:29
完全看不懂,

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

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

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

但是一般的应用应该没问题。如果你有实际例子,我可以帮你单独写个应用程序,
而通用的程序,要等我有时间整理好以后再发表。
您需要登录后才可以回帖 登录 | 免费注册

本版积分规则

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

GMT+8, 2024-3-29 15:52 , Processed in 0.050224 second(s), 7 queries , Gzip On, Redis On.

Powered by Discuz! X3.4

© 1999-2023 Wooffice Inc.

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

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

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