ExcelHome技术论坛

 找回密码
 免费注册

QQ登录

只需一步,快速开始

快捷登录

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

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

  [复制链接]

TA的精华主题

TA的得分主题

发表于 2014-1-1 14:54 | 显示全部楼层 |阅读模式
[广告] Excel易用宝 - 提升Excel的操作效率 · Excel / WPS表格插件       ★免费下载 ★       ★ 使用帮助
本帖已被收录到知识树中,索引项:递归
本帖最后由 香川群子 于 2014-1-9 21:14 编辑

最近发现、各种凑数、凑金额的求助帖还是比较多。

有人建议用规划求解……
但缺点是显而易见的:
源数据个数较多时计算很长时间不会有结果;往往不能精确匹配;只能给出一组近似解……


也有人亲力而为,为求助者写循环代码计算出结果了……
计算效率非常之低就不说了,显然不具有通用性,应该是属于吃力不讨好的工作。


…………
我因为彭版出过的一道求1-100总和=100的所有组合解(共444,793个)的帖子,
所以研究了速度最快的递归组合求和算法。

后来发现这个题目很有实用价值,用来解决凑数、凑金额问题,几乎是手到擒来。


但是考虑到实际需求,于是又不断做了很多改进(牺牲了一些计算速度效率),
但实用性大为提高,最后得到的程序功能之多之全、功力之大,前所未见。


趁着今天休息在家,就把程序重新整理了一遍、并且加了一些简要的注释,把代码公开。
希望能给大家一个惊喜!
凑数字凑金额的最佳递归程序by_kagawa.rar (26.84 KB, 下载次数: 14044)

附件做了一次更新……递归计算深度参数的设置做了改进:
1. 默认留空=0时,按10万次(10^5=100000)大约相当于16.5层的组合
2. 输入>0 的正整数时,按输入值作为递归计算深度
   (该数值可大可小,小了速度快但可能漏掉很多组合解……大了速度降低)
3. 输入<0的负数如=-1时,不限制递归计算深度……每次都是计算直到有解了或者达到剪枝条件时才清零退出


评分

57

查看全部评分

TA的精华主题

TA的得分主题

 楼主| 发表于 2014-1-1 15:07 | 显示全部楼层
彭版出的题目的帖子
http://club.excelhome.net/forum. ... p;page=7#pid6353576

有兴趣的可以从头慢慢看,其中很多人的回帖也很有技术含量。

没兴趣的就看我的附件,计算1-100求总和=100的组合解,耗时不到1秒(机器好的话大约0.3秒)

而一般人中间最快的算法,也会要3-7秒。


最快速的自然序列数组合求和.rar

11.5 KB, 下载次数: 4159

评分

8

查看全部评分

TA的精华主题

TA的得分主题

 楼主| 发表于 2014-1-1 15:09 | 显示全部楼层
2楼的附件只能用来计算1-n的连续自然数、目标和值可以任意。

所以这个程序速度虽然最快,但并不具有通用性、实用性。

但它为递归算法的高效算法,奠定了基础。

评分

2

查看全部评分

TA的精华主题

TA的得分主题

发表于 2014-1-1 15:20 | 显示全部楼层
香川群子 发表于 2014-1-1 15:09
2楼的附件只能用来计算1-n的连续自然数、目标和值可以任意。

所以这个程序速度虽然最快,但并不具有通用 ...

香川老师辛苦了,果断加分支持!

TA的精华主题

TA的得分主题

发表于 2014-1-1 15:30 | 显示全部楼层

TA的精华主题

TA的得分主题

发表于 2014-1-1 19:31 | 显示全部楼层
你去找找法师来看看这个帖子,给个评价,俺好决定加不加分。因为俺看不懂

TA的精华主题

TA的得分主题

 楼主| 发表于 2014-1-1 20:07 | 显示全部楼层
sheet2中有三个论坛里较难解决的求助帖,作为案例。

用通常的方法是难以得到解答,但用我的程序适当调整参数以后就能很快得到组合解的答案了。


建议今后有凑数、凑金额要求的,都请推荐来用我的程序,用法不太明白的可以直接来问我。
不要再说什么规划求解的话了……规划求解是没有用的。

点评

规划求解是设计应付普遍问题的,专项当然是专门设计的好~ 设计成类吧  发表于 2014-1-1 23:20
是的,规划求解只能解出非常简单的题目,稍复杂就死翘翘了。  发表于 2014-1-1 20:21

评分

2

查看全部评分

TA的精华主题

TA的得分主题

 楼主| 发表于 2014-1-1 20:29 | 显示全部楼层
其实,原始数据中如果还含有负数,那么计算量的增加会非常厉害!

但是应用我的程序算法,却仍然能处理。

评分

2

查看全部评分

TA的精华主题

TA的得分主题

发表于 2014-1-2 08:13 | 显示全部楼层
[广告] VBA代码宝 - VBA编程加强工具 · VBA代码随查随用  · 内置多项VBA编程加强工具       ★ 免费下载 ★      ★使用手册
很厉害,值得学习{:soso_e179:}

TA的精华主题

TA的得分主题

发表于 2014-1-2 08:50 | 显示全部楼层
您需要登录后才可以回帖 登录 | 免费注册

本版积分规则

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

GMT+8, 2024-3-29 02:10 , Processed in 0.050250 second(s), 11 queries , Gzip On, Redis On.

Powered by Discuz! X3.4

© 1999-2023 Wooffice Inc.

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

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

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