組合せ

質問

1から　i番目まで、数字がランダムに並んでいます。（マイナス数値からプラス数値まで）。
これらの数値の組合せで、組合せの合計値が、ある目標値になる組合せのすべてを発見して、その組合せを1からiの番号で表示したいのです。
目標値は一個だけ定めます。
どのような論理を組めば可能でしょうか。（この論理をエクセルソフトに組み込み計算します）。

回答No.4

ARC

手元のアルゴリズム辞典では、２進数を利用して解くやり方が紹介されています。

例えば、データの個数が８個だとすると、８ビットの２進数を用意してやって、00000001, 00000010, 00000011, …, 11111111 と、順に１ずつ足していきます。そしてそれぞれの過程で１の位置と対応するデータを取り出せば、８個のデータの全ての組み合わせが判定できるわけです。

面白そうなのでちゃちゃっと作ってみました。長整数型を使って最大３１個の数値の組み合わせを得ます。
ちなみにデータ数を３１と指定する(N=30)と、４０億以上の組み合わせを走査しなくてはならなくなる為、開始したら最後、待てど暮らせど終了しない事態に陥ると思います。

Sub test()
　　Const MOKUHYO As Long = 10 '目標値
　　Const N As Long = 13 '(データの個数 - 1)を設定する。1～30を設定。
　　Dim p() As Long 'データ

　　Dim i As Long, j As Long
　　Dim Tag As Long
　　Dim Goukei As Long
　　Dim Table(30) As Long ' 1,2,4,8,16…を格納する
　　Dim Counter As Long

'データを乱数で初期化する
　　ReDim p(N) As Long
　　For i = 0 To N
　　　　p(i) = Int(Rnd() * 11) - 5 '-5～5の乱数をセット
　　Next i

'処理開始
　　'テーブルの初期化
　　For i = 0 To 30
　　　　Table(i) = 2 ^ i
　　Next i
　　'主処理
　　For i = 1 To 2 ^ N
　　　　Goukei = 0
　　　　For j = 0 To N
　　　　　　If (i And Table(j)) <> 0 Then Goukei = Goukei + p(j)
　　　　Next j
　　　　'合計の判定
　　　　If Goukei = MOKUHYO Then
　　　　　　Counter = Counter + 1
　　　　　　For j = 0 To N
　　　　　　　　If (i And Table(j)) <> 0 Then Debug.Print p(j) & " ";
　　　　　　Next j
　　　　　　Debug.Print
　　　　End If
　　Next

'けっかほおこく
　　Debug.Print
　　For i = 0 To N - 1
　　　　Debug.Print p(i) & ", ";
　　Next i
　　Debug.Print p(i)
　　Debug.Print Counter & "個の組み合わせがあります。"
End Sub