- ベストアンサー
合計値からの数字の抽出
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) 実際には抽出されるレコードは、 百レコード近くになる予定なのですが… どのように組んだらいいのか、 ほんとうに困っています。 どうかよろしくご教授お願いいたします。
- ko-20
- お礼率50% (5/10)
- Visual Basic
- 回答数10
- ありがとう数8
- みんなの回答 (10)
- 専門家の回答
質問者が選んだベストアンサー
サンプルです。 テキストボックス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兆年(笑))かかる計算になります。
その他の回答 (9)
- xcrOSgS2wY
- ベストアンサー率50% (1006/1985)
計算途中の枝切り(例えば合計値を超えた場合の計算打ち切り)だけでは計算時間の最悪値が変わらないので、その条件だけでは「何兆年もかかるかもしれない」という点は変わりません。 枝切りに加えて、必ず実用的な範囲内で枝切りが行われるように入力数値の範囲を制限するとか、制限時間を設けるとかしないといけません。 でも制限時間の導入はともかく、「入力数値の範囲制限」てのは難しいんだなぁ。 入力を制限すれば計算時間が短くなるのは確かなんだが、1000兆年が1年に縮んでも非実用的であることに変わりはないわけで、縮めるなら「1分以内」とかにする必要があるわけです。しかし「入力の範囲をこう絞れば、計算結果は1分以内に出る」と定性的に求めるのが難しい。 SEに「あんたの言う条件で問題を解くのは数学で有名なNP完全問題で、えらい時間がかかる場合があるけど、いいのか?」と聞いて、SEに判断させることも考慮したほうがいいですね。
- todo36
- ベストアンサー率58% (728/1234)
> 何らかの制限を加えないと、常に現実的な時間で解が求まる保証がありません。 「リストの値は必ず正整数である」を前提条件としてもいいのでしょうか?>質問者 計算途中で指定合計値を超えたら、その先を読まなくいいのでかなり楽になる。
お礼
ご意見ありがとうございます。 まだあまりきちんと理解していないのですが、 よく勉強して、きちんと理解したいと思います。
- xcrOSgS2wY
- ベストアンサー率50% (1006/1985)
改行とスペースをちょっと付け直しました。 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)
- xcrOSgS2wY
- ベストアンサー率50% (1006/1985)
#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)を調べるということです。
- fortranxp
- ベストアンサー率26% (181/684)
#3です。 えっ SEが上にいるのですか。 SEが解らないアルゴリズムにどうしてPGに 解決できるのでしょうね。 ともかく そのようなプロトタイプを作って 検討すればイイ答えが思いつくこともあります。 ListBoxはDataGridのほうがいいかも知れません。
お礼
回答ありがとうございました。 仕様も変更になりそうですので、 使わせていただきます。
- xcrOSgS2wY
- ベストアンサー率50% (1006/1985)
#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乗のオーダーで解を求めることができます。 とにかく、何らかの制限を加えないことには、正確な解を現実的な時間で求めることはできません。(・・・多分。私が勘違いしている可能性もありますが。)
- fortranxp
- ベストアンサー率26% (181/684)
答えではありませんが。。。。 1.取り敢えず全てのレコードをListBoxに表示させる。 2.ユーザーさんがListBox上で選択したレコードを ListBox2に表示させる。 3.ListBox2の合計を計算する。 4.期待していた数値の過不足を表示する。 このプロセスのなかで自動計算方法試行を検討するか ユーザーさんにもこのプロトタイプを見せて検討して 頂く。
お礼
回答ありがとうございます。 残念ながら、ユーザーさんと直接お話できる立場にないのです… SEに言っても、やれの一点張りで、 仕様の変更は、今のところありえないのです… でも、いざとなったらこんな方法もありますと 使わせていただきます。ありがとうございます。
- imogasi
- ベストアンサー率27% (4737/17068)
(1)番号が小さいものから、充当していく、というルールだけではないでしょう。それなら余り難しくない。 そのばあいでも(2)はどうするのでしょうか。 (2)指定合計値にぴったり合う組み合わせがない場合(この実証もプログラムが大変と思うが)、「組み合わせがありません」と出して終わりですか。 (3)こういう問題はVBの問題でなく、数学を応用すべき問題で、カテゴリが不適と思いますが。SEは、判らないとき、誰に聞くか、どの分野の書籍・WEBなどに当たるか、どういう聞き方をするか、のセンスも重要だと思いますが。 要求仕様書に質問の通り、もし書いたら、質問続出か、(1)で組まれて 後で問題化するとおもいますが。
補足
回答ありがとうございます。 補足ですが、 (1)は、それだけのルールで悩んでいます… (2)については「組み合わせがありません」のメッセージを出すだけで終了です。 (3)のご意見ですが、私が思っていることそのままなのです…実は私はSEではありません、プログラマなのですが、要求仕様書など何もなく、SEからは、どうやってやるのかわからないけど、絶対にやってと言われて、口述で…本当に困っているのです…よろしくお願いいたします。 カテゴリ不適だとすると、どちらに質問すればいいのかも教えていただけると助かるのですが…
- xcrOSgS2wY
- ベストアンサー率50% (1006/1985)
「どう組んだら」以前に、抽出条件が不明確(曖昧)です。 例えば、例示のデータの場合で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
- 最新日のレコードと合計の抽出
作業テーブル(作業者ID、作業日、作業時間)から、作業者ID毎に指定した作業日のレコード、および作業日を含む月の合計を抽出するSQLを考えております。 DBへのアクセス回数を減らすようにとの事で、1つのSQL文での抽出を検討しておりますが、いまいち上手くいかない状況です。 アドバイスを頂けると非常に助かります。 よろしくお願い致します。
- ベストアンサー
- PostgreSQL
- 指定した合計数と奇数&偶数の数字を抽出する。
どなたかご存じでしたら回答をお願いします。 数字選択式宝くじの「ミニロト」の組合せをフリーソフトで作成&CSVデータに出力しています。 これをエクセルに取りこむと下記のようになります。 【作成されてエクセルに取りこんだCSVデータ】 01 03 05 07 12 01 03 05 07 15 01 03 05 12 15 01 03 07 12 15 01 05 07 12 15 03 05 07 12 15 ここから、「5つの数字の横合計の合計数が○○以上~○○未満で、奇数が○個、偶数が○個のデータを抽出する。」というのをエクセルでやりたいですがどうやればよいでしょうか? できれば1回の操作で結果が出るのがよいです。 上記例でいうと、「5つの数字の横合計の合計数が30以上~40未満で、奇数が4個、偶数が1個」と指定すれば下記抽出結果が得られる。 【抽出結果】 01 03 05 12 15 01 03 07 12 15 01 05 07 12 15 CSVデータは1個~169911個まであります。 CSVデータの中には奇数が0個で偶数が5個というのもあります。(その逆ももちろんあります。) エクセルの操作およびVBAでのソースを教えて下さい。 よろしくお願いします。
- ベストアンサー
- オフィス系ソフト
- SQLの書き方~数字情報の抽出の仕方
SQLの質問です。使っているDBはMS-Accessです。 カラムの中に数字が入っているのですが、理由あって文字列型で入ってます。 これまた理由あってその状態のまま「値5以上」みたいに数字の大小で抽出を行いたいです。 こういうことはできますか?
- ベストアンサー
- その他(データベース)
- Oracle10のソートについて
お世話になります。 今までXP-ORACLE9-VB6で開発していたプログラムを VISTA-ORACLE10-VB6に移植して使用するのですが、 ORDER BYがない場合の抽出が異なっているようなんですが、 ORACLE9と同じように抽出するには、 ORDER BY をつけるしかないのでしょうか。 プログラムの本数がかなりあるので何かいい方法があれば ご教授頂きたくよろしくお願いします。
- ベストアンサー
- Oracle
- VB2005 データセットの内容をDBに更新
VB2005Expressにて開発を行っています。 ・DBから条件を指定して抽出した値をデータセットにセット ・データセット内の値を編集(追加、更新、削除) ・データセットの値をDBへ更新 という処理を行った場合、DB側では 1.データセットの値だけが更新される (抽出されてないデータは残っている) 2.データセットの値に更新されるので、データセットの値のみになる (抽出されてないデータは消えてしまう) のどちらなのでしょうか。 どなたかご存知でしたら教えてください。
- ベストアンサー
- Visual Basic
- 抽出データの欠落
プログラムもほとんど知らない素人ですが質問させていただきます。^^; oracle9iデータベースで、未抽出の情報があれば、「抽出済みフラグ」を立て、さらにその情報はテキストファイルに出力する処理を開発者に作ってもらいました。 しかし、データの10件に抽出済みフラグが付いたのに、テキストファイルへの出力は8件とか9件しか出力されない といった現象が頻発して困っています。 当初はSQL文のみのプログラム(?)で現象が出たのでVBプログラムで作り直してもらったのですが、同じ現象が出ます。 データ総件数は3万件ぐらいで、抽出される件数は20~100件ぐらいです。 こういったトラブルはoracleデータベースで一般的にあり得るのでしょうか? よろしくお願いします。
- ベストアンサー
- Oracle
- あるIDごとの最高値のレコード抽出について
下記のようなテーブルがあるとします。 それぞれの人の最高得点であるレコードを抽出したいのですが可能でしょうか。 テーブル:result no id point date -------------------- 1 A 60 ... 2 A 70 3 B 50 4 B 90 期待出力 no id point date ------------------- 2 A 70 ... 4 B 90 自分でも色々考えたつもりですが、例えば select max(point) from result group by id; とすると 70,90 という値は抽出されますが、該当レコードの全カラムを出力させたいです。 もし同じidで同じpointのレコードがあった場合は、dateの新しいほうを優先したいです。 id,point,dateがまったく同じレコードは存在しないと仮定します。 この他にもdistinct等も考えましたが、指定したカラムが重複した場合どのレコードが選択されるかは 不定のようですので使えそうにありません。 そもそもSQLだけでこのような出力が可能かどうかもわかりません…。 テーブルの設計が悪いというのもあるのでしょうか。 どなたかご助言くだされば幸いです。
- 締切済み
- PostgreSQL
- access → Oracleへのデータ移行(VB.NETで)
お知恵を貸してください。 ただ今、VB.NETでアクセスで開発されたアプリケーションを、 VB.NETに移行する開発をしているのですが、その中で、 現在のDBはアクセス、移行後のDBはオラクル10gなんですが、 何か良い移行方法は無いでしょうか? ちなみに、テーブル名、レコード名は変更しますので、そのまま移行ではありません。 私が考えているのは、アクセスのデータをエクセルにコピペし、 それを.NETで読み込んでテープルに入れて1レコードずつ オラクルに書き込んで行こうと考えております。 しかし、上記の方法でエクセルの読込方法が良く分かりません。 一旦、エクセルに取込む方法の場合の読込方法を教えてください。 また、もっと効率の良い方法をご存知でしたら教えてください。 開発環境は OS : windows XP Pro 開発ソフト : VB.NET DB : Access 2003 SP2 DB : Oracle 10g です。なにぶん、VBでの開発経験が浅いので、 猿でも分かるように(W)お教えいただけると幸いです。
- ベストアンサー
- Visual Basic
- 合計を求めるクエリーについて
1日から30日の間に誰が何のパンを何個売ったのかを調査できるようなデータベースを作ってみました。 クエリーの抽出条件はBetween「○○○」And「○○○」で日付で指定するようにしました。 (日付ですがデータ型はテキスト型です) 該当するレコードが30件あったとすると30件のレコードが抽出されますが、この期間内に誰が何のパンを何個売ったかの合計がわかるようにするにはどうすればいいのでしょうか? なんかうまく説明できなくてすみませんが教えてください。 よろしくお願いいたします。
- ベストアンサー
- その他(データベース)
- 複雑な抽出条件のSQL文
まだまだ初心者ですがよろしくお願いします。 以下の条件でDBからデータを抽出したい場合のSQLを 教えていただきたいです。 ・テーブルAがありカラムがA、Bとある。 ・Aは重複できないようになっているがBは重複可。 ・Bが重複しているレコードのAの値が欲しい。 環境はSQLServer2000+VB6.0です 情報が足りないかも知れませんがよろしくお願いいたします。
- ベストアンサー
- SQL Server
お礼
ありがとうございます。 御礼が遅くなって申し訳ありません。 教えていただいたサンプルを組み込んで、 SEに「数学で有名なNP完全問題で、えらい時間がかかる場合がある」と伝えたところ、 どうやら仕様が変更しそうです… この仕事を続けていくには、 勉強が足りなさすぎると実感しましたので、もっと勉強しようと思います。 本当にありがとうございました。 今後ともなにかありましたら、よろしくお願いいたします。