合計値からの数字の抽出

質問

VB5.0　&　Oracleで開発しています。

DBに
No　　数字
1　　　200
2　　　600
3 　　　400
4 　　　600
5　　　100
6 　　　300

のようなデータがあり、
ユーザーさんが値を指定すると、
Noが小さいレコードから優先的に使用し、
指定した数字が合計値になるプログラムを組みたいのですが、

例：1700と入力した場合、
Noが１、２、４、６のレコードを自動的に選択する（200＋600＋600＋300＝1700）

実際には抽出されるレコードは、
百レコード近くになる予定なのですが…
どのように組んだらいいのか、
ほんとうに困っています。
どうかよろしくご教授お願いいたします。

回答No.8

xcrOSgS2wY · ベストアンサー

サンプルです。

テキストボックスText1、Text2とリストボックスList1、それとコマンドボタンCommand1をフォームに置いてください。Text1がN、Text2がSです。

アルゴリズムのほうは2つ枝切りを追加してあります。（Sがゼロの場合、その先を探索せずに「条件を満たす」と判断する。Sがマイナスの場合、その先を探索せずに「条件を満たさない」と判断する。）

※インデントは全角空白です。ご注意を。

Dim RecordValue(100) As Double
Dim RecordInUse(100) As Boolean

Private Function Combi(ByVal M As Integer, ByVal N As Integer, ByVal S As Double) As Boolean
　　If Abs(S) < 0.1 Then
　　　　Dim i As Integer
　　　　For i = M To N
　　　　　　RecordInUse(i) = False
　　　　Next
　　　　Combi = True
　　　　Exit Function
　　End If

　　If S < 0 Then
　　　　Combi = False
　　　　Exit Function
　　End If

　　If M = N Then
　　　　If Abs(RecordValue(M) - S) < 0.1 Then
　　　　　　RecordInUse(M) = True
　　　　　　Combi = True
　　　　Else
　　　　　　RecordInUse(M) = False
　　　　　　Combi = False
　　　　End If
　　Else
　　　　If Combi(M + 1, N, S - RecordValue(M)) Then
　　　　　　RecordInUse(M) = True
　　　　　　Combi = True
　　　　Else
　　　　　　RecordInUse(M) = False
　　　　　　Combi = Combi(M + 1, N, S)
　　　　End If
　　End If

End Function

Private Function Combination(ByVal N As Integer, ByVal S As Double) As Boolean
　　Dim x As Double
　　x = 1

　　Dim i As Integer
　　For i = 1 To N
　　　　RecordValue(i) = x
　　　　RecordInUse(i) = False
　　　　x = x * 2
　　Next

　　Combination = Combi(1, N, S)

End Function

Private Sub Command1_Click()
　　Dim N As Integer
　　Dim S As Double

　　N = Val(Text1.Text)
　　S = Val(Text2.Text)

　　List1.Clear
　　If Combination(N, S) Then
　　　　Dim i As Integer
　　　　For i = 1 To N
　　　　　　If RecordInUse(i) Then
　　　　　　　　List1.AddItem "No." & Str(i) & ":" & Str(RecordValue(i))
　　　　　　End If
　　　　Next
　　　　MsgBox "Found"
　　Else
　　　　MsgBox "Not Found"
　　End If

End Sub

NとSを入力してボタンを押すと、M番目のレコードの値を2^(M-1)とした場合の組み合わせを検索して表示します。レコードの値が2のべきですので、Sが1から2^N - 1までの整数値であれば、必ず和がその数になる組み合わせが見つかります。

検索時間がもっとも長くかかるのは、組み合わせが見つからない場合です。非常に大きいSを入れればその場合の時間を測ることができます。

当方の環境（P4-3.2GHz）で、コンパイルせずに開発環境内で実行すると、N=24かつ非常に大きいSを入力して検索した場合、検索を終了するまで約10秒かかります。Nを1つ増やすと検索時間はおよそ倍になります。

ですので、この環境でN=100かつ「存在しないS」を入力した場合の検索時間の最悪値は、およそ10 x 2^76秒、つまり7.6 x 10^23秒（24000兆年(笑)）かかる計算になります。

回答No.10

xcrOSgS2wY

計算途中の枝切り（例えば合計値を超えた場合の計算打ち切り）だけでは計算時間の最悪値が変わらないので、その条件だけでは「何兆年もかかるかもしれない」という点は変わりません。

枝切りに加えて、必ず実用的な範囲内で枝切りが行われるように入力数値の範囲を制限するとか、制限時間を設けるとかしないといけません。

でも制限時間の導入はともかく、「入力数値の範囲制限」てのは難しいんだなぁ。

入力を制限すれば計算時間が短くなるのは確かなんだが、1000兆年が1年に縮んでも非実用的であることに変わりはないわけで、縮めるなら「1分以内」とかにする必要があるわけです。しかし「入力の範囲をこう絞れば、計算結果は1分以内に出る」と定性的に求めるのが難しい。

SEに「あんたの言う条件で問題を解くのは数学で有名なNP完全問題で、えらい時間がかかる場合があるけど、いいのか？」と聞いて、SEに判断させることも考慮したほうがいいですね。

お礼

ありがとうございます。
御礼が遅くなって申し訳ありません。
教えていただいたサンプルを組み込んで、
SEに「数学で有名なNP完全問題で、えらい時間がかかる場合がある」と伝えたところ、
どうやら仕様が変更しそうです…

この仕事を続けていくには、
勉強が足りなさすぎると実感しましたので、もっと勉強しようと思います。
本当にありがとうございました。
今後ともなにかありましたら、よろしくお願いいたします。

回答No.9

todo36

> 何らかの制限を加えないと、常に現実的な時間で解が求まる保証がありません。

「リストの値は必ず正整数である」を前提条件としてもいいのでしょうか？＞質問者
計算途中で指定合計値を超えたら、その先を読まなくいいのでかなり楽になる。

お礼

ご意見ありがとうございます。
まだあまりきちんと理解していないのですが、
よく勉強して、きちんと理解したいと思います。

回答No.7

xcrOSgS2wY

改行とスペースをちょっと付け直しました。

1. M = N の場合
　　V(N) <> S であれば R(M, N, S) = φ
　　V(N) = S であれば R(M, N, S) = { N }

2. M < N の場合
　　R(M+1, N, S-V(M)) <> φ であれば R(M, N, S) = { M; R(M+1, N, S-V(M)) }
　　R(M+1, N, S-V(M)) = φ であれば R(M, N, S) = R(M+1, N, S)

回答No.6

xcrOSgS2wY

#2コメント、#3コメントを改めて読み返してみると、遅かろうが何だろうがとにかく動くものを実装してしまって、後始末は上に投げたほうがよさそうな感じですね。

そういうことであれば、こんな感じで。

以下の手順で、レコードのM番目からN番目まで（1 <= M <= N）の値を1個以上使用して、その和がSになるようなレコード番号を求める。

なお、レコードのN番目の値をV(N)と表記する。また、本手順の結果をR(M, N, S)と表記する。

1. M = Nの場合（N番目のレコード1個だけで入力値に一致するかどうかを調べる）
　　V(N) <> SであればR(M, N, S) = φ
　　V(N) = SであればR(M, N, S) = { N }

2. M < Nの場合
　　R(M + 1, N, S - V(M)) <> φであればR(M, N, S) = { M; R(M + 1, N, S - V(M)) }　　R(M + 1, N, S - V(M)) = φであればR(M, N, S) = R(M + 1, N, S)

以上を素直に再帰で実装すれば、ご質問の解はR(1, N, S)の結果になるはずです。

注：

1.は、N番目のレコードの値V(N)が入力値Sに一致すれば、条件を満たす組み合わせは{ N }、という意味です。

また2.は、M番目, M+1番目, M+2番目, ..., N番目のレコードの値のうちいくつかの和が入力値Sに一致するのは、次のいずれかの場合です。

(A) M+1番目, M+2番目, ..., N番目のレコードの値のうちいくつかの和が入力値Sに一致する場合
(B) M+1番目, M+2番目, ..., N番目のレコードの値のうちいくつかの和が、S - V(M)に一致する場合

前者はM番目のレコードを和に加えない場合、後者はM番目のレコードを和に加える場合です。

結果にはなるべく小さい数字を含めるという条件があるようなので、(A)と(B)の両方が成り立つ場合には(B)を優先することになります。つまり、(B)の成立を先に調べ、(B)が成立しない場合に(A)を調べるということです。

回答No.5

fortranxp

#3です。
えっ　SEが上にいるのですか。
SEが解らないアルゴリズムにどうしてPGに
解決できるのでしょうね。

ともかく　そのようなプロトタイプを作って
検討すればイイ答えが思いつくこともあります。
ListBoxはDataGridのほうがいいかも知れません。

お礼

回答ありがとうございました。
仕様も変更になりそうですので、
使わせていただきます。

回答No.4

xcrOSgS2wY

#1回答者です。

選択するレコードの数の制限がないようですので、これはナップザック問題になりそうです。

ナップザック問題
http://hwb.ecc.u-tokyo.ac.jp/current/CDD1B8ECBDB82FA5CAA5C3A5D7A5B6A5C3A5AFCCE4C2EA.html

△100個の荷物から、もっとも20kgに近い組み合わせを選ぶ「ナップザック問題」
　最新のパソコンで10兆年かかる。挑戦中。
http://shop.kodansha.jp/bc2_bc/search_view.jsp?b=2574691

・・・というような問題です。

何らかの制限を加えないと、常に現実的な時間で解が求まる保証がありません。

動的計画法
http://www.na.cse.nagoya-u.ac.jp/~reiji/lect/alg99/sec9-1.html

に述べられているように、レコードに入っている数字が比較的小さな整数である場合には、レコードの1個目～m個目を使う場合についてあらかじめ総当りの計算をしておき、それをもとに1個目～(m+1)個目を使う場合を求める・・・をレコード全体（n個目）になるまで繰り返す、という方法もあります。

この方法は、大きな整数の場合、あるいは実数（浮動小数点数）の場合、mが増えるに従って総当りの計算結果を保存しておくバッファの大きさが指数的に増えてしまうので非現実的です。

あるいは、組み合わせの数を仮に「最大5個まで」と制限すれば、5重ループを回せば総当りが可能なので、レコード数の5乗のオーダーで解を求めることができます。

とにかく、何らかの制限を加えないことには、正確な解を現実的な時間で求めることはできません。（・・・多分。私が勘違いしている可能性もありますが。）

回答No.3

fortranxp

答えではありませんが。。。。
1.取り敢えず全てのレコードをListBoxに表示させる。

2.ユーザーさんがListBox上で選択したレコードを
　ListBox2に表示させる。
3.ListBox2の合計を計算する。

4.期待していた数値の過不足を表示する。

このプロセスのなかで自動計算方法試行を検討するか
ユーザーさんにもこのプロトタイプを見せて検討して
頂く。

お礼

回答ありがとうございます。
残念ながら、ユーザーさんと直接お話できる立場にないのです…
SEに言っても、やれの一点張りで、
仕様の変更は、今のところありえないのです…
でも、いざとなったらこんな方法もありますと
使わせていただきます。ありがとうございます。

回答No.2

imogasi

（１）番号が小さいものから、充当していく、というルールだけではないでしょう。それなら余り難しくない。
そのばあいでも（２）はどうするのでしょうか。
（２）指定合計値にぴったり合う組み合わせがない場合（この実証もプログラムが大変と思うが）、「組み合わせがありません」と出して終わりですか。
（３）こういう問題はVBの問題でなく、数学を応用すべき問題で、カテゴリが不適と思いますが。SEは、判らないとき、誰に聞くか、どの分野の書籍・WEBなどに当たるか、どういう聞き方をするか、のセンスも重要だと思いますが。
要求仕様書に質問の通り、もし書いたら、質問続出か、（１）で組まれて
後で問題化するとおもいますが。

補足

回答ありがとうございます。
補足ですが、
(1)は、それだけのルールで悩んでいます…
(2)については「組み合わせがありません」のメッセージを出すだけで終了です。
(3)のご意見ですが、私が思っていることそのままなのです…実は私はSEではありません、プログラマなのですが、要求仕様書など何もなく、SEからは、どうやってやるのかわからないけど、絶対にやってと言われて、口述で…本当に困っているのです…よろしくお願いいたします。
カテゴリ不適だとすると、どちらに質問すればいいのかも教えていただけると助かるのですが…

回答No.1

xcrOSgS2wY

「どう組んだら」以前に、抽出条件が不明確（曖昧）です。

例えば、例示のデータの場合で600と入力したら、結果は「2」ですか、それとも「1,3」ですか。900と入力したら、結果は「2,6」ですか、それとも「1,3,5」ですか。

「1,100」と「2,99」の数字の和が入力値に一致する場合、結果はどちらですか。「1,100」と「2」だったら？「1,100」と「2,3,4」だったら？

上記のいずれも、質問にある抽出条件だけでは決定できません。抽出条件を補足願います。

お礼

回答ありがとうございます。
説明不足ですみません…
たとえば、600と入力した場合ですが、
抽出結果は、１、３としたいのです、
「1、100」と「2、99」の場合は、「1、100」を
「1,100」と「2」でも「1,100」を
「1,100」と「2,3,4」でも「1,100」を
優先させなくてはいけないのです。
とにかくNo が小さいものを含む組み合わせ
を抽出したいのです。よろしくお願いいたします。