邯郸学步：再做递归凑数之列出开票明细

aoe1981 · 发表于 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, 下载次数: 264)

aoe1981 · 发表于 2014-10-23 22:09

　　附件一角：
　　

aoe1981 · 发表于 2014-10-23 22:10

　　核心的递归代码：

Sub DG(k%, xzwc As Boolean)
Dim j&, i&
If pd Then Exit Sub '找到匹配结果时直接逐层返回
If k = n Then
For j = sl(k, 1) To 0 Step -1
If xzwc Then
If Abs(je(k) - dj(k, 1) * j) <= wcz Then '误差匹配
pd = True
ss(k) = j
For i = 1 To n
s = s & "-" & ss(i)
Next i
End If
Else
If je(k) - dj(k, 1) * j = 0 Then '精确匹配
pd = True
ss(k) = j
For i = 1 To n
s = s & "-" & ss(i)
Next i
End If
End If
Next j
Else
For j = sl(k, 1) To 0 Step -1
je(k + 1) = je(k) - dj(k, 1) * j '下层金额=本层金额-本层单价*本层数量
sl(k + 1, 1) = je(k + 1) \ dj(k + 1, 1) '下层数量=下层金额\下层单价
ss(k) = j
DG k + 1, wc
Next j
End If
End Sub

复制代码

aoe1981 · 发表于 2014-10-23 22:13

附件新特点：
支持精确匹配与可控误差匹配。
如果某个组合注定无解的话，在运行时间上会经历漫长的等待，可能会类似“死循环”……不管如何，重新打开也好，请试一试误差匹配，也许会很快。

aoe1981 · 发表于 2014-10-23 22:15

至于项目明细的选择，不再像香川一样，提供丰富而功能强大的随机选择与手动选择，而是只支持手动点击选择，再击则取消，凡点击着，依据公式，会自动添加进“票据品名”项中……

aoe1981 · 发表于 2014-10-23 22:26

本帖最后由 aoe1981 于 2014-10-23 22:30 编辑

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

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

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

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

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

aoe1981 · 发表于 2014-10-23 22:39

本帖最后由 aoe1981 于 2014-10-23 22:48 编辑

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

aoe1981 · 发表于 2014-10-23 22:41

　　上一张较极端情况测试图：
　　

aoe1981 · 发表于 2014-10-23 22:45

增加了一句：

If je(1) < 0 Then MsgBox "所选商品单价和大于凑数金额，请减少选择商品种类！", , "友情提示": Exit Sub

复制代码

解决了7楼问题1，并更新了1楼附件。

aoe1981 · 发表于 2014-10-23 23:03

　　下面上一组我与香川附件在某组特定数据下的对比效果图：
　　aoe1981（启用了误差匹配）：

　　香川（只支持精确匹配）：

　　可见，香川的没有找到（对其附件中的某些参数，本人不十分了解）。而我的代码在做这组数据的精确匹配时，显然，我是等不住的……虽然，参考循环次数是4832（这个数字是以各商品最大匹配数量相乘求和得出的……），但实际的肯定比这要多……

		自动登录	找回密码
密码			免费注册

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

评分