エクセルVBAで、特定の数字になる組み合わせを知りたいのですが・・・

質問

A.5380、B.4730、C.3310、D.2840、E.2360、F.1890、G.1420、H.940
以上８種類の数字を組み合わせて、合計13010ちょうどになる組み合わせをすべて知りたいです。８種類の数字は、同じものを何度組み合わせても構いません。
例えば、A+A+B=○のようにです。

色々自分なりに調べたところ、ソルバーで試してみましたが、組み合わせの数字が複雑な為か、解答はでませんでした。
また、VBAを使用して以下のような例が掲載されていたので試してみましたが、オーバーフローしてしまって答えがでません。
VBAがまったくの初心者のため、どのようにしたら問題が解消されるのかわかりません。
どなたか教えていただけませんでしょうか。お願いします。

' knapsack総当たり
' 目標値と一致する物をすべて求める
'
'by S. Tada

Const N = 8 ' データの数
Dim wa(N) As Long

Sub knap_main()
Dim w As Long, wmax As Long
Dim i As Integer, j As Long, k As Integer
Dim y1 As Integer, y2 As Integer
Dim b As Long

y1 = 1 ' A1:Anにデータを入れておく
y2 = y1 + 1 ' B列以降が結果
For i = 1 To N
wa(i) = Cells(i, y1).Value
Next

wmax = Cells(45, y1).Value ' A45に目標値を入れておく
For j = 1 To 2 ^ N - 1
w = 0
b = 1
For k = 1 To N
If j And b Then w = w + wa(k)
b = b + b
Next
If w = wmax Then
b = 1
For k = 1 To N
If j And b Then Cells(k, y2).Value = wa(k)
b = b + b
Next
y2 = y2 + 1
End If
Next

End Sub

回答No.4

popuplt · ベストアンサー

方法はマクロで８個の数字を繰り返して加算して、合計以下の組み合わせをセルに全部書き出して、フィルタで確認しました。
ちなみに、4,435,200組み合わせ、時間は２分程度でした。（性能によりますが・・・）

Sub test()
kei = 0: mm = 4
For A = 0 To 3: For B = 0 To 3: For C = 0 To 4: For D = 0 To 5
For E = 0 To 6: For F = 0 To 7: For G = 0 To 10: For H = 0 To 14
kei = A * 5380 + B * 4730 + C * 3310 + D * 2840 + E * 2360 + F * 1890 + G * 1420 + H * 940
If kei <= 113010 Then
mm = mm + 1
Cells(mm, 1) = A * 5280: Cells(mm, 2) = B * 4730:Cells(mm, 3) = C * 3310: Cells(mm, 4) = D * 2840
Cells(mm, 5) = E * 2360: Cells(mm, 6) = F * 1890: Cells(mm, 7) = G * 1420: Cells(mm, 8) = H * 940: Cells(mm, 9) = kei
kei = 0
End If
Next: Next: Next: Next: Next: Next: Next: Next
End Sub
手抜きのコードです。あしからず。

回答No.6

imogasi

一案
下記は、この質問の場合の、「枝刈り」に当たるのかな。
枝刈り　http://www.ic-net.or.jp/home/takaken/pz/pz4/index.html
ーー
２行目の数字は、13010をその上の数字で割った整数部に当たる。
これ以上その数＋１を足すとそれだけで13010を超えてしまう。
これらの数字の組み合わせ（ネットワーク的線の全ての通り道の
数）　例
A　X
B　Y
の時AX,AY、BX、BY
ーーー表の列が乱れるかもしれないが修正して考えてください
5380 4730 3310 2840 2360 1890 1420 940
3 3 4 5 6 7 10 14
なし なし なし なし なし なし なし なし
１回 １回 １回 １回 １回 １回 １回 １回
２回 ２回 ２回 ２回 ２回 ２回 ２回 ２回
ー ー ３回 ３回 ３回 ３回 ３回 ３回
ー ー ー ４回 ４回 ４回 ４回 ４回
ー ー ー ー ５回 ５回 ５回 ５回
ー ー ー ー ー ６回 ６回 ６回
ー ー ー ー ー ー ７回 ７回
ー ー ー ー ー ー ８回 ８回
ー ー ー ー ー ー ー ー
ー ー ー ー ー ー ー ー
ー ー ー ー ー ー ー ー
ー ー ー ー ー ー ９回 ９回
ー ー ー ー ー ー ー １０回
ー ー ー ー ー ー ー １１回
ー ー ー ー ー ー ー １２回
ー ー ー ー ー ー ー １３回
ー ー ー ー ー ー ー ー
ー ー ー ー ー ー ↑ ↑
ー ー ー ー ー ー ８回以上
ー ー ー ー ー ー - ８回以上
上記回数以上足すとそれだけで１３０１０を超える。
また８個以上を足すケースは除外して考えない。
だから直前までの組み合わせのケースに加え、１例で説明すると、３３１０の場合なら
（直前の組み合わせ全部）＋なし
（直前の組み合わせ全部）＋3310
（直前の組み合わせ全部）＋3310+3310
（直前の組み合わせ全部）＋3310+3310+3310
をチェックする。
ーーーー
そのときチェックルールとして
（１）項目数が８（「なし」を数に入れず）を超えると、次回の組み合わせから除外する。＜－－質問条件から。
（２）和が13010を超えるとそれ以後の組み合わせは除外する。
（３）13010に等しいときは該当１例
増えこそすれ減らないから、以後の組み合わせの和は13010を必ず超えるから、組み合わせをチェックする必要はない。
＝＝＝
VBAでやってみるかもしれないが、複雑になりそうなので、とりあえず考え方（の１つ）だけ書いてみた。

お礼

ありがとうございます。
色々な方法があるんですね。

回答No.5

mt2008

目的の数値は本当に「13010」ですか？
私もソルバーで確認しましたが、この数値になる組み合わせはありません。
もしかして「130100」とかでは有りませんか？

補足

13010に間違いはないようです。。。

ただ、もしかしたら数値のどれかが間違っているのかもしれません。
仕事で依頼されましたが、当面保留となりました。

回答No.3

Randomize

私も試していましたが、確かに無いですね。
私の回答時に使った積み上げの組み合わせ式の方法を以下に記します。
アナログ/デジタル変換の方法をヒントにした解法の1個です。ブロックを積み上げて行き、ある高さをオーバーしたらそのうちのブロックをより小さなブロックに交換していくという方法です。
Excelの関数のみで計算可能です。下のように作業してください。
-------------------------------------------------------------
A1～H1に8個の数字(A.5380、B.4730、C.3310、D.2840、E.2360、F.1890、G.1420、H.940)を入力してください。
次にJ1に目標数値13010を入力してください。
A2に3を入力してください(全自動ですと更に関数が複雑になるのでここだけは手動で入力してください。)
I2に「=A2*A$1+B2*B$1+C2*C$1+D2*D$1+E2*E$1+F2*F$1+G2*G$1+H2*H$1」と入力してください。
J1に「=I2-$J$1」と入力してください。
I2とJ2をI3とJ3にコピーしてください。
ここからが本番です
A3に「=IF(OR(AND(SUM(B2:$G2)=0,H2<>0),$J$1-A2*A$1<0),IF(A2=0,0,A2-1),A2)」と入力してください。
B3に「=IF(A2=A3+1,ROUNDUP(($J$1-A3*A$1)/B$1,0),IF(OR(A1=A2+1,AND(SUM(C2:$G2)=0,$H2<>0)),IF(B2=0,0,B2-1),B2))」と入力してください。
C3に「=IF(B2=B3+1,INT(($J$1-A3*A$1-B3*B$1)/C$1),IF(OR(B1=B2+1,AND(SUM(D2:$G2)=0,$H2<>0)),IF(C2=0,0,C2-1),C2))」と入力してください。
D3に「=IF(C2=C3+1,ROUNDUP(($J$1-A3*A$1-B3*B$1-C3*C$1)/D$1,0),IF(OR(C1=C2+1,AND(SUM(E2:$G2)=0,$H2<>0)),IF(D2=0,0,D2-1),D2))」と入力してください。
E3に「=IF(D2=D3+1,ROUNDUP(($J$1-A3*A$1-B3*B$1-C3*C$1-D3*D$1)/E$1,0),IF(OR(D1=D2+1,AND(SUM(F2:$G2)=0,$H2<>0)),IF(E2=0,0,E2-1),E2))」と入力してください。
F3に「=IF(E2=E3+1,ROUNDUP(($J$1-A3*A$1-B3*B$1-C3*C$1-D3*D$1-E3*E$1)/F$1,0),IF(OR(E1=E2+1,AND(SUM(G2:$G2)=0,$H2<>0)),IF(F2=0,0,F2-1),F2))」と入力してください。
G3に「=IF(F2=F3+1,ROUNDUP(($J$1-A3*A$1-B3*B$1-C3*C$1-D3*D$1-E3*E$1-F3*F$1)/G$1,0),IF(OR(F1=F2+1,$H2<>0),IF(G2=0,0,G2-1),G2))」と入力してください。
H3に「=IF($J$1-A3*A$1-B3*B$1-C3*C$1-D3*D$1-E3*E$1-F3*F$1-G3*G$1>0,ROUNDUP(($J$1-A3*A$1-B3*B$1-C3*C$1-D3*D$1-E3*E$1-F3*F$1-G3*G$1)/H$1,0),0)」と入力してください。
最後に、A3～J3を下方向へコピーしてください。
そうすると次々と組み合わせ結果が表示されます。
I列はその行の組み合わせ結果のときの合計、J列はその合計と目標数字との差です。色をつけて置くといいでしょう。
あとはオートフィルターをかけるなりして出てきた結果を見てみてください。
-------------------------------------------------------------
No.1さんの言うとおり、これはExcelの問題ではなくアルゴリズムをどう考えるかの問題ですね。
どのように考えたら組み合わせの検討ができるかなと考えて、頭に浮かんだ検討方法を関数なりプログラムなりで記述するとおのずと答えになります。(という意味では答えを書いてしまうのは質問者のためにはならないのですけどね・・・)
なので、ざっとした原理の説明のみにとどめておきます。出てきた結果の数字をにらめっこして、その関数がどのように動いているかを考えてみてください。
ちなみに、A1～H1とJ1の値を変更すると変更した結果に合わせて計算結果の表示も変わります。いろいろ試してみてもよいでしょう。

回答No.2

popuplt

チョット試してみました。
合計が13010以下となる組み合わせは１５７０組ありましたが
合計13010はありませんでした。
間違いがあるかもしれませんので、参考まで。

補足

popupltさん、回答ありがとうございます！
そうですか・・・。ぴったり13010はないんですか・・・。
ちなみに、どのような方法で解いたのでしょうか？？

教えてください！！お願いします！

回答No.1

imogasi

この質問の内容は
エクセル
VBA
の問題ではない。
数字がエクセルのシートに有るからといって、エクセルの問題と
思うのは、本質を見てない。
エクセルはたまたま手近な道具というだけ。
エクセルに少しぐらい詳しくてもこの問題は解けない。
ーーー
主な解決すべき点は、「アルゴリズム（計算方法。処理方法）はどういうようになるか。」
それも「総尽くし法」では時間がかかりすぎるのは、やる前から目に見えている。
工夫して如何に、計算回数量を減らすかがポイント。
ーーーー
数学のカテに、数学的思考に基づき、詳しい人がいて、ヒントを与えてくれるかもしれない。
将棋などのプログラムでは次の取りうる手の組み合わせが膨大で
、どうするかなどの問題も有る。
質問カテゴリの質問者の見当違いだよ。別のカテに質問しては。
ーーー
思いつきだが、例えばデータの最小は９４０で、13010/940+1＝１４の個数以上の個数は足す必要がないとか。
同じように最大値５３８０なので、13010/5380＝2.4なので２個以下は考える必要はない。
ーーー
＞８種類の数字は、同じものを何度組み合わせても構いません
が一段と難しさを大きくしている。８種の数字を何個使ってもよいのか。全て８個を使うということか、あいまい。A+A+B=○の例からたぶん前者か。

お礼

imogasiさん、アドバイスありがとうございました！
8種類の数字は、何度使っても良いし、使わなくても良いので、とにかく13010になる組み合わせが知りたいんです。
仕事で、13010になる組み合わせがあるはずと言われて依頼されたのですが、実はないのでしょうか・・・。
とにかくすごく難しい問題なんですね。
貴重なアドバイスありがとうございました！！