2014新年元旦第一强帖：实用凑数凑金额高效递归剪枝算法

gaoxt2005

太厉害了！！！！帮我解决了个实际的问题！！感恩！

townyee

非常强大的技术贴，受教了！

香川群子

对2014版，做一个简单的强化更新。

第一，Long整数范围仍较小，处理数值数位较大时容易溢出。
因此，改成Dec十进制数类型，这样基本上不会有取数范围太大的问题了。

第二，很多人提出，希望快速标识组合结果是那几行组成的。
因此，改进如下：选中J列组合结果之后点击按钮，即可黄色高亮显示该组合的所有元素。
选中不同行的不同组合之后点击按钮，可以更新黄色显示。
如果选中J1再点击按钮，可以取消当前黄色显示。

以上。

备注，希望大家使用前，好好看一下代码注释。
最起码看懂参数设置方法。

' 《凑数、凑金额的实用多功能强化版》 by kagawa 2014-01-01
'  2017-7-7更新 增加回溯 以便快速计算得到部分结果
'  2021-4-21 数值由Long整数改为CDec十进制数计算模式

'  经Excel Home 香川群子 的深入研究, 采用排序以后的差值递归、末位搜索、
'  当前位超过剩余值剪枝、当前位剩余和不足剪枝、递归计算深度参数控制等技
'  最后产生了目前最好的Excel VBA 高速高效的组合求和递归剪枝算法。
'  可处理小数、负数、重复数等各种情况
'  通过指定小数位数、指定目标和值范围、组合个数范围、指定求解个数、递归计算深度等参数使用
'  可以得到很多有趣的效果、可以满足几乎所有之前要求凑数、凑金额的求助帖子
'  我愿意公开此代码以便大家使用和学习
'========================================================================================
'Dim sj(), jg(), dic, d&, d1&, h, h0#, h1, h2, h3#, k&, l&, l2&, m&, n&, n2&, t2&, cnt&, cnt0&, cnt1&, cnt2&, tms#

'递归用公用变量定义：
' sj(): 存放递归用原始数据的数组,已经过升序预处理含[原始数值]、[小数位转换为十进制数值]、[剪枝用累计和]
' jg(): 存放递归计算结果的数组,含组合个数、组合总和、组合明细、递归计算深度
' dic:  原始数据有重复时用来排除重复的字典dic
' d:    d=[b3] 指定小数位数d
' d1:   [b12]=d1 元素重复个数(用于是否有重复元素需要使用字典的判断)

' h:    h=[b1] 目标和值 转为Dec十进制数
' h0#:  目标和值下限 双精度原始值
' h1:   [b11]=h1 有负数时负数累计总和h1
' h2:   h2=[b2] 目标和值上限。并计算转换为和值上限、下限的差值h2 转为Dec十进制数
' h3#:  目标和值上限 双精度原始值
' h和h2 有3种组合类型：
'       [h,0]→[h,h]输出完全匹配=h的组合；
'       [h<h2]输出[h,h2]范围组合；  即以h2位上限、h为下限的求和范围
'       [h>h2]输出[h-h2,h]范围组合。即以h为上限目标 h2(h2<h时)为差值 的求和范围

' k:    [b7]=k 组合结果存入jg数组时的序号、计算得到的组合结果总数
' l:    l=[b6] jg()数组的最大下标=限制计算以及输出到工作表的最大行数l
'       留空时不限制计算、但输出默认为<65530行
'       l=-1时输出组合结果到txt文本文件
' l2:   统计组合结果文本长度最大值 因为超过911时不能进行数组直接输出

' m:    原始数据中待组合元素个数m
' n:    n=[b4] 指定组合元素个数下限n
' n2:   n2=[b5] 指定组合元素个数上限n2
' n和n2 共有4种组合类型：
'       [0,0]→[0,m]输出全部组合；[n,0]→[n,n]匹配=n的组合；
'       [0,n2]→输出0-n2范围组合；[n,n2]→输出n-n2组合。

' t2:   t2=[b14] 允许回溯时的t值限制 有扩大计算深度的效果
' cnt:  [b8]=cnt 递归计算次数
' cnt0: cnt0=[b15] 递归计算深度(默认留空时=2^16即65536次递归)
'       初次计算无解则改输入=-1 就遍历计算全部组合无限制(大量计算可能会陷入假死循环)
' cnt1: 递归计算深度 有解时归零、或未达到允许回溯的t值时归零
' cnt2: [b13]=cnt2 递归计算深度的最大值记录

香川群子

如果看不懂参数设置方法，可以慢慢提问。

chenwenming

香川群子 发表于 2021-4-23 19:29
如果看不懂参数设置方法，可以慢慢提问。

已知X1+X2=100,X1*Y1=200,X2*Y2=50,且X1、X2、Y1、Y2正整数，求X1、X2、Y1、Y2的值？表格如何凑？

huanghai22

chenwenming 发表于 2021-7-14 22:42
已知X1+X2=100,X1*Y1=200,X2*Y2=50,且X1、X2、Y1、Y2正整数，求X1、X2、Y1、Y2的值？表格如何凑？

X1、X2、Y1、Y2为正正数，因为Y2=50/X2,即X2<=50,当X2=50时，X1=100-X2=50,Y1=200/X1=40
所以X1=50,X2=50,Y1=4,Y2=1

小当家123

老师，我测试了一下，计算单个目标值和计算区间输出的结果不一样，可以看看是哪里不对呢？
目标值为85，输出结果为56+29；目标值为[85,88]，输出结果为70+15.5或者72+15.5
我的组合元素为（56,15.5,55,29,29,41,41,60,72,154,127.5,41,62.5,49,166.5,91.5,49.9,116,65,67.5,155.5,70,89.5,63,46,15.5）

香川群子

小当家123 发表于 2021-8-1 09:07
老师，我测试了一下，计算单个目标值和计算区间输出的结果不一样，可以看看是哪里不对呢？
目标值为85，输 ...

如果你要计算得到全部组合，那么B7参数【求解结果数l】应该清空。
你现在是输入=2，所以计算得到2个组合结果时就停止计算了。

应该有7组解：
+72+15.5
+70+15.5
+56+29
+56+15.5+15.5
+55+15.5+15.5
+46+41
+41+29+15.5

德贤

插个楼，求一个各位大佬怎么实现这个过程。B数组的每一个数据都是A数组n个数据的和，在求解中，如果A数组的某个数据已经被使用，则不再使用第二次。即B数组的每一个与A数组的每个数存在1对一、一对多的情况，但不存在交叉。算完所有对应关系后，将A数组的特征值放在B数组数据之后。结果已上传，请教各位老师VBA可以实现这个功能么？

小当家123

香川群子 发表于 2021-8-1 19:25
如果你要计算得到全部组合，那么B7参数【求解结果数l】应该清空。
你现在是输入=2，所以计算得到2个组合 ...

好的，谢谢！