| |
▼教えてください さん：
> 59
> 45
> 31
> 11
> 32
>
>という5つの数字があるとします。この5つの数字を使って74になる組合せを
>探したいときにどのようにすればよいのですか？（すべて足し算での組合せ。上の例では31と11と32を足したことが知りたいのです。）教えてください。
ここまでの話であれば簡単に答えは出ます。
問題なのは
>ちなみに実際には30個ぐらいの数字からＸになる組合せを見つけなければならないのです…。
こちらです。
少なくとも組み合わせる個数をある程度絞らないと大変な量ですよ。
教えてください さんの例で数字が５個なら
59 = 59
45 = 45
59 + 45 = 104
31 = 31
59 + 31 = 90
45 + 31 = 76
59 + 45 + 31 = 135
11 = 11
59 + 11 = 70
45 + 11 = 56
59 + 45 + 11 = 115
31 + 11 = 42
59 + 31 + 11 = 101
45 + 31 + 11 = 87
59 + 45 + 31 + 11 = 146
32 = 32
59 + 32 = 91
45 + 32 = 77
59 + 45 + 32 = 136
31 + 32 = 63
59 + 31 + 32 = 122
45 + 31 + 32 = 108
59 + 45 + 31 + 32 = 167
11 + 32 = 43
59 + 11 + 32 = 102
45 + 11 + 32 = 88
59 + 45 + 11 + 32 = 147
31 + 11 + 32 = 74 ←ヒット
59 + 31 + 11 + 32 = 133
45 + 31 + 11 + 32 = 119
59 + 45 + 31 + 11 + 32 = 178
の全３１通りで簡単に出ます。（コードは下記）
この組み合わせの数は「=2^5-1」で求められます。
例えば数字が６個なら「=2^6-1」で６３通り、
数字が１０個なら「=2^10-1」で１,０２３通りです。
つまり組み合わせの数は数字が１つ増えるごとに倍になり、「２のｎ乗−１」となります。
で、これが３０個になると「=2^30-1」で１,０７３,７４１,８２４通りとなります。
具体的に言うと「=(2^30)/65536/256」、シートを６４枚フルで使うことになります。
>30個ぐらいの数字からＸになる組合せを見つけなければならないのです…。
このままの条件だと、普通に考えて１０億個以上の組み合わせが出てくることになりますよ^^
それと、処理時間の問題もあります。
私のショボイＰＣとコード（「(２のｎ乗−１)ｘｎ」回ループ）だと、
１５個・・・6秒849
１６個・・・12秒457
１７個・・・27秒678
２０個・・・4分9秒218
ほぼ理論通り倍になっていきます。
１５個で約７秒とすると理論的には
「=7*(2^15)/60/60」で約６４時間
最新の高速パソコンを使用しても丸１日はかかりそうです。
※高速化を図れる可能性は多分にありますが組み合わせが
１,０７３,７４１,８２４通りあることには変わりません。
さらに、結果をどこかに格納する処理を加えることを考えると・・・
いずれにしても現実的ではないですね^^
参考までに、サンプルです。
Ａ列に任意の数字を入れてテストしてください。
※最初は１５行ぐらいまでで実行してください。
それ以降は１行増えるごとに処理時間が約倍になると思ってください。
'*****************************************************************************************************
Sub test()
Dim rend As Long, tmp As Long
Dim i As Long, j As Long
Dim res As String
Const req As Long = 74
rend = Range("A65536").End(xlUp).Row
For i = 1 To 2 ^ rend - 1
tmp = 0
res = ""
For j = 1 To rend
If (i And 2 ^ (j - 1)) <> 0 Then
tmp = tmp + Cells(j , 1).Value
If res <> "" Then res = res & " + "
res = res & Cells(j , 1).Value
End If
Next j
' Debug.Print res & " = " & tmp
If tmp <> req Then Debug.Print res
Next i
End Sub
|
|
漂流民
- 06/9/13(水) 0:24 -
