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

lby0712

香川群子 发表于 2017-4-15 13:20
直接凑数更简单，5秒钟

10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,36,67,68,69,70

I think you can make your program better ！

香川群子

lby0712 发表于 2017-4-15 13:34
I think you can make your program better ！

呵呵，钻一下牛角尖。

就你的题目例子来说，下面算法可以生成很多满足条件的随机组合。

1. Sub test2()
   
2.     Dim a&(), b&(), dic, h&, h1&, h2&, i&, j&, m&, n&, r1&, r2&, t&, tms#
   
3.     tms = Timer
   
4.    
   
5.     h = 590: h1 = 10: h2 = 70
   
6.     m = 61: n = 21
   
7.    
   
8.     ReDim a(n - 1), b(h1 To h2)
   
9.     t = h
   
10.     For i = 0 To n - 1
    
11.         a(i) = i + h1: b(a(i)) = 1: t = t - a(i)
    
12.     Next
    
13.     For i = n - 1 To 0 Step -1
    
14.         If t Then t = t + a(i): b(a(i)) = 0: If t > i + h2 - n + 1 Then a(i) = i + h2 - n + 1: b(a(i)) = 1: t = t - a(i) Else a(i) = t: b(t) = 1: Exit For
    
15.     Next
    
16.    
    
17.     For j = 1 To 10 '需要生成的组合次数
    
18.         For i = 1 To n * m
    
19.             r1 = Int(Rnd * n): r2 = Int(Rnd * (n - 1) + r1 + 1) Mod n
    
20.             If h1 + h2 < a(r1) + a(r2) Then t = h2 - a(r2) Else t = a(r1) - h1
    
21.             t = Int(Rnd * (t + 1))
    
22.             If b(a(r1) - t) + b(a(r2) + t) = 0 Then
    
23.                 If a(r1) - t <> a(r2) + t Then
    
24.                     b(a(r1)) = 0: b(a(r2)) = 0
    
25.                     a(r1) = a(r1) - t: a(r2) = a(r2) + t
    
26.                     b(a(r1)) = 1: b(a(r2)) = 1
    
27.                 End If
    
28.             End If
    
29.         Next
    
30.         Cells(1, j).Resize(n) = WorksheetFunction.Transpose(a)
    
31.     Next
    
32.    
    
33.     MsgBox Format(Timer - tms, "0.000s")
    
34. End Sub

复制代码

lby0712

香川群子 发表于 2017-4-15 14:49
呵呵，钻一下牛角尖。

就你的题目例子来说，下面算法可以生成很多满足条件的随机组合。

Thank you so much!

vleexhya

想不到EH藏龙卧虎到如此程度。
请问香川群子大侠这个程序不适合求N个数最接近M的组合，这个问题（N个数最接近M的组合），您有没有开贴指导过？
希望百忙中能给予解答，谢谢！

excel8402

香川群子 发表于 2017-4-15 14:49
呵呵，钻一下牛角尖。

就你的题目例子来说，下面算法可以生成很多满足条件的随机组合。

你好，美女，我在用你做的凑数字递归程序，现在实际运用中，有些数字是可以重复用的，要怎么设置呢？

kingty_x

非常好的资源  正在苦于对账系统类似这种问题需要手工干预 太low不说 还需要大量的人工时间 楼主的代码值得我好好研究学习 哪怕能在出现这种情况时给出可能的解 也是系统的一大进步 估计能领先于全省 感谢你的无私分享

iNicol

真心牛逼！

iNicol

高手，刚才试了下，1～100求和为100，你的结果里怎么没有诸如43～12～9～8～7～6～5～4～3～2～1这样的结合呢？

香川群子

iNicol 发表于 2017-6-1 18:13
高手，刚才试了下，1～100求和为100，你的结果里怎么没有诸如43～12～9～8～7～6～5～4～3～2～1这样的结合 ...

一共会有444,793组解。全部输出没意义了。

三次握手

太好了，学习了。