求1-n个数总和符合目标值的 高效【组合递归方法】

香川群子

vbaplus 发表于 2013-1-18 13:18
在看了你的代码后，然后我根据我对你的思路的理解，自己尝试着写出来了，最后比对细节上和你的写法有细微 ...

呵呵，效果是一样的。

就是不知道计算速度上有多大差异。

香川群子

香川群子 发表于 2013-1-17 15:18
嗯。

我记得我一开始也是有这一段代码的，后来自己把它删掉了。

今天又测试了代码，发现是：ElseIf sj(j, 1) > r + h2 Then 这一句代码惹的祸！


因为 If sj(j, 1) > r + h2 这个If判断需要计算、比对，还是比较耗时的。

而ElseIf的代码结构，使得不能避免计算重复。

vbaplus

香川群子 发表于 2013-1-18 16:41
今天又测试了代码，发现是：ElseIf sj(j, 1) > r + h2 Then 这一句代码惹的祸！

我也在测试这个代码

vbaplus

香川群子 发表于 2013-1-18 16:41
今天又测试了代码，发现是：ElseIf sj(j, 1) > r + h2 Then 这一句代码惹的祸！

个人觉得这个解释有些牵强，elseIf sj(j, 1) > r + h2 Then 固然需要计算比对而耗时，但如果在sj(j, 1) > r + h2第一次出现时不退出循环的话，会一直循环到 i-1 个，每循环一次，都要进行sj(j,1)>=r and sj(j,1)<=r+h2的计算和比对，尽管都不会成立，但计算和比对的消耗的时间加在一起会大大超过第一次判断sj(j, 1) > r + h2时计算比对并退出循环的时间。

不知道这样理解对不对。

vbaplus

香川群子 发表于 2013-1-18 16:41
今天又测试了代码，发现是：ElseIf sj(j, 1) > r + h2 Then 这一句代码惹的祸！

而且你的递归算法中，我觉得还有一个不能忽视的BUG，虽然在主程序中限制了65536的结果显示数据，但在递归过程中，结果数如果超过 jg数组的 redim边界的话，会报超出边界的错误。所以我觉得主程序中结果数组的定义应该改进一下，在定义大小上不应首先根据行数限制边界，而直接根据combin(m,n)来定义结果数组，先存放所有结果，然后显示时，根据界面行数选择结果数。当然，这样做也有个问题，内存有限制，也可以根据结果的内存需求量与combin(m,n)数来联合决定 结果数组的大小。

香川群子

vbaplus 发表于 2013-1-18 22:52
而且你的递归算法中，我觉得还有一个不能忽视的BUG，虽然在主程序中限制了65536的结果显示数据，但在递归 ...

首先，如果组合结果数量很多，那么输出全部结果基本上是没有实际意义的。

其次，符合目标总和的结果总数，远比组合可能数要少。

最后，你有一个错误认识必须给予纠正：
组合总数不是combin(m,n)而是combin(m,1)……直到combin(m,n)的总和，
即我前面已经说过的二进制结果=2^m-1

vbaplus

香川群子 发表于 2013-1-19 13:29
首先，如果组合结果数量很多，那么输出全部结果基本上是没有实际意义的。

其次，符合目标总和的结果总 ...

你知道我说的combin(m,n)不是指的所有组合的数量，因为所有的组合并不需要作为结果来存放。
你说的combin(m,1)+combin(m,2)+。。。。+combin(m,n)只存在于不设定取值个数n的大小的情况。

不管取所有的值有没有意义，但如果在递归过程中结果数没有得到控制的话，jg数组就会有越界的报错问题，这就是BUG。我没有想好更好的结束递归的办法才提出以上建议方法，我想过，如果用if k>65536 then exit sub的方式的话，应该会有无操作的空递归直到结束，不算是个好办法，所以才想着以上的建议。

vbaplus

而且我回过头来用你主楼中的代码来测试的话，发现很多结果都漏掉了，不知道为什么。
比如我用1~20的20个序列数作为原始数，取值范围为35到80，取值个设置为8.
如果用你主楼中的代码，只得到313个结果。而且用差值的算法，得到的结果49889个，而且我用字典检测过，没有重复值。不知道为什么。

香川群子

vbaplus 发表于 2013-1-19 22:31
而且我回过头来用你主楼中的代码来测试的话，发现很多结果都漏掉了，不知道为什么。
比如我用1~20的20个序 ...

1楼附件中有一个bug没有更新。
但1楼代码已经更新过，如果重新按照1楼代码运算那结果就是正确的。49889个解。

错误原因是循环中多了Exit Sub一句没有注释掉，因此提前结束了。

vbaplus

香川群子 发表于 2013-1-20 00:51
1楼附件中有一个bug没有更新。
但1楼代码已经更新过，如果重新按照1楼代码运算那结果就是正确的。49889个 ...

哦，原来代码和附件不一样，看的是帖子，测试的是附件，真不巧。

谢谢香川群子的这个帖子，让我学到了不少东西，最重要的是让我领会到了递归算法的精髓，尽管不一定参透了。