|
▼教えてください さん:
> 59
> 45
> 31
> 11
> 32
>
>という5つの数字があるとします。この5つの数字を使って74になる組合せを
>探したいときにどのようにすればよいのですか?(すべて足し算での組合せ。上の例では31と11と32を足したことが知りたいのです。)教えてください。
ここまでの話であれば簡単に答えは出ます。
問題なのは
>ちなみに実際には30個ぐらいの数字からXになる組合せを見つけなければならないのです…。
こちらです。
少なくとも組み合わせる個数をある程度絞らないと大変な量ですよ。
教えてください さんの例で数字が5個なら
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
の全31通りで簡単に出ます。(コードは下記)
この組み合わせの数は「=2^5-1」で求められます。
例えば数字が6個なら「=2^6-1」で63通り、
数字が10個なら「=2^10-1」で1,023通りです。
つまり組み合わせの数は数字が1つ増えるごとに倍になり、「2のn乗−1」となります。
で、これが30個になると「=2^30-1」で1,073,741,824通りとなります。
具体的に言うと「=(2^30)/65536/256」、シートを64枚フルで使うことになります。
>30個ぐらいの数字からXになる組合せを見つけなければならないのです…。
このままの条件だと、普通に考えて10億個以上の組み合わせが出てくることになりますよ^^
それと、処理時間の問題もあります。
私のショボイPCとコード(「(2のn乗−1)xn」回ループ)だと、
15個・・・6秒849
16個・・・12秒457
17個・・・27秒678
20個・・・4分9秒218
ほぼ理論通り倍になっていきます。
15個で約7秒とすると理論的には
「=7*(2^15)/60/60」で約64時間
最新の高速パソコンを使用しても丸1日はかかりそうです。
※高速化を図れる可能性は多分にありますが組み合わせが
1,073,741,824通りあることには変わりません。
さらに、結果をどこかに格納する処理を加えることを考えると・・・
いずれにしても現実的ではないですね^^
参考までに、サンプルです。
A列に任意の数字を入れてテストしてください。
※最初は15行ぐらいまでで実行してください。
それ以降は1行増えるごとに処理時間が約倍になると思ってください。
'*****************************************************************************************************
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
|
|