複数の数字の中からどれかを足して合計を出す方法

いつもお世話になっております。
過去にも同様の質問がありましたが、ナップザック問題について教えていただきたく思います。

エクセルのＡ列に５０個程の数値（千円単位～１千万円単位）が入っています。
その中のどれかを足し合わせて、特定の数字を探したいのです。
（求めたい数字21,069,182）

（例）
１０
５　
１２
２
なら、１５になるのは１０と５の組み合わせで、１０と５を求めるような感じです。

過去の質問を読み、エクセルのＶＢＡをコピーしてやったりしましたが、フリーズしてしまったり、オーバフローなどになってしまいます。
５０個と数字が多いのが問題なのでしょうか・・・

何か良い方法がございましたら、ご教授いただきたく思います。
よろしくお願いします。

No.1 ベストアンサー 回答者： noname#140971 回答日時： 2007/08/18 14:06

一介の服飾デザイナですが、パッと思い付いたアルゴリズムは次のようです。

まず、クイックソートでもバブルソートでも構わないので昇順に並べます。

2,5,10,12

2+5---------------7 (7+5=12 next)
2+5+10------------17 (stop)

2+10--------------12 (2+10+10=22 Stop)

2+12--------------14 (Stop)

5+10--------------15 hit

10----------------10 (10+10 Stop)

次に、小さい数字から順次足していきます。
次を加算するのは、同じ数字を足して目的値に等しいか以下である場合。
もちろん、結果オーバーしていれば即抜けます。

次を加算するべきか否かは、最初の１個でも判定する必要があります。
そうすれば、10以上はテストする必要がないことが判ります。

プログラマでも何でもないので参考程度にして下さい。

この回答へのお礼

ご回答ありがとうございます。

例がちょっと言葉足らずであったかもしれませんが、
二つの数字のみで答えが出るとは限らないんです。
５０個の数値のうち２５個足して数字が出るか
あるいは４０個足して数字が出るか・・・

この場合、難しいですよねぇ・・・

お礼日時：2007/08/18 17:37

No.2 回答者： zap35 回答日時： 2007/08/18 15:48

どのようなVBAを試されたのか分からないのですが、総当たり法では2^50-1通りの計算が必要になり、EXCELの有効桁数を超えてしまいます。

下記URLの動的計画法をお試しになってはいかがでしょうか。
（既にお試しなら読み飛ばしてください）

ただし時間がかかるのは覚悟してください。フリーズと見えても本当に計算中なのだと思いますよ。

http://www.geocities.co.jp/SiliconValley-Oakland …

この回答へのお礼

ご回答ありがとうございます。

動的方法を試しましたが、やはりフリーズしてしまいました。
メモリが少ないので、５０個の数値は厳しいです・・・

お礼日時：2007/08/19 20:23

No.3 回答者： noname#140971 回答日時： 2007/08/18 19:40

そのナップザック問題に関しては無知ですが、２個でも３０個でも同じじゃないですかね。

No.4 回答者： noname#140971 回答日時： 2007/08/18 20:34

ちょっと、回答に自信がなかったのでコードを書いてみました。

確かに、100になる組み合わせを見つけました。
もちろん、素人が酒飲みながら書いたコード。
ちゃんと URL のやり方を参照されて下さい。

[イミディエイト]
10, 15, 20, 25, 30,

Private Sub Command1_Click()
　　Dim H　　　　 As Integer
　　Dim I　　　　 As Integer
　　Dim N　　　　 As Integer
　　Dim M　　　　 As Integer
　　Dim Target　　As Integer
　　Dim Amount(9) As Long
　　Dim strUnit　 As String
　　
　　Amount(0) = 10: Amount(1) = 20: Amount(2) = 30: Amount(3) = 40: Amount(4) = 50
　　Amount(5) = 45: Amount(6) = 35: Amount(7) = 25: Amount(8) = 15: Amount(9) = 5
　　' ------------
　　'　昇順ソート
　　' ------------
　　QSort Amount(), 0, UBound(Amount())
　　' ----------------------------------
　　'　100 になる組合せを求める
　　' ----------------------------------
　　Target = 100
　　For I = 0 To 9
　　　　strUnit = Str(Amount(I)) & ","
　　　　M = Amount(I)
　　　　H = I + 1
　　　　If M = Target Then
　　　　　　Debug.Print strUnit
　　　　ElseIf M * 2 <= Target Then
　　　　　　For J = H To 9
　　　　　　　　M = M + Amount(J)
　　　　　　　　strUnit = strUnit & Str(Amount(J)) & ","
　　　　　　　　If M = Target Then
　　　　　　　　　　Debug.Print strUnit
　　　　　　　　　　Exit For
　　　　　　　　ElseIf M + Amount(J) > Target Then
　　　　　　　　　　Exit For
　　　　　　　　End If
　　　　　　Next J
　　　　End If
　　Next I
End Sub

Public Sub QSort(ByRef Datas() As Long, ByVal intTop As Integer, ByVal intLast As Integer)
　　Dim I As Integer
　　Dim J As Integer
　　Dim R As Integer
　　Dim N As Integer
　　Dim Temp As Long
　　Dim Part As Long

　　N = intLast - intTop + 1
　　If N < 2 Then
　　　　Exit Sub
　　End If
　　Part = Datas(intTop + Int(N / 2))
　　I = intTop - 1
　　J = intLast + 1
　　Do
　　　　Do
　　　　　　I = I + 1
　　　　Loop While Datas(I) < Part
　　　　Do
　　　　　　J = J - 1
　　　　Loop While Datas(J) > Part
　　　　If (I < J) Then
　　　　　　Temp = Datas(I): Datas(I) = Datas(J): Datas(J) = Temp
　　　　End If
　　Loop Until (I >= J)
　　R = N - I
　　QSort Datas(), 0, I - 1
　　QSort Datas(), I, I + R - 1
End Sub

この回答へのお礼

ご回答ありがとうございます。

ＵＲＬの方法を参考にしながらやってみましたが、フリーズしてしまって先に進めない状態です。
２０個位の少ない数字なら大丈夫なんでしょうけど、５０個もあり、
しかも桁が多い場合は時間ばかりかかり答えを求めるのは不可能なようですね・・・

お礼日時：2007/08/19 20:32

No.5 回答者： noname#140971 回答日時： 2007/08/19 21:24

総当り法のコードを眺めてみました。

事前に昇順ソートされていないデータを総当りしている感じですね。
問題は、コードを真似るのではなくアルゴリズムを理解すること。
例えば、クイックソートのアルゴリズムを理解するのに私はカードを使いました。
「あー、なるほど。このような要領で並び替えているのか」
コードを書くというのは、決して、知的な作業ではないです。
一旦、アルゴリズムを理解してしまえば、コード書きは単なる肉体労働です。
先ずは、アルゴリズムを「ガッテン！」と思うまで解読されたし。

なお、私の回答は、組み合わせは求めることが可能。
だが、エクセルのどのセルかには答えられません。
しかし、値と取り込む際に、10,20,15,234 を 10.01, 20.02,15.03,234.04と変換して取り込めば、それも可能です。

No.6 回答者： noname#140971 回答日時： 2007/08/20 08:02

総当り法・・・なるほどですね。

私の書いたコードは、さらに、修正しなきゃならんですね。

私が見つけているのは、最も、多い要素での組み合わせ。
次は、それより１個少ない組み合わせを見つけにゃならんですね。
そういう意味では、次のループは最初の検索のそれ。

総当り法・・・なるほどですね。
酒飲みながら書くようなコードじゃなかったですね。
反省！

No.7 回答者： noname#140971 回答日時： 2007/08/20 08:17

ゴミ回答をしたので、もう、少し補足しておきます。

５つの組み合わせがみつかったら、その要素同士の組合せの個数分だけチェック。

1+5->6
1+5+6->12
5+6->11

6、11、12があれば、それも組合せ。
次は、これを一つづ見つけなきゃならんですね。

まあ、しんどい話ですね。
だが、これで　Husky流のアルゴリズムは見えてきたと思います。
なお、軽々な回答、お詫びしておきます。