VB5.0 & Oracleで開発しています。
DBに
No 数字
1 200
2 600
3 400
4 600
5 100
6 300
のようなデータがあり、
ユーザーさんが値を指定すると、
Noが小さいレコードから優先的に使用し、
指定した数字が合計値になるプログラムを組みたいのですが、
例:1700と入力した場合、
Noが1、2、4、6のレコードを自動的に選択する(200+600+600+300=1700)
実際には抽出されるレコードは、
百レコード近くになる予定なのですが…
どのように組んだらいいのか、
ほんとうに困っています。
どうかよろしくご教授お願いいたします。
No.8ベストアンサー
- 回答日時:
サンプルです。
テキストボックス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
- 回答日時:
計算途中の枝切り(例えば合計値を超えた場合の計算打ち切り)だけでは計算時間の最悪値が変わらないので、その条件だけでは「何兆年もかかるかもしれない」という点は変わりません。
枝切りに加えて、必ず実用的な範囲内で枝切りが行われるように入力数値の範囲を制限するとか、制限時間を設けるとかしないといけません。
でも制限時間の導入はともかく、「入力数値の範囲制限」てのは難しいんだなぁ。
入力を制限すれば計算時間が短くなるのは確かなんだが、1000兆年が1年に縮んでも非実用的であることに変わりはないわけで、縮めるなら「1分以内」とかにする必要があるわけです。しかし「入力の範囲をこう絞れば、計算結果は1分以内に出る」と定性的に求めるのが難しい。
SEに「あんたの言う条件で問題を解くのは数学で有名なNP完全問題で、えらい時間がかかる場合があるけど、いいのか?」と聞いて、SEに判断させることも考慮したほうがいいですね。
ありがとうございます。
御礼が遅くなって申し訳ありません。
教えていただいたサンプルを組み込んで、
SEに「数学で有名なNP完全問題で、えらい時間がかかる場合がある」と伝えたところ、
どうやら仕様が変更しそうです…
この仕事を続けていくには、
勉強が足りなさすぎると実感しましたので、もっと勉強しようと思います。
本当にありがとうございました。
今後ともなにかありましたら、よろしくお願いいたします。
No.7
- 回答日時:
改行とスペースをちょっと付け直しました。
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
- 回答日時:
#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.4
- 回答日時:
#1回答者です。
選択するレコードの数の制限がないようですので、これはナップザック問題になりそうです。
ナップザック問題
http://hwb.ecc.u-tokyo.ac.jp/current/CDD1B8ECBDB …
△100個の荷物から、もっとも20kgに近い組み合わせを選ぶ「ナップザック問題」
最新のパソコンで10兆年かかる。挑戦中。
http://shop.kodansha.jp/bc2_bc/search_view.jsp?b …
・・・というような問題です。
何らかの制限を加えないと、常に現実的な時間で解が求まる保証がありません。
動的計画法
http://www.na.cse.nagoya-u.ac.jp/~reiji/lect/alg …
に述べられているように、レコードに入っている数字が比較的小さな整数である場合には、レコードの1個目~m個目を使う場合についてあらかじめ総当りの計算をしておき、それをもとに1個目~(m+1)個目を使う場合を求める・・・をレコード全体(n個目)になるまで繰り返す、という方法もあります。
この方法は、大きな整数の場合、あるいは実数(浮動小数点数)の場合、mが増えるに従って総当りの計算結果を保存しておくバッファの大きさが指数的に増えてしまうので非現実的です。
あるいは、組み合わせの数を仮に「最大5個まで」と制限すれば、5重ループを回せば総当りが可能なので、レコード数の5乗のオーダーで解を求めることができます。
とにかく、何らかの制限を加えないことには、正確な解を現実的な時間で求めることはできません。(・・・多分。私が勘違いしている可能性もありますが。)
No.3
- 回答日時:
答えではありませんが。
。。。1.取り敢えず全てのレコードをListBoxに表示させる。
2.ユーザーさんがListBox上で選択したレコードを
ListBox2に表示させる。
3.ListBox2の合計を計算する。
4.期待していた数値の過不足を表示する。
このプロセスのなかで自動計算方法試行を検討するか
ユーザーさんにもこのプロトタイプを見せて検討して
頂く。
回答ありがとうございます。
残念ながら、ユーザーさんと直接お話できる立場にないのです…
SEに言っても、やれの一点張りで、
仕様の変更は、今のところありえないのです…
でも、いざとなったらこんな方法もありますと
使わせていただきます。ありがとうございます。
No.2
- 回答日時:
(1)番号が小さいものから、充当していく、というルールだけではないでしょう。
それなら余り難しくない。そのばあいでも(2)はどうするのでしょうか。
(2)指定合計値にぴったり合う組み合わせがない場合(この実証もプログラムが大変と思うが)、「組み合わせがありません」と出して終わりですか。
(3)こういう問題はVBの問題でなく、数学を応用すべき問題で、カテゴリが不適と思いますが。SEは、判らないとき、誰に聞くか、どの分野の書籍・WEBなどに当たるか、どういう聞き方をするか、のセンスも重要だと思いますが。
要求仕様書に質問の通り、もし書いたら、質問続出か、(1)で組まれて
後で問題化するとおもいますが。
この回答への補足
回答ありがとうございます。
補足ですが、
(1)は、それだけのルールで悩んでいます…
(2)については「組み合わせがありません」のメッセージを出すだけで終了です。
(3)のご意見ですが、私が思っていることそのままなのです…実は私はSEではありません、プログラマなのですが、要求仕様書など何もなく、SEからは、どうやってやるのかわからないけど、絶対にやってと言われて、口述で…本当に困っているのです…よろしくお願いいたします。
カテゴリ不適だとすると、どちらに質問すればいいのかも教えていただけると助かるのですが…
No.1
- 回答日時:
「どう組んだら」以前に、抽出条件が不明確(曖昧)です。
例えば、例示のデータの場合で600と入力したら、結果は「2」ですか、それとも「1,3」ですか。900と入力したら、結果は「2,6」ですか、それとも「1,3,5」ですか。
「1,100」と「2,99」の数字の和が入力値に一致する場合、結果はどちらですか。「1,100」と「2」だったら?「1,100」と「2,3,4」だったら?
上記のいずれも、質問にある抽出条件だけでは決定できません。抽出条件を補足願います。
回答ありがとうございます。
説明不足ですみません…
たとえば、600と入力した場合ですが、
抽出結果は、1、3としたいのです、
「1、100」と「2、99」の場合は、「1、100」を
「1,100」と「2」でも「1,100」を
「1,100」と「2,3,4」でも「1,100」を
優先させなくてはいけないのです。
とにかくNo が小さいものを含む組み合わせ
を抽出したいのです。よろしくお願いいたします。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- その他(データベース) Accessのクエリで1フィールドの抽出条件設定をNullでなく全角半角含む空白のみの文字列でない文 1 2023/04/24 15:20
- その他(データベース) Accessフォームからパラメーターで表示したレコードを指定のExcelのセルへ転送する方法について 2 2022/08/22 18:04
- Access(アクセス) アクセスの更新クエリでカレントレコードのみ更新したい 1 2022/06/02 23:32
- その他(データベース) 更新クエリをリンクデータベーステーブルに実行し実行時エラー3362固有インデックスに重複する値が含ま 1 2022/09/21 11:44
- Excel(エクセル) SUMIF関数について 4 2023/06/14 13:13
- Visual Basic(VBA) 複数ファイルのデータの統合について 12 2022/05/14 12:03
- Visual Basic(VBA) VBA初心者です 検索した数字の行に色をつける 5 2023/02/13 14:22
- スピーカー・コンポ・ステレオ レコードのマトリクス番号の見方を教えてください。 最近レコードの知識が少しずつ増え、最近マトリクス番 1 2022/08/14 13:58
- Excel(エクセル) Excelの1つのセルにそれぞれ文字+数字が入力されていて、 数字のみ抽出して合計したいです。(合計 4 2023/03/16 23:44
- Visual Basic(VBA) Excel VBA 複数ブックシートごとにデータを統合する方法について 4 2022/05/20 14:23
関連するカテゴリからQ&Aを探す
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
ワードの差込印刷で教えて下さ...
-
DataGridViewの内容をDBに反映...
-
レコードセット(ADO.Recordset)...
-
Access を×ボタンで閉じ...
-
DataGridViewの、選択されてい...
-
サブフォームに新規レコードを...
-
ADO VBA 実行時エラー3021
-
ACCESSで大量の更新を行うと「...
-
ファイル書込みで一行もしくは...
-
JSPのNULLレコード表示について...
-
vbからmdbのレコード削除
-
ヘッダレコードとトレーラレコ...
-
レコード長を数えてくれる関数
-
決定性有限オートマトン
-
GROUP BYを行った後に結合した...
-
抽出したデータを修正して元の...
-
Oracleでの文字列連結サイズの上限
-
【初歩】ラジオボタンをつかっ...
-
外部結合とor条件混在の記述方法
-
select句副問い合わせ 値の個...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
レコードが存在しなかった場合
-
DataGridViewの、選択されてい...
-
ADO VBA 実行時エラー3021
-
差し込み印刷のレコード数について
-
ACCESSで大量の更新を行うと「...
-
ファイル書込みで一行もしくは...
-
カレントレコードが無い事を判...
-
ワードの差込印刷で教えて下さ...
-
アクセスでレポートの1印刷内...
-
DataGridViewの内容をDBに反映...
-
[VBA] ADOの Clone と AddNew
-
固有レコード識別子の選択とは
-
JSPのNULLレコード表示について...
-
Access を×ボタンで閉じ...
-
サブフォームに新規レコードを...
-
データセットのレコード更新が...
-
サブレンジ分割されたNDB(富士...
-
レコードセット(ADO.Recordset)...
-
DataGridViewにてセル以外をク...
-
COBOLでのランダムアクセス
おすすめ情報
