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

香川群子

三坛老窖 发表于 2018-8-30 21:13
这是我设计这组数据的思路，目的是少了906496.18、391006.01、200270.1这三个数中的任意一个，就得不到尾 ...

或者用拉网式排查，设置匹配范围，也可很快得到结果：
这里计算提速的关键是，允许回溯的参数设置。这可以大大提高组合的筛选能力。
原理是，我一般默认设置为深度搜索16层没有找到可以进一步缩小匹配差值的组合时，自动停止继续向下搜索。
这样计算速度可以非常快。（只在某个新增数据位置，再向下搜索较浅的16层即退回进行递归回溯，不再往下遍历了。）

但是，这样一来，肯定无法完成所有组合的遍历，于是接下来我对我的程序做了革命性的改良，
那就是，可以任意设置允许在某个位置没有匹配组合时，继续再进行16层或更多的向下搜素。
理论上，如果我的允许回溯深度继续加大，最终和完成所有遍历组合的结果是一样的。
但是，我可以自由控制允许回溯深度的加大程度，那就对速度的控制有了更大的自由。

哈哈。

香川群子

三坛老窖 发表于 2018-8-30 21:13
这是我设计这组数据的思路，目的是少了906496.18、391006.01、200270.1这三个数中的任意一个，就得不到尾 ...

或者取范围凑数，也可以在较短时间内得到5000-1万组解，从中筛选出正好匹配的组合结果。

我的凑数程序在进行这样的凑数计算时，能够比遍历组合大大提速的关键，
在于：
我一开始设置了递归搜索深度为16层，之后如果没有找到匹配组合，就会直接退出，跳到下一个位置开始新的组合分枝。
这样可以大大加快计算速度（但这样忽略了很多组合），
因此，为了避免漏掉一些近在眼前的可能组合，我设置了允许在某个位置，重新开始向下深度搜索的算法结构。（这个和一开始就设置递归深度，是不一样的）
这样就既保证了一定的计算深度，也得到了很好的计算速度。

当然，把允许回溯深度值设置得很大，那就和遍历全部组合是一样的效果了，因此速度也会慢成蜗牛。

好处时，现在的算法，可以逐步提高回溯深度值，逐步扩大计算范围，逐步增加计算时间，到你无法容忍很长的计算时间时就可以放弃，
而不是一开始就设置遍历全组合，完全停不下来（会在一开始就陷入深度计算陷阱。）

香川群子

或者可以设置匹配范围，计算5000-1万的组合，在这些组合中找到完全匹配解。

香川群子

三坛老窖 发表于 2018-8-30 21:13
这是我设计这组数据的思路，目的是少了906496.18、391006.01、200270.1这三个数中的任意一个，就得不到尾 ...

试过了，用完全随机算法很难找到完全匹配的组合解。

但是能找到=1501234.28，即差1分的解。

不过，这是在不确定组合个数的情况下。
如果能够事先指定这个匹配组合由8个数组成，然后再来计算，则也能很快得到正好=1501234.29的解。

…………
我现在凑数已经有4个工具：
1. 香川递归剪枝组合凑数
    有选择的遍历组合+当前数值大于剩余额剪枝+剩余数之和小于差值剪枝   

2. 香川完全随机分组凑数
    算法是：随机乱序后依次相加得到接近目标值的结果、匹配精度依赖于随机次数。

3. 香川可指定个数的随机分组凑数（可按平均个数分摊为金额接近的几个组）
    算法是：随机得到接近目标值之后，任选组内一个数和组外任选一个数进行随机交换。
                如果结果更接近目标值就接受、继续。直到差异最小，或到指定随机次数后终止。

4. 利用一维排料的随机算法（这个局限性还是比较大，但原理是相通的，算法可以用）

三坛老窖

香川群子 发表于 2018-8-31 11:57
试过了，用完全随机算法很难找到完全匹配的组合解。

但是能找到=1501234.28，即差1分的解。

确实是我小看了你的这个程序。
有针对性的设计了几组数据，你的这个程序都能在可接受的时间范围内找到全部的解！

大、小剪枝可以理解，有选择的遍历组合还是理解不了。你的这个选择，为何不会遗漏可能存在的解？是我设计的数据没能找到你这个程序的命门吗？

给定n个数和一个和值，如果存在的解中，必然包含第一个数，而不包含第二个数，按我的理解，你的这个程序要找到这个解，则必须遍历大于2^（n-1）的空间，尽管依靠大小剪刀可剪除一部分空间，但当n较大时，需要遍历的空间还是目前的计算机难以承受的。

香川群子

cnt1 = cnt1 + 1: If cnt0 Then If cnt1 > cnt0 Then If t < t2 Then cnt1 = 0 Else Exit Sub '允许回溯到t2时 重新向下开始计数
    '指定计算深度cnt0时 当计数cnt1超过cnt0时 开始回溯 如果t回溯到小于t2个数时则允许重新计数 这样可以在剩余t2个数之后延长计算深度
   

蓝色jht

牛牛牛，完美解决了我和几个同事的问题。感谢香川老师！！！
在此复现一下我和同事遇到的问题（也就是需求）：
公司允许每个员工每月报销油票1300元，报销规则很简单，每个人上报油票的总金额等于或大于1300元。
现在我们每人都有若干金额不等的油票，我们想通过大家资源共享互换，尽量把所有的油票最大化的利用起来。

香川群子

三坛老窖 发表于 2018-9-4 16:40
确实是我小看了你的这个程序。
有针对性的设计了几组数据，你的这个程序都能在可接受的时间范围内找到全 ...

这个是应用了分治原理，以及失之毫厘、差之千里的原理。

首先，我把原始数据从大到小降序排序（这个非常重要）
然后，我先从大数开始进行一部分组合，
假设结果和值可以分为2部分，h=h1+h2 其对应的组合元素个数（n=n1+n2）则n1<<n2

即，首先在很少的几个大数组合中找到h1>>h/2，（此时n1并不会很大，而是会很小这样就大大降低组合难度）
于是，在剩余的数中尝试找到h2，但你会发现，如果有解当然很容易就找到了（因为h2已经很小）
如果在一定的<=h2的遍历组合中找不到=h2的解，而是组合结果<>h2，那么我就不用在n1个h1的基础上向下深度遍历搜寻了。因为失之毫厘，再组合下去，也不可能有正好相等的结果，反而是误差越来越大。

于是就可以开始回溯了。

大致是这个原理吧。

香川群子

三坛老窖 发表于 2018-9-4 16:40
确实是我小看了你的这个程序。
有针对性的设计了几组数据，你的这个程序都能在可接受的时间范围内找到全 ...

换个比方吧，假设做一个大型拼图，（几何形状不规则，大小差异很大的那种）
那么我先放入一些大块，占满大部分空间。
然后我就在细节之处做一些遍历修饰，嵌入一些小的模块。
如果所有的小模块都无法嵌入（会超出框架，即找不到=h2的部分），
那么我就认为当前的大块组合已经失效，无需进一步加入中等模块来遍历测试了。

这样就大大节省了时间，也无需真正的遍历。
反之，如果有解，那么解就直接出来了。


顺便解释一下【分治原理】
把n个数分成n1和n2两个集合，
那么n1中的组合之和=h1，n2中的组合之和=h2，h1+h2=h时就是组合解。
这样的计算，会比直接计算遍历n的组合，要省事的多。

理论上，h的所有组合数=h1的组合数*h2的组合数
计算总量并不会减少，但是，如果事先把h2的结果计算并排序，然后再和h1的结果进行区间匹配，就能大大减少实际计算量。

大致是这个原因吧。

火冷

男人们都要被香川老师折服了，真的太厉害，
我之前研究了几天想自己写一个简单的递归，各种碰壁，算法真是大坑，还是拿来主义吧。
我的问题发在http://club.excelhome.net/forum.php?mod=viewthread&tid=1438591&page=1#pid9675843感谢“刀羊”版主的推荐，让我发现了神器。
顺便再请教几个问题：
1、您的算法参数是否考虑搞个函数参数的形式，返回jg数组，这样可移植性比较好。
2、jg是否带有数值的行号(或序号)信息，这样可以根据jg对原始数据进行后续操作。