有关数字组合的问题请求帮助

aiboboy

又有新问题出来了,请看有金额的那文件,求哪位高手能帮忙处理一下,刚入门,狼版主的代码有些地方看不懂啊,请狼版主再帮忙看一下吧,谢谢

[ 本帖最后由 aiboboy 于 2008-12-28 11:19 编辑 ]

dsp5000

重量不超过300，体积不超过400的所有组合?

你给的数据全部符合要求啊，用高级筛选就可以了。

northwolves

动态规划。不知有多少组解？

aiboboy

需要要一个用VBA解决的办法

northwolves

方案太多，把计算规模减小了一半(http://blog.csdn.net/northwolves/archive/2008/12/20/3563350.aspx)：

1. 
   
2. Sub getit()
   
3.     Dim s() As String, i&, j&, k&, l&, n&, t, v, w, temp$, sum1&, sum2&
   
4.     t = Sheet1.[a2:c41]
   
5.     sum1 = 170
   
6.     sum2 = 200
   
7.     ReDim s(UBound(t), sum1, sum2)
   
8. 
   
9.     For i = 1 To UBound(t)
   
10.         If t(i, 2) <= sum1 And t(i, 3) <= sum2 Then s(1, t(i, 2), t(i, 3)) = t(i, 1)
    
11.     Next
    
12. 
    
13.     For j = 2 To UBound(t)
    
14.         For k = 1 To sum1
    
15.             For l = 1 To sum2
    
16.                 If s(j - 1, k, l) > "" Then
    
17.                     v = Split(s(j - 1, k, l))
    
18.                     For m = 0 To UBound(v)
    
19.                         If Not v(m) Like "*" & UBound(t) Then
    
20.                             w = Split(v(m), ",")
    
21.                             For i = Val(w(UBound(w))) + 1 To UBound(t)
    
22.                                 If k + t(i, 2) <= sum1 And l + t(i, 3) <= sum2 Then s(j, k + t(i, 2), l + t(i, 3)) = Trim(s(j, k + t(i, 2), l + t(i, 3)) & " " & v(m) & "," & t(i, 1))
    
23.                             Next
    
24.                         End If
    
25.                     Next
    
26.                 End If
    
27.             Next
    
28.         Next
    
29.     Next
    
30.     ReDim v(65535, 1 To 3)
    
31.     v(0, 1) = "序号"
    
32.     v(0, 2) = "重量"
    
33.     v(0, 3) = "体积"
    
34.     For k = 1 To sum1
    
35.         For l = 1 To sum2
    
36.             For j = 1 To UBound(t)
    
37.                 If s(j, k, l) > "" Then
    
38.                     w = Split(s(j, k, l))
    
39.                     For m = 0 To UBound(w)
    
40.                         n = n + 1
    
41.                         v(n, 1) = w(m)
    
42.                         v(n, 2) = k
    
43.                         v(n, 3) = l
    
44.                     Next
    
45.                 End If
    
46.             Next j, l, k
    
47.             Sheet2.[a1].Resize(n, 3) = v
    
48.         End Sub
    
49. 
    

复制代码

[ 本帖最后由 northwolves 于 2008-12-22 16:15 编辑 ]

xiangchendub

狼版用DP解决的话，楼主的数据密度很大，按道理不应该占很多内存。
改换机器了
其实可以只算重量，范围从 25 - 300 用一个布尔数组标记即可，
在合乎要求的组合中再 check 体积。

Merry Xmas guys

northwolves

原帖由 xiangchendub 于 2008-12-22 17:22 发表
狼版用DP解决的话，楼主的数据密度很大，按道理不应该占很多内存。
改换机器了
其实可以只算重量，范围从 25 - 300 用一个布尔数组标记即可，
在合乎要求的组合中再 check 体积。

Merry Xmas guys

有道理，有空时再看看。
Merry Xmas too.

aiboboy

谢谢狼行，我先试试

灰袍法师

很明显
只要不超过20个数的重量组合，都能满足体积要求
只要超过20个数的重量组合，都不满足体积要求
所以就是取最多20个数字，使其重量不超过300

由于最小的数都是25, 重量限制是300, 所以最多只能取 300 / 25 -1 = 11个数
也就是说，根本不需要check体积

楼主的数据这么有规律，直接分情况讨论就好了

只有一个数，很明显是40种
只有两个数， 也很明显是 combin(40,2)种
只有三个数， 也很明显是 combin(40,3)种
只有四个数， 也很明显是 combin(40,4)种

只有五个数，300 - 5*25 = 175
原问题等价于从 0-39取5个数，不超过175

只有六个数，300 - 6*25 = 150
原问题等价于从 0-39取5个数，不超过150
........
只有10个数，300 - 10*25 = 50
原问题等价于从 0-39取10个数，不超过50

只有11个数，300 - 11*25 = 25
原问题等价于从 0-39取11个数，不超过25 (不可能满足要求)

很简单嘛

[ 本帖最后由 灰袍法师 于 2008-12-25 11:55 编辑 ]