Excel VBA質問箱 IV

当質問箱は、有志のボランティア精神のおかげで成り立っています。
問題が解決したら、必ずお礼をしましょうね。
本サイトの基本方針をまとめました。こちら をご一読ください。

投稿種別の選択が必要です。ご注意ください。
迷惑投稿防止のため、URLの入力を制限しています。ご了承ください。


39374 / 76732 ←次へ | 前へ→

【42471】Re:組合せ
発言  漂流民  - 06/9/13(水) 0:24 -

引用なし
パスワード
   ▼教えてください さん:
>  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

0 hits

【42432】組合せ 教えてください 06/9/11(月) 23:32 質問
【42467】Re:組合せ [名前なし] 06/9/12(火) 21:05 発言
【42471】Re:組合せ 漂流民 06/9/13(水) 0:24 発言
【42472】Re:組合せ ナイスプログラム 06/9/13(水) 1:07 回答
【42473】Re:組合せ ichinose 06/9/13(水) 6:37 発言
【42529】Re:組合せ ナイスプログラム 06/9/13(水) 21:58 回答
【42556】Re:組合せ 教えてください 06/9/14(木) 23:04 お礼

39374 / 76732 ←次へ | 前へ→
ページ:  ┃  記事番号:
2610219
(SS)C-BOARD v3.8 is Free