アドバイスください！和を構成する数値の選び出し

質問

ここに１３個の数値があります。

999,000
735,000
429,996
299,470
407,862
237,405
251,492
194,118
253,023
352,800
92,432
133,875
221,812

このなかの任意の数の和が、2,476,620になる数値を選びだしたいと思っています。
選択対象が多すぎてなかなかみつけることができません。とにかくいろんな組み合わせがあると思うので確率のように順番に組み合わせていったら途方にくれてしまいます。
業務で求められているのですが、このような任意の数を選び出す方法はあるのでしょうか？こんな風にすれば答えがみつかりやすい、といったようなヒントや見つけ方（答えが出ればとても嬉しいのですが）のノウハウをお持ちの方がいらっしゃればお願いいたします。
なお、組み合わせる数値の数（３個以内で和に達さなければならないとか）の制限は特にありません。

回答No.6

k_train_9999 · ベストアンサー

#1の補足
この数のうち一番大きい数から順に足していくと
　999,000＋735,000＋429,996＝2,163,996＜2,476,620
　999,000＋735,000＋429,996＋407,862＝2,571,858＞2,476,620
　なので最低でも4つ以上足さないとならないです。
逆にこの数のうち小さい順に足していくと
　92,432＋133,875＋194,118＋221,812＋237,405＋251,492＋253,023＋299,430＋352,800＋407,862＝2,206,844＜2,476,620
92,432＋133,875＋194,118＋221,812＋237,405＋251,492＋253,023＋299,430＋352,800＋407,862＋429,996＝2,636,840＞2,476,620
これより最大でも10個使う可能性があります。
　それと末尾1桁をみて和が必ず0になるわけですから、これで少しは絞り込めますがそれでも6,000通りまでは行かなくてもかなりの組合わせがあります。
　どなたかにプログラムを作ってもらった方がいいです。　今後このような和の計算が必要ならプログラムを組む意味はあると思います。

お礼

補足までありがとうございました。
やはり、計算のしくみを理解してもかなり労力を要するようですね。手計算でやっていたという事例を聞いていただけなので、実際にできるかどうかみなさんのご意見を聞いてみたかったということもあります。
多分、以前手計算でやっていたときは、他にも予測できる案件があったのかもしれないし、対象数値もこんなに多くなかったのかもしれません。
和のプログラムということで、シロウトでも組めるものなのか、別カテゴリで再度質問してみたいと思います。
どうもありがとうございました。

回答No.5

cyoki_par

袋詰め問題というものだと思います。
コンピュータでは時間をかけてしらみつぶしで解くようになると思いますが、実務ではデータを良く見て整理しながら考えるのでしょう。

私なら最初に下一桁に注目して分類すると思います。
６は一つしかないので、これを選ぶときは絞り込めそうだからです。

何も１０進数で考えなくてもよいわけで、１６進数だったらもっと絞り込めるかもしれません。

コンピュータを使うのでしたら、２で割った余り、３で割った余り、・・・などを計算して考える方法もあると思います。

お礼

ご回答ありがとうございます。
袋詰め問題ですか・・・そんな名前があるのですね。計算というより、パズルみたいなものだなあという印象（なので、よけいに面倒くさく感じてしまいました）を受けてはいたのですが。ネットで検索してみたいと思います。
２で割った余り、３で割った余りがどうのという話しは周りの誰かがちらっと言っていたような気がしますが、結局その考えでどうしたらいいかという明確な答えはそのとき得られませんでした。
私のように数学に弱い人は手計算はちょっと難しいような気がしてきています・・・

回答No.4

Noy

もう皆さんからの結論がでていますが、手計算でやるとして、少しでも楽にしようと思うなら、この手の問題は、場合の数をヒタスラ減らすことを考えれば正解に近づいていきます。

大きい順に並べると、
999,000
735,000
429,996
407,862
352,800
299,470
253,023
251,492
237,405
221,812
194,118
133,875
92,432
となります。ここで、999,000+735,000+429,996
=2,163,996 < 2,476,620
なので、３つ以下の組み合わせの和で2,476,620を超えることは不可能。よって、４つ以上の組み合わせの和を考えます。それでも、13_C_4+13_C_5+……+13_C_13通りあるので、結構ありますね…すべての和を考えていては、足し算が永遠に終わりませんので、下１ケタだけ絞込みます。
1)４つの数字の下一桁の数字の和の下一桁が０になるのは、
0+0+0+0=0
6+2+2+0=10
3+2+5+0=10
5+8+5+2=20
......
2)５つの数字の下一桁の数字の和の下一桁が０になるのは、
......
.
.
.
10)13つの数字の下一桁の数字の和の下一桁が０になるのは、0+0+6+2+0+0+3+2+5+2+8+5+2=35
よって、存在しない。

これでもハードですが、まだできると思います。
以上、素人より。

お礼

ご回答ありがとうございます。
私も、とりあえず下１ケタが０になるものを選びだして計算していたのですが、そのうち、「選び出す数値の数も不明なんじゃ、永遠に終わらないじゃないか！」と思い、すっかりあきらめモードになってしまってました。
ただ、大きなものから順に足していくと、２４７万何がしを超えるため、この数の組み合わせは４個以上である、という考え方は、数学からすっかり離れていた私をひとつおりこうにさせてくれた考え方でした。勉強していた頃は当たり前の考え方なのに、今となってはそういう基本的なことを全く忘れてしまってます。

回答No.3

ryn

今の数字の場合の解は No.2 さんが書かれているように
735000+429996+299470+407862+251492+352800=2476620
が唯一の解ですね．

これを手計算で求めるのはかなり無理があると思います．
簡単なプログラムを組んだところ1秒とかからずに
全通り計算して解を出してくれましたので，
機械作業は機械にやらせるのが一番だと思います．

お礼

ご回答ありがとうございます。
ああ、こうやって一発で解が求められたらどんなによいことか！！（でも、答えだけだしてもらう質問は禁止ですものね。）
この解を求めるプログラムはシロウトレベルでも組めるものなのでしょうか？（エクセルとかで）
いろいろ日々の仕事を効率よくしたくて、フリーソフトを探したり、こちらの回答などを参考にさせていただいているのですが、エクセルの関数式でもなかなか入力するのが難しくて・・・かといってお金を払って組んでもらうほど頻繁に使ったりしないんですよね。

回答No.2

eatern27

何か上手い方法があるのかもしれませんが、
組み合わせは高々2^13=8192通りなので(ん？#1さんと違う？？)、パソコン使って、強引に探す方法が一番楽だと思います。

13個から100個、1000個と増えるのなら、効率的に探す方法を考える必要がありますが。

735000+429996+299470+407862+251492+352800=2476620

お礼

ご回答ありがとうございます。
やっぱりプログラミングレベルですよね。
５，６個の数値ならまだしも、１３個もあって、何百万という数値規模でビンゴすることなんか果たしてできるのだろうかと半信半疑でした。
とりあえず１桁がゼロになるような数を足してみましたが、すぐに挫折しました。

回答No.1

k_train_9999

これはコンピュータのプログラミングの方で聞いたほうがいいと思います。
　数を小さい順に並べ、Ａ１，Ａ２，・・・・・，Ａ１３として
　あらゆる和のプログラムをコンピュータに詳しい人に作ってもらえばいいと思います。計算が間違ってなければ28,190通りあります。
　今回の場合はＡ１＝92,432、・・・・、Ａ１３＝９９９，０００として。
　手計算では無理があります。

お礼

ご回答ありがとうございます。やっぱりそうですよね。業務に絡むことなのであまり詳しくは書けないのですが、このような割り出しを手計算で予測をつけてやっていたので私にもやってくれ、と言われまして・・・内心「それはコンピュータじゃないとムリでしょ！」と思ったんですけど、やってたと言われてしまったら、返す言葉ないですよ、ねえ。