[[20100610115421]]　『数値の表からランダムな数値を組み合わせて、求め』（くるみ）　ページの最後に飛ぶ

『数値の表からランダムな数値を組み合わせて、求めたい数値にさせる組み合わせ』（くるみ）

入金管理をしています。
入金対象の請求データが紛失して、入金がありましたが
どれがその請求であったか分からなくなりました。

分かっていることは、１２０件の入金があるなかで、その中の８０件の
入金を組合せすれば１００万円になるということです。

通帳のイメージで、縦の列に１２０件の金額が並び
その中の８０件の組み合わせをすれば１００万円になるという
回答を導き出したいのですが、お分かりになる方はおられますか。

ＥＸＣＥＬ2003　ＸＰです。宜しくお願いします。

 データによりますが、解が一意になるとは限りません。

 一般解を求めるのでなければ、実際の数値を提示してもらったほうが、
 話は早いと思いますが、会社の情報ですから簡単には出せそうもないですね。

 請求データはどこにも残っていないのですか？
 (Mook)

 120件の中から80件を選ぶ組み合わせは、
 3836の後に0が136くらい並ぶほどの種類があります。
（あっているかな？いずれにしてもそれほど多いということ）

 数式ではほぼ不可能といっていいと思います。
 マクロでは理論上は可能ですが、現実にどれくらい時間がかかるものなのか・・・
 （天地人）

 思い切り衝突！ 同じ内容ですがそのままＵＰします。

 120件から80件を選ぶ組み合わせは、天文学的数字になります。
 従って、プログラムでしらみつぶしに調べるのは不可能。

 データ次第で、何かうまいロジックがあれば別ですが、
 普通に考えたら、答えは出せないのでは？

 入金してきた相手先に聞けないのですか？
　
（純丸）(o^-')b

 二重衝突！ですが同じく、そのままＵＰします。

 実際にはそこまで多くはないと思いますが、EXCEL でしたら
 =COMBIN(120,80)
 で求められます。

 マクロでやるときは実際には枝刈りするので、現実的な時間で解が得られると
 思いますが、複数解がありそうなこと(つまり、苦労しても結局解決しない)
 のほうが問題だと思います。
 (Mook)

 さっきレス前に =COMBIN(120,80) をやってみたのですが、
 33ケタの数字になったので「天文学的数字」と書きました。
 １秒に１兆通りを調べても、３０億年以上かかる計算ですけど、、。 
　
（純丸）(o^-')b

 Mookさんが言っているのはオイラのことでしょう。
 計算違いだったみたいです。
 （天地人）

 ランダムにはランダムで対向～
 という事で、当たるも八卦当たらぬも八卦、完全運任せのコードです。
 私のテストデータでは、最短３秒！　最長・・・ＰＣフリーズ（笑）

 運を天に任せてみましょうか？

 A1:A120に金額データがあるものとします。
 ちなみに、複数の解がある場合でもランダムです（笑）
 ユニークな解かどうかすらチェックしてませんしわかりませんのでご注意を。

  Sub test()
  Dim myC As Object, myRnd(1 To 120, 1 To 1) As Long
  Dim i As Long, j As Long, tbl As Variant, myR As Range
  Set myR = Range("A1:A120") '金額セル
  tbl = myR.Value
  Randomize
  Do
    Set myC = New Collection
    Erase myRnd
    For i = 1 To 120
      myC.Add i
    Next i
    For i = 1 To 80
      j = Int((121 - i) * Rnd + 1)
      myRnd(myC.Item(j), 1) = 1
      myC.Remove (j)
    Next i
  Loop Until Application.WorksheetFunction.SumProduct(tbl, myRnd) = 1000000
  For i = 1 To 120
    If myRnd(i, 1) = 1 Then
      myR.Cells(i).Interior.ColorIndex = 3
    End If
  Next i
  End Sub

 （ｍｏｍｏ）

 ナップサック問題(袋詰め問題)ですネ。
 今月この質問で3件目
 ※『パズルのような…』
 ※『セルの合計となるパターン逆計算』

 総数が20件ぐらいなら一応ソルバーでも出来ますが、
 総数120件では、とても無理です。
 総数15件で約12～15秒、総数20件で約37～40秒かかります。(データの桁数にもよると思いますが・・)
 総数25件で実験を行なったことがありますが、解は見つからない上、3分以上もかかり中断させました
 ソルバーを使用してナップサック問題の解を見つけるには、総数20件前後が限度と思います。(私見です)
 (atiboh)

 枝刈りをすることで全検索に比べて大幅に計算量を減らすことができます。
 ですが、よほど効率のよい方法で桁を半分にできたとしても、１京ですか・・・。

 ちょっと過小評価していたようですね。
 失礼しました。
 (Mook)

コメント返信：

[ 一覧(最新更新順) ]

[[20100610115421]] 『数値の表からランダムな数値を組み合わせて、求め』（くるみ） ページの最後に飛ぶ

[[20100610115421]]　『数値の表からランダムな数値を組み合わせて、求め』（くるみ）　ページの最後に飛ぶ