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经典代码实践指南
查看: 4403|回复: 23

[原创] 邯郸学步:再做递归凑数之列出开票明细

[复制链接]

TA的精华主题

TA的得分主题

发表于 2014-10-23 22:08 | 显示全部楼层 |阅读模式
本帖已被收录到知识树中,索引项:递归
本帖最后由 aoe1981 于 2014-10-28 14:21 编辑

  香川群子女侠有一帖:
  《barry1126 求助:凑数实用例子 列出开票明细》
  http://club.excelhome.net/thread-1150861-1-1.html
  给出了开创性的解决方案,我曾下载测试过许多次,颇对其算法好奇。然而不明其算法原理,且附件代码中无一字之注释,参悟即是不大可能。于是便自我想解决办法,逐着自个的思路,从新写来,倒也流畅。

  一开始出了《开票明细(aoe1981之幼儿水平版)》,见下面链接:
  http://club.excelhome.net/forum. ... 1150861&pid=7895280
  自我感觉极是不满意,简直是不知天高地厚,班门弄斧,关老爷门前耍大刀,便没敢新发帖,在香川的“英雄”帖后狗尾续貂。

  然而,问题我一直惦记着,尤其在学习了《归去来兮-漫谈递归》后,便似乎有了一项利器,想像中的思路似乎可以用代码实现了。虽然这种思路可能并不高效,但至少可以解决问题。当然,仍不排除个别情况下漫长的等待,类似无解。所以如此说,主要是因为,我至今仍不明白香川所言“深度优先”的剪枝算法是什么意思……

  现在,我终于可以把我的所作拿出来示人了,尤其希望得到香川女侠的点评!!!
  吹牛时刻,附件如下:
   开票明细(aoe1981之小学版).rar (44.82 KB, 下载次数: 207)

评分

参与人数 2鲜花 +4 收起 理由
liu-aguang + 2 兄弟玩的都是高IQ呀
lm1221 + 2 值得学习

查看全部评分

TA的精华主题

TA的得分主题

 楼主| 发表于 2014-10-23 22:09 | 显示全部楼层

TA的精华主题

TA的得分主题

 楼主| 发表于 2014-10-23 22:10 | 显示全部楼层
  核心的递归代码:

  1. Sub DG(k%, xzwc As Boolean)
  2. Dim j&, i&
  3. If pd Then Exit Sub '找到匹配结果时直接逐层返回
  4. If k = n Then
  5.     For j = sl(k, 1) To 0 Step -1
  6.         If xzwc Then
  7.             If Abs(je(k) - dj(k, 1) * j) <= wcz Then '误差匹配
  8.                 pd = True
  9.                 ss(k) = j
  10.                 For i = 1 To n
  11.                     s = s & "-" & ss(i)
  12.                 Next i
  13.             End If
  14.         Else
  15.             If je(k) - dj(k, 1) * j = 0 Then '精确匹配
  16.                 pd = True
  17.                 ss(k) = j
  18.                 For i = 1 To n
  19.                     s = s & "-" & ss(i)
  20.                 Next i
  21.             End If
  22.         End If
  23.     Next j
  24. Else
  25.     For j = sl(k, 1) To 0 Step -1
  26.         je(k + 1) = je(k) - dj(k, 1) * j '下层金额=本层金额-本层单价*本层数量
  27.         sl(k + 1, 1) = je(k + 1) \ dj(k + 1, 1) '下层数量=下层金额\下层单价
  28.         ss(k) = j
  29.         DG k + 1, wc
  30.     Next j
  31. End If
  32. End Sub
复制代码

TA的精华主题

TA的得分主题

 楼主| 发表于 2014-10-23 22:13 | 显示全部楼层
附件新特点:
支持精确匹配与可控误差匹配。
如果某个组合注定无解的话,在运行时间上会经历漫长的等待,可能会类似“死循环”……不管如何,重新打开也好,请试一试误差匹配,也许会很快。

TA的精华主题

TA的得分主题

 楼主| 发表于 2014-10-23 22:15 | 显示全部楼层
至于项目明细的选择,不再像香川一样,提供丰富而功能强大的随机选择与手动选择,而是只支持手动点击选择,再击则取消,凡点击着,依据公式,会自动添加进“票据品名”项中……

TA的精华主题

TA的得分主题

 楼主| 发表于 2014-10-23 22:26 | 显示全部楼层
本帖最后由 aoe1981 于 2014-10-23 22:30 编辑

  下面说说我的核心思路:
  首先,假定所选项目必须要买,其数量至少为1,因此,所要凑数的金额,则为总金额减去所选项目的单价,相当于各减数量1的价格。

  2.匹配时,按所选项目顺序从上至下进行匹配测试;

  3.对于第一种商品(或项目),先计算其最大可能数量,在此基础上以步长-1递减;
  (备注:每种商品都有一个最大匹配数量,只是这个最大匹配数量是在假定其他商品匹配为0的情况下,如果其他商品已购买,则这个最大匹配数量将动态下降)

  4.每种商品都做一个步长为-1的递减循环,但这个循环变量的起始值(也即该商品的最大匹配数量)除第一种商品外,其余皆是动态变化的……
  (因此,要准确确定循环的总次数,在实际累计的方法之外,通过理论计算,则是不确定的,因此附件中的循环次数“仅做参考”)

  5.关于循环层数,选几种商品,则循环几层……

TA的精华主题

TA的得分主题

 楼主| 发表于 2014-10-23 22:39 | 显示全部楼层
本帖最后由 aoe1981 于 2014-10-23 22:48 编辑

目前,附件中开票明细项目最多支持20种商品,我其实主要在10种以内进行测试,因为,当商品数过多时有两个问题:
1.凑数金额小于所选商品单价之和的错误应当排除(其实,所选商品数少时也存在这个问题,马上修正);
2.循环层数过多,使代码运行效率上的低下被放大,估计大家都是没有耐心的……呵呵,这主要是和算法有关……在此,像伟大的香川致以敬意,她的效率比我的高很多……
(不过,对于不可能精确匹配的组合,我想一样需要等待)
……
记住,当商品太多时,感觉快等到花儿都谢了的时候,请启用“误差匹配”……

TA的精华主题

TA的得分主题

 楼主| 发表于 2014-10-23 22:41 | 显示全部楼层

TA的精华主题

TA的得分主题

 楼主| 发表于 2014-10-23 22:45 | 显示全部楼层
增加了一句:
  1. If je(1) < 0 Then MsgBox "所选商品单价和大于凑数金额,请减少选择商品种类!", , "友情提示": Exit Sub
复制代码
解决了7楼问题1,并更新了1楼附件。

TA的精华主题

TA的得分主题

 楼主| 发表于 2014-10-23 23:03 | 显示全部楼层
  下面上一组我与香川附件在某组特定数据下的对比效果图:
  aoe1981(启用了误差匹配):
aoe.jpg
  香川(只支持精确匹配):
xiangchuan.jpg
  可见,香川的没有找到(对其附件中的某些参数,本人不十分了解)。而我的代码在做这组数据的精确匹配时,显然,我是等不住的……虽然,参考循环次数是4832(这个数字是以各商品最大匹配数量相乘求和得出的……),但实际的肯定比这要多……
您需要登录后才可以回帖 登录 | 免费注册

本版积分规则

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

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

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

Powered by Discuz! X3.4

© 1999-2020 Wooffice Inc.

   

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

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

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