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

qianbin0503 · 发表于 2015-7-27 17:50

香川群子发表于 2015-7-26 08:42
找到14组解。涵盖最多行。（包括4个0 为50行）
总和总比例明细
119425963.5 30.000007% +7800000+698 ...

50行数据有点少（一共960行），是不是调整一下行数，供应商的范围也就会相应扩大呢。看能不能重新筛选一下，由于之前没接触过宏，也不知道该怎么使用，麻烦您啦~

cgl201 · 发表于 2015-8-8 12:10

香川老师你好，用了您的程序，却提示溢出堆栈空间，请问该如何处理，你的代码我实在不知该如何修改，谢谢！
附件为我的数据代入到您的程序之后

香川群子 · 发表于 2015-8-8 14:46

cgl201 发表于 2015-8-8 12:10
香川老师你好，用了您的程序，却提示溢出堆栈空间，请问该如何处理，你的代码我实在不知该如何修改，谢谢！ ...

目测你的数据都是100以上的整数，所以不可能有匹配 224045778的结果……不会有78

另外，重复数太多，全部1000多个数据，组合量太大了，不可能全部算一遍。

建议先把基础数量扣除，只需计算少量的数据匹配要求即可。

cgl201 · 发表于 2015-8-8 22:38

香川群子发表于 2015-8-8 14:46
目测你的数据都是100以上的整数，所以不可能有匹配 224045778的结果……不会有78

另外，重复数太多， ...

哦，好的，谢谢。

香川群子 · 发表于 2015-8-9 08:36

cgl201 发表于 2015-8-8 22:38
哦，好的，谢谢。

按下面方法计算：

1. 目标总额=224045778
确认不可能有正好78的尾数，只能截取 105304+429272=534576 是尾数最接近的。

2. 提取重复部分总额=181712600
因此剩余=224045778-181712600-534576=41798600

3. 剩余444个不重复总额87185711.5中，计算=41798600的组合，有很多、很多个。

取第1个组合得到总额=224045776，结果如下：

234项的组合：
组合元素个数金额
1711500 1 1711500
1400000 1 1400000
1286000 1 1286000
1248000 1 1248000
1180000 1 1180000
860000 1 860000
782000 1 782000
658400 1 658400
610000 1 610000
558000 1 558000
504500 1 504500
490000 1 490000
469600 1 469600
465000 1 465000
450000 3 1350000
444000 1 444000
443900 1 443900
440000 2 880000
436000 1 436000
430000 1 430000
429272 1 429272
429000 1 429000
420000 3 1260000
419000 1 419000
410000 5 2050000
408000 2 816000
405000 1 405000
400000 7 2800000
399800 1 399800
398000 2 796000
395000 1 395000
394000 1 394000
393000 1 393000
390000 8 3120000
389000 2 778000
388000 1 388000
386000 1 386000
384000 1 384000
383000 1 383000
380000 6 2280000
379000 3 1137000
378000 2 756000
377000 1 377000
376000 1 376000
375800 1 375800
374000 3 1122000
370000 15 5550000
365000 6 2190000
362000 1 362000
360000 9 3240000
358000 1 358000
356000 2 712000
355000 3 1065000
351000 1 351000
350000 14 4900000
349000 1 349000
347000 1 347000
346000 1 346000
340000 8 2720000
339000 2 678000
336000 2 672000
334000 4 1336000
333000 3 999000
330000 11 3630000
329900 1 329900
329000 1 329000
328000 1 328000
327000 1 327000
326000 3 978000
324000 2 648000
323000 1 323000
322000 3 966000
321000 1 321000
320000 18 5760000
319000 1 319000
318000 3 954000
317000 1 317000
315000 4 1260000
313000 4 1252000
312000 1 312000
310000 26 8060000
309000 1 309000
308000 3 924000
306000 2 612000
303000 2 606000
302000 2 604000
301000 1 301000
300000 36 10800000
298000 4 1192000
297000 3 891000
296000 3 888000
295000 4 1180000
294000 1 294000
293000 1 293000
291800 1 291800
290000 21 6090000
289000 3 867000
288000 1 288000
280000 23 6440000
279000 1 279000
278000 3 834000
277000 3 831000
276000 1 276000
275000 3 825000
273000 4 1092000
270000 19 5130000
269000 5 1345000
268000 1 268000
266000 4 1064000
265000 2 530000
264000 3 792000
263000 4 1052000
261000 2 522000
260000 30 7800000
258000 1 258000
257000 5 1285000
256000 8 2048000
255000 12 3060000
254000 5 1270000
253000 1 253000
250000 35 8750000
249000 5 1245000
248000 1 248000
247000 2 494000
246000 3 738000
245000 7 1715000
244000 4 976000
242000 3 726000
240000 21 5040000
239800 1 239800
237000 4 948000
230800 1 230800
230000 19 4370000
225000 3 675000
224000 1 224000
223000 1 223000
220000 27 5940000
219000 1 219000
217000 3 651000
216000 1 216000
210000 10 2100000
205000 2 410000
200000 27 5400000
196000 1 196000
195000 3 585000
190000 15 2850000
187000 1 187000
185000 1 185000
183800 1 183800
180000 15 2700000
176800 1 176800
170000 14 2380000
168000 2 336000
167000 2 334000
166000 1 166000
165000 2 330000
160000 8 1280000
150000 15 2250000
149800 2 299600
145800 3 437400
143000 1 143000
140000 6 840000
135000 1 135000
134800 1 134800
132800 1 132800
130000 1 130000
129800 2 259600
124800 4 499200
123300 1 123300
120900 1 120900
120000 5 600000
115900 1 115900
114700 1 114700
113000 1 113000
110800 3 332400
110000 10 1100000
108800 2 217600
106000 2 212000
105304 1 105304
103000 2 206000
100000 9 900000
98900 1 98900
98800 1 98800
95900 1 95900
93800 1 93800
92800 1 92800
91800 1 91800
90000 1 90000
89900 3 269700
85800 1 85800
85300 2 170600
84900 1 84900
84800 1 84800
83800 2 167600
83000 1 83000
82900 5 414500
82800 1 82800
81900 1 81900
81800 2 163600
80000 2 160000
77400 1 77400
76800 1 76800
75900 1 75900
74900 2 149800
74600 1 74600
73900 3 221700
72000 1 72000
70900 1 70900
69800 1 69800
67000 2 134000
66600 1 66600
65900 2 131800
65000 1 65000
63800 2 127600
59800 1 59800
58300 1 58300
58000 3 174000
57900 1 57900
57800 1 57800
57200 1 57200
55900 2 111800
55300 1 55300
54900 1 54900
54800 1 54800
53900 2 107800
52300 2 104600
51800 3 155400
49800 1 49800
45800 1 45800
44800 1 44800
44500 1 44500
44400 2 88800
43800 3 131400
42900 2 85800

snyn168 · 发表于 2015-8-24 11:19

Sub dgH4(r&, s$, i&, t&)
Dim j&, r2&, s2$, t1&
If L * (k = L) Then Exit Sub '设定了求解个数L且满足k=L时退出
请教下，这个*是不是应该改为and？

香川群子 · 发表于 2015-8-25 18:13

snyn168 发表于 2015-8-24 11:19
Sub dgH4(r&, s$, i&, t&)
Dim j&, r2&, s2$, t1&
If L * (k = L) Then Exit Sub '设定了求解个 ...

If 条件判断时，And 就是对两个条件式的 * 运算，Or 是对两个条件式的 + 运算。

所以，是一回事。

vslqdivu · 发表于 2015-8-31 17:28

香川老师，我有5000个小数。需要从这些数字中凑数使它们的和是《=500的最大数，请问，用您的附件可以做出来吗？谢谢。您的代码太复杂，小白看不懂。

香川群子 · 发表于 2015-8-31 22:27

vslqdivu 发表于 2015-8-31 17:28
香川老师，我有5000个小数。需要从这些数字中凑数使它们的和是《=500的最大数，请问，用您的附件可以做出来 ...

你的问题需要我怎么回答？我说不可以是什么理由？我说可以又是什么理由？

s542546486 · 发表于 2015-9-28 15:49

学习了，必须顶顶{:soso_e113:}

		自动登录	找回密码
密码			免费注册

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