ExcelHome技术论坛

标题: 2014新年元旦第一强帖：实用凑数凑金额高效递归剪枝算法 [打印本页]

---

作者: 香川群子    时间: 2014-1-1 14:54
标题: 2014新年元旦第一强帖：实用凑数凑金额高效递归剪枝算法


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

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


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


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

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


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


趁着今天休息在家，就把程序重新整理了一遍、并且加了一些简要的注释，把代码公开。
希望能给大家一个惊喜！
(, 下载次数: 14097)

上传

点击文件名下载附件

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

---

作者: 香川群子    时间: 2014-1-1 15:07
彭版出的题目的帖子
http://club.excelhome.net/forum. ... p;page=7#pid6353576

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

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

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

---

作者: 香川群子    时间: 2014-1-1 15:09
2楼的附件只能用来计算1-n的连续自然数、目标和值可以任意。

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

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

---

作者: windimi007    时间: 2014-1-1 15:20

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

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

香川老师辛苦了，果断加分支持！

---

作者: fffox    时间: 2014-1-1 15:30
学习一下，谢谢香川老师

---

作者: liucqa    时间: 2014-1-1 19:31
你去找找法师来看看这个帖子，给个评价，俺好决定加不加分。因为俺看不懂

---

作者: 香川群子    时间: 2014-1-1 20:07
sheet2中有三个论坛里较难解决的求助帖，作为案例。

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


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

---

作者: 香川群子    时间: 2014-1-1 20:29
其实，原始数据中如果还含有负数，那么计算量的增加会非常厉害！

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

---

作者: 616891719    时间: 2014-1-2 08:13
很厉害，值得学习{:soso_e179:}

---

作者: 青见    时间: 2014-1-2 08:50
收藏慢慢学习，看是否能用到对账上。

---

作者: 航起帆扬    时间: 2014-1-2 09:02
谢楼主，学习。

---

作者: gjj136138139    时间: 2014-1-2 09:13
很不错！这是2014年最好的礼物了，谢谢楼主。

---

作者: 香川群子    时间: 2014-1-2 10:00


我的递归程序在实用化上面，有一项重大发明：【单次递归计算深度】参数的应用。

如果源数据分布较均匀，满足条件的组合解有很多，
那么递归过程会很顺利，每向下深入递归1次到2次，就可能发现一个有效解……（自然数序列时）

但实际情形显然不可能如此，因此，递归会以近似剩余个数n的2^n的级别进行深度递归计算，
直到有解或最后仍然无解……

我发现，大部分情况下，如果一开始没有解，那么后面有解的概率会很低、很低。
因此，我设置了单次递归计算深度的限制条件，默认为计算10万次。（大约是向下搜索16-17层）
如果接下来连续16个数的全部组合都没有解，那么就不再向下搜索了。

这个方法，当然会漏掉一些解，但在提高通用性程序不死机的效果上，具有明显的好处。

因此，我的这项发明，是可以值得骄傲的。


sheet2中例子3：
http://club.excelhome.net/thread-386306-2-1.html
在以下29个数据求目标总和=404034.3，就是个很好的例子
975,1001,1398,5538,10345,12128,12133,13000,13000,13000,13000,13000,15068.6,15485.4,15700,15717.8,19680.5,20674.9,24880.5,25000,25256,29877.1,33992,34710.6,43500,50797.6,54540,64629.3


按默认递归计算深度=10万次时，计算1秒不到得到 6组解。
但是如果设置递归计算深度=50万次时，计算10秒能得到 33组解。

这已经是全部解了。因为即使设置递归计算深度到100万次，结果也是一样的。

注意到计算速度的差异为 10多倍。
如果设置计算深度为 35000时（实际能得到组合解的最小递归深度）
那么得到1组解，但耗时仅0.1秒。

如果不需要全部组合解，或者不需要很多解时，用这个方法来提高计算效率是很好的方法。

ps：
如果不设置计算深度，往往程序会在某个区间进入假死状态。
（当剩余计算量为2^n个组合，而这一分支的最后结果仍然是无解时）


本题举例中全部数据仅29个，如果原始数据个数增加到200个、300个时，
如果不有效进行递归深度的设置，那么计算一定会死机。

---

作者: 香川群子    时间: 2014-1-2 10:28
程序在通用性、实用性方面做了很多改进，但是速度效率也就有较大的牺牲了。

以自然序列计算1-100求总和=100的全部组合解444793为例，
我的【仅能计算任意正整数】的递归剪枝算法，计算只需1秒（不含输出）。
含输出结果的也大约只需2秒不到，但现在的通用计算程序需要大约2.5秒以上。

但这些速度效率的牺牲是值得的。一个通用性强的程序才有实用价值。

---

作者: sportskill    时间: 2014-1-2 13:31
学习一下，谢谢分享！

---

作者: 高文贤    时间: 2014-1-2 15:35
{:soso_e179:}

---

作者: 灰袍法师    时间: 2014-1-2 16:08

香川群子 发表于 2014-1-2 10:28
程序在通用性、实用性方面做了很多改进，但是速度效率也就有较大的牺牲了。

以自然序列计算1-100求总和= ...

说得好，宁肯慢一点，反正计算的时候用户可以趁机偷懒。。。。。。

---

作者: m_n_j001    时间: 2014-1-2 16:11
香帅就是帅！美女就是美！

---

作者: no11road    时间: 2014-1-3 08:27
学习一下，谢谢香川老师

---

作者: huangyun    时间: 2014-1-3 08:33
收藏了，下次凑数字可有大用长了。

---

作者: xinhunter    时间: 2014-1-3 09:03
算法这种伤脑细胞的事，直接收藏备用。

---

作者: 840205910    时间: 2014-1-3 09:20
该程序的最大受益者是财务人员

---

作者: Ron2000    时间: 2014-1-3 10:07
支持香川大侠，看得出花很多时间整理、说明。加了参数配置，考虑了实际应用的很多情况！

---

作者: 香川群子    时间: 2014-1-3 10:20

灰袍法师 发表于 2014-1-2 16:08
说得好，宁肯慢一点，反正计算的时候用户可以趁机偷懒。。。。。。

其实也只是稍微慢了一点，比起普通二进制组合算法，仍然是火车和牛车的差别。

最最关键是，适当的参数调整就可以不死机，一般在几十秒之内就有结果了。

---

作者: aoranbuqun    时间: 2014-1-3 10:58
太强大了!学习一下!谢谢楼主!好生仰慕啊!

---

作者: casinosun    时间: 2014-1-3 12:22
学习一下，谢谢香川老师

---

作者: 香川群子    时间: 2014-1-7 15:27
欢迎大家使用后发表感想……

另外，如果程序使用中有问题，可以随时提问咨询。

我在这里会礼貌地进行答复……但如果是私信就会粗俗地回复……呵呵。

---

作者: 香川群子    时间: 2014-1-9 21:16

Ron2000 发表于 2014-1-3 10:07
支持香川大侠，看得出花很多时间整理、说明。加了参数配置，考虑了实际应用的很多情况！

组合计算以外，我的参数设置才是亮点。

一般人考虑不到那么细致的……女生的特长么、心细。

---

作者: cpscqqccps    时间: 2014-1-26 13:42
非常感谢，真是大好人

---

作者: 中国86    时间: 2014-2-11 22:43
很厉害，值得学习

---

作者: unione    时间: 2014-2-14 15:57


算法精巧，可以快速找到解。确实是一种通用的方法。

---

作者: ttplayer1    时间: 2014-3-5 11:02
牛逼   收下了

---

作者: finacc    时间: 2014-3-5 11:47
先下载，再慢慢学习吧

---

作者: VBA万岁    时间: 2014-3-5 14:36
没看懂，不知所云。还望楼主明示。

---

作者: wqfzqgk    时间: 2014-3-7 19:01
太厉害了，学习

---

作者: smdon    时间: 2014-3-17 17:31
我爱你楼主，我爱你帮我解决大问题了。祝你青春美丽，万事顺利，吉祥如意，阖家平安。

---

作者: hzeng168    时间: 2014-3-20 11:30
好犀利，学习！！

---

作者: 66327823    时间: 2014-3-30 17:30


川老师，等于100的组合有很多，我想找出1-100这些数只用一次的所有组合。如1+99，2+98，3+97，4+5+6+85，等等，前面的数字用过一次，后面的组合就不能用了。如4+96也等于100，但是4已经用过，不能用这个组合了。

---

作者: homehomehome    时间: 2014-3-30 20:10
下载学习下。多谢

---

作者: 香川群子    时间: 2014-3-31 00:38

66327823 发表于 2014-3-30 17:30
川老师，等于100的组合有很多，我想找出1-100这些数只用一次的所有组合。如1+99，2+98，3+97，4+5+6+85，等 ...

这个当然也可以做到，但得到的结果就会是所有有解组合中的不重复组合……

那么，如果你没有一个明确的规则的话，做起来就很伤脑筋……
比如1+99=100用过了以后，那么以后所有含1的组合都不能再用了……这回漏掉很多组合的。

那么，你实际需要的是1 一定要和99组合吗？
还是允许 1+2+97=100呢？


当然，如果你没有任何限制，随便取出一些组合直到剩余最后几个无法组合成=100就算结束。
这样的代码可以有。

---

作者: 香川群子    时间: 2014-3-31 00:41
这个例子就是从一堆数中抽取符合条件的组合，直到剩余元数无法满足求和条件时停止。

但显然这样得到的结果，只是成千上万种所有可能解组合中的一种。

---

作者: 善读书    时间: 2014-3-31 12:33
谢谢楼主提供这个牛的程序 解决了不少问题
请问一下 最终计算出组合 能不能实现 当选定某组合的格子时
该组合格子中 所涉及的数字 其原始表格 都自动高亮呢

---

作者: haryzbs    时间: 2014-3-31 23:51
学习了，，，

---

作者: 香川群子    时间: 2014-4-1 11:49

善读书 发表于 2014-3-31 12:33
谢谢楼主提供这个牛的程序 解决了不少问题
请问一下 最终计算出组合 能不能实现 当选定某组合的格子时
该 ...

当然可以，而且并不复杂……

选中G列后，激活SelectiChange事件，即可自动分析、查找、高亮该行组合。

…………
但是我在本帖附件中放弃了这个做法，因为如果对象组合元素中有重复时会产生干扰。

---

作者: 香川群子    时间: 2014-4-1 11:59

善读书 发表于 2014-3-31 12:33
谢谢楼主提供这个牛的程序 解决了不少问题
请问一下 最终计算出组合 能不能实现 当选定某组合的格子时
该 ...

1. Private Sub Worksheet_SelectionChange(ByVal Target As Range)
   
2.     If Target.Count > 1 Then Exit Sub
   
3.     If Target.Column <> 8 Then Exit Sub
   
4.     If Target = "" Then Exit Sub
   
5.    
   
6.     m = Range("A1").End(xlDown).Row
   
7.     Range("A1").Resize(m).Interior.ColorIndex = 0
   
8.     If Target.Row = 1 Then Exit Sub
   
9.    
   
10.     sj = Range("A1").Resize(m)
    
11.     Set d = CreateObject("Scripting.Dictionary")
    
12.     For i = m To 2 Step -1
    
13.         d(CStr(sj(i, 1))) = i
    
14.     Next
    
15.    
    
16.     t = Split(Target, "+")
    
17.     For i = 1 To UBound(t)
    
18.         Cells(d(t(i)), 1).Interior.ColorIndex = 6
    
19.     Next
    
20.    
    
21. End Sub

复制代码

你把上边这段代码整体复制、粘贴到Sheet1的代码页中，然后就可以有这个功能了。

使用方法：
1. 组合凑数计算完成后，选中H列（有+号表达式的那一列）
然后A列对应数值就会高亮显示（单元格底色黄色）

2. 选中H1单元格时即可取消A列全部底色


呵呵。自己复制试一试吧。

但是提醒你，如果A列中数据有较多重复，则可能出错。
另外，可能会因为数据小数点显示误差而导致错误。

因为有可能出错，所以我没有加入我的正式程序中。

但你如果自己方便要用，可以自己加进去，做个提醒还是有用处的。

---

作者: 百度不到去谷歌    时间: 2014-4-1 18:01
收藏学习了

---

作者: 592rmb    时间: 2014-4-2 09:52
Ron2000 发表于 2014-1-3 10:07
支持香川大侠，看得出花很多时间整理、说明。加了参数配置，考虑了实际应用的很多情况！
组合计算以外，我的参数设置才是亮点。

一般人考虑不到那么细致的……女生的特长么、心细。
原來想穿裙子老師是大美女呀，佩服

---

作者: DZ潇潇    时间: 2014-4-6 15:10
V盲表弟也来收藏此宝帖。

---

作者: 海婷    时间: 2014-4-8 10:44
确实是一种通用的方法，多谢！！！

---

作者: tom2228    时间: 2014-4-19 15:12
谢谢楼主，高手

---

作者: tom2228    时间: 2014-4-19 15:23
楼主，显示颜色运行出错，请再看看。谢谢

---

作者: siewa    时间: 2014-4-23 16:56
先谢谢楼主，你太厉害了，解决了我的大问题。另外，能不能再稍微改进下，把表格中第一列空出来？因为A列的数字我要从别的表格里考过来，如何能多一列放一个关键字进去，我能够比较快地从原表格里把选出来参与计算的记录找出来。

---

作者: calvin909    时间: 2014-4-30 11:44


谢谢楼主，真是很完美，速度很快，秒算。

---

作者: 香川群子    时间: 2014-5-28 08:32
5月28日求助帖

40个左右数值随即取N个数加起来等于或者接近这个数就可以了！谢谢大神
http://club.excelhome.net/thread-1125160-1-1.html

---

作者: chaucerwong    时间: 2014-5-28 09:39
香川大侠，真是好，无私奉献，技术精湛

---

作者: ZXD12231984    时间: 2014-5-28 20:36
没有看懂，先收藏

---

作者: 绝版青春    时间: 2014-5-28 22:41
这个在财务对账上应该有用武之地。哈哈，正好可以试试。

---

作者: jimcomputer    时间: 2014-5-28 22:58
高手经典之作！

---

作者: szrunstar1    时间: 2014-5-29 11:44
下下来研究，谢谢分享

---

作者: zm19782001    时间: 2014-6-4 19:03
万分感谢香川。这个问题困扰我好久了。必须感谢！

---

作者: office8424    时间: 2014-6-5 15:20
香川老师这个算法,在业界有没有颁发过什么奖章啊!!!!这个绝对可以归纳到高等数学里面去了!!!

---

作者: eyeshot    时间: 2014-6-7 22:29
大神算法 收藏之~~~~~~~~~~~~

---

作者: 香川群子    时间: 2014-6-25 16:18

office8424 发表于 2014-6-5 15:20
香川老师这个算法,在业界有没有颁发过什么奖章啊!!!!这个绝对可以归纳到高等数学里面去了!!!

这个算法也不是在技术上有很大的创新，值得颁奖。


但是，在个人电脑上，实际应用方面，尤其是仅仅依靠简单那的VBA代码就能达到如此效果，
应该说我自己都认为、称之为世界第一毫无夸张。

因为VBA的低级应用方面，并没有高级人才在这里下工夫。所以我就毫不客气地世界第一了，呵呵。


…………
如果你有兴趣，我准备写个长帖，把算法原理好好介绍一下啊。

---

作者: office8424    时间: 2014-6-25 16:25

香川群子 发表于 2014-6-25 16:18
这个算法也不是在技术上有很大的创新，值得颁奖。

我当然有兴趣!!!!高等数学在基础实践中的运用,写篇论文都可以了,你写好卖给毕业生,包赚!!!话说我只能给你鲜花其他给不了哈哈!!!

---

作者: codexq    时间: 2014-7-4 20:02
跟楼主思路差不多：先快速排序→递归实现深度优先搜索，剪枝只用到是否比目标数大这个条件

跟lz思路不一样的地方就是，程序检测到一个解的时候马上退出。我测试了很多组随机数（每组50个数），即使在4位小数的情况下，都基本上不存在唯一解。

但是在小样本的情况下，例如每组20个数，基本上都存在唯一解。

lz你的程序用了剪枝，但是你把整棵树除了剪枝部分都遍历了，有点本末倒置了，深搜本来就是在找到答案后马上退出才显出优势。如果lz你要现实所有答案，不放利用do循环进行广搜。

---

作者: 2007小金猪    时间: 2014-7-5 09:14
先收藏，再学习，感谢Eh老师的无私支持

---

作者: 香川群子    时间: 2014-7-5 10:14

codexq 发表于 2014-7-4 20:02
跟楼主思路差不多：先快速排序→递归实现深度优先搜索，剪枝只用到是否比目标数大这个条件

跟lz思路不一 ...

我的程序是实用化的，并不是你想象的那么简单。

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

当然，也可以设置为其它指定个数解，直至所有解。

并且，如果要得到所有解，我的程序也是速度效率很高的，肯定比你想象中的广搜要快。呵呵。


你有兴趣的话，还是继续深入研究一下代码吧。

…………
至于包含负数，结果排除重复值……小数位设置及向上取整模糊计算……呵呵。

---

作者: lightringer    时间: 2014-7-5 21:19
大神您好，我有49个数，需要抽出三个组合，分别有一个和，需要同时求出三个组合，能否实现

b,c,d∈{0,1}

A=[a1:a49]

B=[b1:b49]

C=[c1:c49]

D=[d1:d49]

Sum(A*B)=x

Sum(A*C)=y

Sum(A*D)=z

Sum(B*C)=0

Sum(B*D)=0

Sum(C*D)=0

a,x,y,z是已知量，求B，C，D

即是求从49个数中，抽出若干组成三种组合，各组的和分别为x，y，z

---

作者: 香川群子    时间: 2014-7-6 14:19

lightringer 发表于 2014-7-5 21:19
大神您好，我有49个数，需要抽出三个组合，分别有一个和，需要同时求出三个组合，能否实现

没看懂，你应该上附件说明。

---

作者: byhyxb    时间: 2014-7-6 15:21
大侠之作，学习了

---

作者: codexq    时间: 2014-7-7 13:49

香川群子 发表于 2014-7-5 10:14
我的程序是实用化的，并不是你想象的那么简单。

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

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

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

---

作者: codexq    时间: 2014-7-7 14:10

codexq 发表于 2014-7-7 13:49
其实根本就没必要求出所有解，假设现在有50个数据，他们的排列组合是2^50（不剔除重复），也就是1千万亿个 ...

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

---

作者: 香川群子    时间: 2014-7-7 14:39

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

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

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

---

作者: 香川群子    时间: 2014-7-7 14:41

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

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

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

---

作者: ghostjiao    时间: 2014-7-15 09:57
支持，前来来学习一下。我递归一直都学不明白...
大爱香川老师，嘿嘿

---

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

---

作者: 香川群子    时间: 2014-7-15 15:25

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秒就出来了。

---

作者: lolmuta    时间: 2014-7-15 17:29
完全看不懂，

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

---

作者: Blenderama    时间: 2014-7-15 18:06

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

大谢！实际应用中确实应该这样做～

---

作者: 香川群子    时间: 2014-7-15 19:20

lolmuta 发表于 2014-7-15 17:29
完全看不懂，

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

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

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

但是一般的应用应该没问题。如果你有实际例子，我可以帮你单独写个应用程序，
而通用的程序，要等我有时间整理好以后再发表。

---

作者: 我的一生14    时间: 2014-7-17 13:24

学习一下，谢谢香川老师

---

作者: ghostjiao    时间: 2014-7-22 21:28
香川老师你好：
我现在遇到另外一种凑数情况，麻烦指导一下，如图所示。把100分给这几个地区，怎么样分配能使分配之后，每个地区的数量除以指导线这个值 几个区最接近。
数量都是整数，或者说是我们可以设定一个误差值，比如让最终除以的结果，几个区的误差值在5%以内。不考虑数据本来不合理，根本就不能够达到误差5%以内。
或者其他任何方法，自己没有思路，不一定是我说的这样，就类似于这种求最优解的问题，麻烦香川老师给点指导，多谢！

---

作者: 香川群子    时间: 2014-7-23 08:56

ghostjiao 发表于 2014-7-22 21:28
香川老师你好：
我现在遇到另外一种凑数情况，麻烦指导一下，如图所示。把100分给这几个地区，怎么样分配能 ...

你这个根本就是小学生问题：

指导线总和=150，因此分配权重=100/150=2/3
然后每个地区按=Round([指导线]*[权重],0) 四舍五入计算、最后个别调整一下即可。

---

作者: ghostjiao    时间: 2014-7-23 09:17

香川群子 发表于 2014-7-23 08:56
你这个根本就是小学生问题：

指导线总和=150，因此分配权重=100/150=2/3

...这个，实际上要复杂点，我想想换个模拟方法，多谢！

---

作者: 香川群子    时间: 2014-7-23 09:20

ghostjiao 发表于 2014-7-23 09:17
...这个，实际上要复杂点，我想想换个模拟方法，多谢！

那就老老实实地把实际问题提出来……

模拟也许能说明问题，但也可能无法替代实际，反而让别人误入歧途。

---

作者: Kelidai    时间: 2014-8-17 13:05
学习了，太强大了。

---

作者: 香川群子    时间: 2014-8-17 14:27

Kelidai 发表于 2014-8-17 13:05
学习了，太强大了。

我这帖子发了大半年了……你咋才来呀？ 你还是不是香川粉？！

---

作者: barry1126    时间: 2014-9-8 21:41
工作中碰到的事情：我是超市的一名出纳，工作中经常有人来买购物卡，人家说开办公用品1025元，我要给人家附个明细，现在都是手工凑单太累，所以才有了这个想法，请大师帮忙，谢谢！ (, 下载次数: 40)

上传

点击文件名下载附件

---

作者: 香川群子    时间: 2014-9-9 09:02

barry1126 发表于 2014-9-8 21:41
工作中碰到的事情：我是超市的一名出纳，工作中经常有人来买购物卡，人家说开办公用品1025元，我要给人家附 ...

你的问题很实际，但也不太容易。

因为数据种类比较多，所以任意一个金额的有效组合都有成千上万种，这反而造成问题。


所以，你必须明确规则：
1. 是否规格个数有限制？
比如，我只用2种规格就能凑出1025元，行不行？

2. 如果规格是否有优先权？
比如，某些规格尽量含有

3. 所配个数是否有数量限制？或者任意？


…………
为简化计算，建议：
一、是否可以先生成一些基本模板，如 500元、750元、1000元……
然后在此基础上适当增减调整。

这样，凑数要求就只是25元、132元这样较小的范围了。

呵呵。

---

作者: barry1126    时间: 2014-9-9 10:38

香川群子 发表于 2014-9-9 09:02
你的问题很实际，但也不太容易。

因为数据种类比较多，所以任意一个金额的有效组合都有成千上万种，这 ...

谢谢大师！
我把最原始的表格再发给你，原来只有品名、单价、单位，根据这些进行凑单。 (, 下载次数: 33)

上传

点击文件名下载附件

你说的几个问题：
1、关于个数。原则是钱少条目相对就少，钱多相对就多。如果1000元有四五个条目也就够了，如果是500元三个条目也够了，如果是10000元的话，可以上升到十个或者十五个条目。
2、关于规格是否有优先权的问题。我的想法是点一下凑单出一种结果，觉得不满意，再点一次如果可能再出一次结果。不知能否实现。
3、所配个数，跟第一条一样。
4、关于预先生成的基本模板问题。条目、个数都是固定的，我怕老板说为什么每都是这几个，尽量有所差别

在这里再次谢谢楼主。

---

作者: 香川群子    时间: 2014-9-9 10:48

barry1126 发表于 2014-9-9 10:38
谢谢大师！
我把最原始的表格再发给你，原来只有品名、单价、单位，根据这些进行凑单。

1、关于个数。
既然你心目中是有一定的原则的，那么如果需要设计宏进行自动操作，你首先必须把你的规则具体化。

而不能只是口头说几条……计算机不认你的这几个简单规则的。

你先把这个问题落实、解决了，我再看看。

其它的部分暂时不能进入考虑。

---

作者: 香川群子    时间: 2014-9-9 10:50

barry1126 发表于 2014-9-9 10:38
谢谢大师！
我把最原始的表格再发给你，原来只有品名、单价、单位，根据这些进行凑单。

2、关于规格是否有优先权的问题。

我的想法是点一下凑单出一种结果，觉得不满意，再点一次如果可能再出一次结果。不知能否实现。

这个可以通过随机算法处理。问题不大。

---

作者: 香川群子    时间: 2014-9-9 10:53

barry1126 发表于 2014-9-9 10:38
谢谢大师！
我把最原始的表格再发给你，原来只有品名、单价、单位，根据这些进行凑单。

3、所配个数，跟第一条一样。

这个可能你没有明白我的问题：
我是说，选定某种规格以后，可取数量是否有某种限制？

比如，规格-1 我选了 200个，规格-2选了 1个，规格-3选了1个……这样合理吗？

还是需要都在一定范围内？

另外，其中某些规格的结果，是否必须是：
规格-1 数量 > 规格-2 数量，不能反过来？（反过来就不合理了。）

这个也有些复杂的，我很担心在这些个地方会有较复杂的限制因素。

呵呵。

---

作者: 香川群子    时间: 2014-9-9 10:55

barry1126 发表于 2014-9-9 10:38
谢谢大师！
我把最原始的表格再发给你，原来只有品名、单价、单位，根据这些进行凑单。

4、关于预先生成的基本模板问题。条目、个数都是固定的，
我怕老板说为什么每都是这几个，尽量有所差别


老板是哪一个？是你的店老板，还是要求开发票的客户老板？


为什么每次都是这几个……是指的同一个客户老板，经常来开票时，需要每次不同的明细？


…………
不管怎么说，有了模板，在模板上略作改动，总比每次直接计算要简易的多。

---

作者: barry1126    时间: 2014-9-9 11:53

香川群子 发表于 2014-9-9 10:55
4、关于预先生成的基本模板问题。条目、个数都是固定的，
我怕老板说为什么每都是这几个，尽量有所差别
...

谢谢楼主的讲解，受益匪浅。
1、能不能把条目设成一个变量，比如当我看到总金额500元的时候，我手动输入条目4条，当我看到1000元的时候，手动输入条目6条，以此累推，然后按条目进行求解。 (, 下载次数: 67)

上传

点击文件名下载附件

2、对于规格没有特别限制。比如1000元总额，条目6条。规格1-100条，规格2-10条，规格3-20条，规格4-1条，规格5-1条，规格6-1条，只要够条目，怎么组合都是可以的。
3、关于模板的问题。模板可能有，但要是能做相应的调整更好一些。一个是应付我们内部的财务检查，不能每次开出的明细都一样。另外就是老顾客，一样的金额，不能每次都给一样的明细条目。

---

作者: 天地有雪    时间: 2014-9-9 12:32
收藏学习！谢谢香川老师分享！

---

作者: 香川群子    时间: 2014-9-9 12:37
这样吧，采用两种方法：
一、完全随机算法
1. 输入总金额
2. 输入规格条目数

然后随机出结果。

二、手动指定条目
1. 输入总金额
2. 勾选规格条目

然后在指定规格条目的基础上计算。


…………
等我有时间，先把第1个完全随机的算法搞出来。

希望你先提供 5-10份合适的、有效的清单，以供参考。

---

作者: 香川群子    时间: 2014-9-9 15:05

barry1126 发表于 2014-9-8 21:41
工作中碰到的事情：我是超市的一名出纳，工作中经常有人来买购物卡，人家说开办公用品1025元，我要给人家附 ...

以后请直接到这里去回帖、提要求。

http://club.excelhome.net/forum. ... =1150861&extra=

---

作者: 香川群子    时间: 2014-9-10 14:21

barry1126 发表于 2014-9-9 11:53
谢谢楼主的讲解，受益匪浅。
1、能不能把条目设成一个变量，比如当我看到总金额500元的时候，我手动输入 ...

问题已解决，请去下面链接查看。

http://club.excelhome.net/forum. ... 861&pid=7844468

---

作者: barry1126    时间: 2014-9-15 08:44
楼主无私的精神，值得我们学习。楼主强大的技术功底，更值得我们学习。谢谢香川群子。这几天回老家，没得上网。

---

欢迎光临 ExcelHome技术论坛 (https://club.excelhome.net/)

Powered by Discuz! X3.4