ここから本文です

ある数列(例:2 3 5 7 11 13 17 19 23 29)を幾つか加算して、ある数Nになるか。 ...

アバター

ID非公開さん

2016/3/3121:24:48

ある数列(例:2 3 5 7 11 13 17 19 23 29)を幾つか加算して、ある数Nになるか。
ならない場合、Nに最も近い値(絶対値)を求めたいです。

例えば、
Nが55のとき、3+5+7+17+23=55なのでNになる。
Nが130のとき、2+3+5+7+11+13+17+19+23+29=129なのでNにならず差=1
といった感じです。

上記例では数列の例として素数を使いましたが、実際は適当な数字で最大20個程度です。
数列の中に、Nが存在する可能性もあります。

全通りを計算するには、莫大な計算量になると思います。良い解法はお教えいただけないでしょうか。
なお、JavaScriptかVBAかVB.NETで計算したいと思っているのですが、多言語でも良いので、実装のヒントをお教えください。

よろしくお願い致します。

閲覧数:
298
回答数:
8
お礼:
500枚

違反報告

ベストアンサーに選ばれた回答

30246kikuさん

2016/4/108:13:16

以下でどうでしょう

Excelで、数ある数値の中から何個か選び出し
http://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q1215400047...

この回答は投票によってベストアンサーに選ばれました!

ベストアンサー以外の回答

1〜5件/7件中

並び替え:回答日時の
新しい順
|古い順

has********さん

2016/4/109:51:17

「Nがあるかどうか」、または「Nに最も近い値は何か」だけが分かればいいのであれば、動的計画法というのを使えば、1秒もかからずにわかるかも。

昨年 ? 知恵袋に以下のような質問があった。
「下記の28個の数字を合計して1,000,000になる組み合わせの数を教えてください。(5+5+5…のように重複選択も可)
2、3、5、8、13、21、34、55、89、144、233、377、610、987、1,597、2,584、4,181、6,765、 10,946、17,711、28,657、46,368、75,025、121,393、196,418、317,811、514,229、 832,040」

その回答者の説明通りにプログラムを作ったら、あっという間に
35149126091976381690058120656043297588150432104344399通り
という答えが出た。

重複選択は許さないというようにもできると思う。

返信を取り消しますが
よろしいですか?

  • 取り消す
  • キャンセル

prs********さん

2016/4/100:24:12

こんな感じはいかがですか・・・・・・・・・・・・

Private Sub CommandButton1_Click()
Dim s, n, i, h As Long
s = TextBox1.Text
n = TextBox2.Text
If s > 100 Then
MsgBox "数を減らして下さい。"
End If
For i = 1 To s
h = h + Cells(i, 1)
Next
Cells(17, 3) = n - h
End Sub

こんな感じはいかがですか・・・・・・・・・・・・

Private Sub...

返信を取り消しますが
よろしいですか?

  • 取り消す
  • キャンセル

プロフィール画像

カテゴリマスター

2016/3/3123:56:48

2分探索で探せば良いのでは、

・その数列の要素数をW個とすると、足し算の組み合わせ方は、[1から((2のw乗)-1)]までの2進数で表わせて、
その数列を昇順にソートしておけば、
(足し算の組み合わせ方を示す2進数の大小関係)と、
(足し算の組み合わせ方に従って、その数列の部分集合を合計した数値の大小関係)とは、同じだから、2分探索できるでしょう?

そのコードは、Ruby言語では約40行。
http ://ideone. com/pVEwzH


p search([2, 3, 5, 7, 11, 13, 17, 19, 23, 29],55)
[3, 23, 29]
55

p search([2, 3, 5, 7, 11, 13, 17, 19, 23, 29],130)
129

p search([2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97],512)

[2, 19, 71, 73, 79, 83, 89, 97]
513


という25個の数列の中から足し算の組み合わせを出すのに、0.05秒だった。

返信を取り消しますが
よろしいですか?

  • 取り消す
  • キャンセル

境良夫さん

2016/3/3122:59:28

最初にすることは、与えられた数列をソートして最大値と最小値を求めることでしょう。
これで、範囲が絞られます。
A)1個だけで該当する数値が有り得ない場合。
B)全てを足してもNに届かないもの。
C)1個でNを超過するもの。
かなり範囲が絞られるでしょう。
B、Cのときは、直ちに答えが得られます。
D)全てを足した値とNの差から何をすべきか考えます。
E)最小値とNの差から何をすべきかを考えます。
上記のようにして逐次範囲を絞りましょう。
言語は、何を使っても大同小異でしょう。

kae********さん

2016/3/3122:51:26

総当たりを計算するのだが、まともに全部計算しないで、各段階で計算するものだけをふるいにかける。必要な計算量はぐっと減る。時間制限が無いのだからわりと楽に出来る。

この質問につけられたタグ

みんなで作る知恵袋 悩みや疑問、なんでも気軽にきいちゃおう!

Q&Aをキーワードで検索:

Yahoo! JAPANは、回答に記載された内容の信ぴょう性、正確性を保証しておりません。
お客様自身の責任と判断で、ご利用ください。
本文はここまでです このページの先頭へ

「追加する」ボタンを押してください。

閉じる

※知恵コレクションに追加された質問は選択されたID/ニックネームのMy知恵袋で確認できます。

不適切な投稿でないことを報告しました。

閉じる