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

香川群子

suxianchun1 发表于 2017-7-30 08:22
老师您好  剪枝算法是根据金额排序后 得出结果 ， 我现在有个需求是要按照日期排序，根据日期在前的金额 ...

数据不排序，也能计算。但是就无法使用剪枝算法了，实际计算效率会低很多、很多。

如果数据量不大，也可以算。

【另外一种思路】，你先按照日期顺序，贴一部分数据上去，开始凑数。
如果正好凑数成功，那么把用过的数据删去以后，接着贴后面日期的数据上去，继续接着算……

虽然麻烦一点，但是效果可以自己掌握。

如果凑不出结果，那就再贴一部分日期的数据上去。

suxianchun1

香川群子 发表于 2017-7-30 10:43
数据不排序，也能计算。但是就无法使用剪枝算法了，实际计算效率会低很多、很多。

如果数据量不大，也 ...

恩 明白您第二种思路，就是先按照日期排序拿出一部分数据进行筛选，找不到在添加一部分数据，但是遇到一种情况，数据量大的时候找不到，会等很久程序还没有结束。

香川群子

suxianchun1 发表于 2017-7-30 12:19
恩 明白您第二种思路，就是先按照日期排序拿出一部分数据进行筛选，找不到在添加一部分数据，但是遇到一 ...

如果数据量大，有时计算会耗费很长很长的时间……这个是没有办法的事情了。

只要求在一定范围内匹配还好，如果要求必须完全相等的匹配，那么计算量会很大的。
因此，如有可能，应该将原始数据进行筛选，只输入可能用关联的数据进行计算，
肯定无关的数据应该事先排除，这样就可以尽量减少组合计算量。

suxianchun1

香川群子 发表于 2017-7-30 14:56
如果数据量大，有时计算会耗费很长很长的时间……这个是没有办法的事情了。

只要求在一定范围内匹配还 ...

谢谢老师，我明白您的意思了，您说如果用01背包问题规划求解是不是可以呢？  这个我研究了下，但是没太看懂 ，但是感觉应该可以

香川群子

suxianchun1 发表于 2017-7-31 13:11
谢谢老师，我明白您的意思了，您说如果用01背包问题规划求解是不是可以呢？  这个我研究了下，但是没太看 ...

背包问题的动态规划求解算法，局限性太大。
只能计算元素个数较少，总额不太大的整数。

单纯说凑数程序，我这个是最好的。

我已经反复说了，如果希望减少计算量，那么实现进行一定的条件筛选，
仅对可能性大的数据进行凑数计算，是最应该做到的基本条件。

否则，大量数据将使组合可能性指数式上升，即使用银河计算机也算不过来的。

另外，如果要求计算精确匹配（完全相等）可能就会困难一点。

……总之，要根据实际情形，自己做一定的处理。

鄂龙蒙

老师：学习您的作品，长知识了。
您的作品是N个数取数凑数。我现在有个顺序求和小于或等于设定值，思考了好长时间，用小于等于只是取第一个数，用等于不是刚好取到最后一个值，用范围判断时，这个范围又不好确定，能否打扰您有空帮看下？谢谢！
http://club.excelhome.net/thread-1360783-1-1.html

香川群子

鄂龙蒙 发表于 2017-8-3 17:00
老师：学习您的作品，长知识了。
您的作品是N个数取数凑数。我现在有个顺序求和小于或等于设定值，思考了 ...

没明白你的意思，举几个例子说明一下吧。

鄂龙蒙

香川群子 发表于 2017-8-3 19:34
没明白你的意思，举几个例子说明一下吧。

感谢您老师百忙之中回复！
是这样的：A列有多行【不确定行数】的数，从A1向下【A2-A3-A4........】连续相加，事先设定了一个值，想得到从A1向下连续相加的数，最接近【等于或小于】设定的值时，那个数的行号。

香川群子

鄂龙蒙 发表于 2017-8-3 20:11
感谢您老师百忙之中回复！
是这样的：A列有多行【不确定行数】的数，从A1向下【A2-A3-A4........】连续 ...

你这还是太抽象，举几个数字说明一下。

deepbox

向高手学习，非常好的资料