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

wuxianyu86

这么好的贴，才看见，标记一下

sdfsadfsa

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

但显然这样得到的结 ...

香川老师，能不能在这个例子的条件上，要求程序输出最大的数值组合结果。比如1到100，步长为1，求101的目标值，输出最大组合数是50组，最大组合数值累加是5050（当然程序输出结果是这样）；但我有组数据，要求组合个数是2到4之间，其数值范围是140.5到143.0，数值长度是39有7个，33.85有20个，31.88有20个，47有6个，37有1个，却输出不了最大的组合数值

香川群子

sdfsadfsa 发表于 2018-10-13 14:06
香川老师，能不能在这个例子的条件上，要求程序输出最大的数值组合结果。比如1到100，步长为1，求101的目 ...

你是要这样分配吗：

142.64=31.88+31.88+31.88+47
142.64=31.88+31.88+31.88+47
142.64=31.88+31.88+31.88+47
142.64=31.88+31.88+31.88+47
142.64=31.88+31.88+31.88+47
142.64=31.88+31.88+31.88+47
141.76=39+39+31.88+31.88
140.55=39+33.85+33.85+33.85
140.55=39+33.85+33.85+33.85
140.55=39+33.85+33.85+33.85
140.55=39+33.85+33.85+33.85
140.55=39+33.85+33.85+33.85
138.55=33.85+33.85+33.85+37
67.7=33.85+33.85

sdfsadfsa

香川群子 发表于 2018-10-15 09:33
你是要这样分配吗：

142.64=31.88+31.88+31.88+47

首先非常感谢，香川老师的回复，没想到香川老师这么忙，也会不计利益抽空回答我，非常感谢

那我直接开门见山了，实在抱歉，上面的数值长度写错了，正确的数值长度是39有8个，33.85有20个，31.88有20个，47有6个，37有2个；

39 +33.85+33.85+33.85=140.55
39 +33.85+33.85+33.85=140.55
39 +33.85+33.85+33.85=140.55
39 +33.85+33.85+33.85=140.55
39 +33.85+33.85+33.85=140.55
39 +33.85+33.85+33.85=140.55

47 +31.88+31.88+31.88=142.64
47 +31.88+31.88+31.88=142.64
47 +31.88+31.88+31.88=142.64
47 +31.88+31.88+31.88=142.64
47 +31.88+31.88+31.88=142.64
47 +31.88+31.88+31.88=142.64

33.85+31.88 +39 + 37=141.73
33.85+31.88 +39 + 37=141.73

刚好其数值范围是140.5到143.0；
这只是我已知的可行解，不知道是不是唯一解，但可以在数值范围里所有长度数值全部利用到了；

我的需求就是希望程序输出，在条件1、数值范围里，条件2、组合个数的限定条件下，求全部组合累加的最大值数解；比如在这例子中，我如果开始用47+47+47=141的组合，最终递归结果就有几个数值组合不了；
不知道这个问题难不难，跟求最少损耗差不多，因为我工作之一是车间排单，人工这样凑数时间效率低，出错率高

香川群子

sdfsadfsa 发表于 2018-10-15 11:44
首先非常感谢，香川老师的回复，没想到香川老师这么忙，也会不计利益抽空回答我，非常感谢

那我直接开 ...

不是唯一解吧：

142.64=31.88+31.88+31.88+47
142.64=31.88+31.88+31.88+47
142.64=31.88+31.88+31.88+47
142.64=31.88+31.88+31.88+47
142.64=31.88+31.88+31.88+47
142.64=31.88+31.88+31.88+47

141.76=39+39+31.88+31.88
141.7=33.85+33.85+37+37

140.55=39+33.85+33.85+33.85
140.55=39+33.85+33.85+33.85
140.55=39+33.85+33.85+33.85
140.55=39+33.85+33.85+33.85
140.55=39+33.85+33.85+33.85
140.55=39+33.85+33.85+33.85

结果都用上，也就可以了吧。

sdfsadfsa

香川群子 发表于 2018-10-15 17:36
不是唯一解吧：

142.64=31.88+31.88+31.88+47

可以啊，我就是想要这样的效果，苦于自己没这能力做

sdfsadfsa

香川群子 发表于 2018-10-15 17:36
不是唯一解吧：

142.64=31.88+31.88+31.88+47

可以程序发给我吗，我愿意给香川老师发个小红包

yeshuangyong

很遗憾，不知是不会用还是怎么有些没法算，组合元素不能重复，比如3+3+3+5？

香川群子

yeshuangyong 发表于 2018-10-16 17:05
很遗憾，不知是不会用还是怎么有些没法算，组合元素不能重复，比如3+3+3+5？

组合元素中有相同数字重复出现时是可以计算的，
如果你有10个3、8个5，求和=14，那么3+3+3+5=14可以算出来的。

……
但是，如果你只提供3和5这2个数字，要从中凑出14，这个程序做不到。
需要另外的程序。

ccczzzfff

香川群子 发表于 2014-1-1 15:07
彭版出的题目的帖子
http://club.excelhome.net/forum.php?mod=viewthread&tid=151178&page=7#pid6353576
...

香川老师，你这个附件只能算出来有多少种结果吗，怎么样添加一个TextBox把所有结果列出来，比如1+2+3=6这样