ExcelHome技术论坛

 找回密码
 免费注册

QQ登录

只需一步,快速开始

EH搜索     
EH云课堂-专业的职场技能充电站 Excel转在线管理系统,怎么做看这里 Excel服务器-会Excel,做管理系统 Excel Home精品图文教程库
Excel不给力? 何不试试FoxTable! Excel 2016函数公式学习大典 高效办公必会的Office实战技巧 免费下载Excel行业应用视频
300集Office 2010微视频教程 Tableau-数据可视化工具 精品推荐-800套精选PPT模板,点击获取 ExcelHome出品 - VBA代码宝免费下载
你的Excel 2010实战技巧学习锦囊 欲罢不能, 过目难忘的 Office 新界面 Excel VBA经典代码实践指南
查看: 61625|回复: 372
打印 上一主题 下一主题

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

  [复制链接]

TA的精华主题

TA的得分主题

跳转到指定楼层
1
发表于 2014-1-1 14:54 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
本帖已被收录到知识树中,索引项:递归
本帖最后由 香川群子 于 2014-1-9 21:14 编辑

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

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


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


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

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


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


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

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


评分

参与人数 45财富 +50 鲜花 +96 技术 +2 收起 理由
开明兽9527 + 2
swf + 2 优秀作品
hb_alucard + 2 太强大了
七夕、 + 3 谢谢群子老师、&amp;amp;#10048;&amp;amp;#10048;&amp;amp;#10.
autumnalRain + 3 优秀作品

查看全部评分

TA的精华主题

TA的得分主题

2
 楼主| 发表于 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, 下载次数: 2720

评分

参与人数 4鲜花 +9 收起 理由
七夕、 + 3 感谢帮助
鄂龙蒙 + 2 优秀作品
人事难料 + 2 感谢帮助
windimi007 + 2 优秀作品

查看全部评分

TA的精华主题

TA的得分主题

3
 楼主| 发表于 2014-1-1 15:09 | 只看该作者
2楼的附件只能用来计算1-n的连续自然数、目标和值可以任意。

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

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

评分

参与人数 2鲜花 +5 收起 理由
七夕、 + 3 感谢帮助
windimi007 + 2 值得肯定

查看全部评分

TA的精华主题

TA的得分主题

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

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

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

TA的精华主题

TA的得分主题

5
发表于 2014-1-1 15:30 | 只看该作者

TA的精华主题

TA的得分主题

6
发表于 2014-1-1 19:31 | 只看该作者
你去找找法师来看看这个帖子,给个评价,俺好决定加不加分。因为俺看不懂

TA的精华主题

TA的得分主题

7
 楼主| 发表于 2014-1-1 20:07 | 只看该作者
sheet2中有三个论坛里较难解决的求助帖,作为案例。

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


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

点评

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

评分

参与人数 1鲜花 +3 收起 理由
七夕、 + 3 感谢帮助

查看全部评分

TA的精华主题

TA的得分主题

8
 楼主| 发表于 2014-1-1 20:29 | 只看该作者
其实,原始数据中如果还含有负数,那么计算量的增加会非常厉害!

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

评分

参与人数 1鲜花 +3 收起 理由
七夕、 + 3 感谢帮助

查看全部评分

TA的精华主题

TA的得分主题

9
发表于 2014-1-2 08:13 | 只看该作者

TA的精华主题

TA的得分主题

10
发表于 2014-1-2 08:50 | 只看该作者
您需要登录后才可以回帖 登录 | 免费注册

本版积分规则

关注官方微信,高效办公专列,每天发车

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

GMT+8, 2019-8-19 10:24 , Processed in 0.110689 second(s), 15 queries , Gzip On, MemCache On.

Powered by Discuz! X3.4

© 1999-2020 Wooffice Inc.

   

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

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

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