左に書いてある数字から（その数字は一回しか使えません）選び、足した値が 220,103にできるだけ近くする数式はありますか？

1,890　左に書いてある数字から（ただしその数字は一回しか使えません）選び、足した値が　220,103にできるだけ近くする数式はありますか？
2,100
2,000
3,000
3,203
1,597
5,642
2,834
5,228
4,336
5,953
500
3,358
5,000
2,268
2,944
1,130
4,000
2,706
1,643
1,000
2,947
500
3,835
1,955
3,540
2,866
2,843
3,705
2,421
500
3,000
300
6,143
3,876
2,000
3,425
1,000
4,220
3,260
4,323
3,837
3,518
2,000
2,284
2,563
4,274
2,000
1,000
5,105
1,000
4,200
1,000
2,000
2,091
4,770
4,085
3,265
4,160
3,636
4,109
4,417
4,526
3,706
3,500
1,000
500
5,141
10,000
6,016
3,000
2,000
4,707
4,330
2,000
3,946
3,993
680
501
4,268
6,201
5,000
3,200
4,020
4,916
3,472
2,000
5,000
4,627
1,000
2,278
4,234
1,483
4,198
3,000
5,000
1,000
4,131
2,000
5,617
4,043
8,820
4,331
4,327
4,258
978
3,559
2,000
1,000
1,000
3,829
2,000
5,000
4,628
2,234
2,310
4,118

No.5 回答者： Wendy02 回答日時： 2009/08/18 10:57

こんにちは。

たぶん、ご質問のデータ自体を解答してほしいというだけなら、すでに、解答は出ていますから、それはそれで良いと思いますが、回答者ご自身で、問題を解く方法を提示してあげられるかどうかだと思います。

部分集合和問題(Subset-sum problem) に関して、一通り他の回答者の方の回答を見させていただきました。特に、#4様の回答には目が行きましたが、お示しになっているリンク先は、Excelのものではありませんし、私には、その出ているスクリプトコードをVBAには移植できません。

一般的には、プログラミングコードでは、最低100万回程度の計算はしますから、VB系のアルゴリズムさえ分かれば可能だと思います。Google 検索（英語)で、Excel 範囲内で今回の質問に回答に結びつきそうなものは、ほとんど見受けられませんでしたね。

ただ、Excelの経験者なら誰でも思いつく、ソルバー(Solver)の利用です。試してみる価値はあるのではないでしょうか。

昨日、小一時間*試してみましたが、近似値（数10前後)までは出ますが、4万回の分岐まででは、#4様の正答にまでには達しえませんでした。4～5万回がソルバーの限界かもしれません。

*設定時間（デフォルト100秒)を越えたら、ダイアログで聞いてきますので、[継続]すると、後は、再び実行しますが、そのままですと終わりませんので、ESCでとめます。

**シナリオは、データ数が、32個を越えていますので保存できません。

***ソルバーにはどうやらバグが存在するようで、数式の中に、IFなどのブーリアン型(TRUE/FALSE)があると、実行しないようです。また、動的範囲の条件を[バイナリ(0,1)]と設定しても、それ以外の数字も出てきてしまいますので、手動で直さなくてはなりません。


ソルバーの設定は、図で示しておきます。
他は、デフォルトのままでもよいはずです。

この回答へのお礼

早速、解答ありがとうございました。しかも複数回いただきまして。
ありがとうございます。
また、お礼のお返事が遅くなってしまい申し訳ありませんでした。
今回の答えはいただいておりますので、また別の数値98個＆もとめる総和数で実行しています。
今回初めてソルバーを使った、とういうレベルです・・・。

お礼日時：2009/08/25 12:41

No.4 回答者： warumx 回答日時： 2009/08/17 11:17

他の回答者が指摘されてますように、ナップサッック問題の１つで

部分集合和問題と言います。
例えば解説とコード例は参考URLのサイトにあります。
一般的な解法は知られていない難問です。
ExcelならばVBAを使うのが良いでしょうね。
基本的に反復計算なのでワークシートの数式で計算するのは
難しいと思いますが、循環参照を利用するとなんとかできる
かもしれません。

参考までに、提示された数値例の最適解の例を載せておきます。
解１：重複したデータを許す場合
　　　5000等のいくつかのデータは複数回現れている。
解２：すべて最大でも1回しか使用しない場合

どちらの解も和は220103です。
　　　　解1　　解2
10000　　1　　　1
8820　　 1　　　1
6201　　 1　　　1
6143　　 1　　　1
6016　　 1　　　1
5953　　 1　　　1
5642　　 1　　　1
5617　　 1　　　1
5228　　 1　　　1
5141　　 1　　　1
5105　　 1　　　1
5000　　 5　　　1
4916　　 1　　　1
4770　　 1　　　1
4707　　 1　　　1
4628　　 1　　　1
4627　　 1　　　1
4526　　 1　　　1
4417　　 1　　　1
4336　　 1　　　1
4331　　 1　　　1
4330　　 1　　　1
4327　　 1　　　1
4323　　 1　　　1
4274　　 1　　　1
4268　　 1　　　1
4258　　 1　　　1
4234　　 1　　　1
4220　　 1　　　1
4200　　 1　　　1
4198　　 1　　　1
4160　　 1　　　1
4131　　 1　　　1
4118　　 1　　　1
4109　　 1　　　1
4085　　 1　　　1
4043　　 1　　　1
4020　　 1　　　1
4000　　 1　　　1
3993　　 1　　　1
3946　　 0　　　1
3876　　 0　　　1
3837　　 0　　　1
3835　　 0　　　1
3829　　 0　　　1
3706　　 0　　　0
3705　　 0　　　0
3636　　 0　　　0
3559　　 0　　　0
3540　　 0　　　0
3518　　 0　　　0
3500　　 0　　　0
3472　　 0　　　0
3425　　 0　　　0
3358　　 0　　　0
3265　　 0　　　1
3260　　 0　　　0
3203　　 0　　　0
3200　　 0　　　0
3000　　 0　　　0
2947　　 0　　　0
2944　　 0　　　0
2866　　 0　　　0
2843　　 0　　　0
2834　　 0　　　0
2706　　 0　　　0
2563　　 0　　　0
2421　　 0　　　0
2310　　 0　　　0
2284　　 0　　　0
2278　　 0　　　0
2268　　 0　　　0
2234　　 0　　　0
2100　　 0　　　1
2091　　 1　　　0
2000　　 0　　　0
1955　　 0　　　0
1643　　 0　　　0
1597　　 1　　　0
1483　　 0　　　0
1130　　 0　　　0
1000　　 1　　　0
978　　　0　　　0
680　　　0　　　0
501　　　0　　　0
500　　　0　　　0
300　　　0　　　0

参考URL：http://www.geocities.com/siliconvalley/garage/33 …

この回答へのお礼

早速の解答ありがとうございました。
また、お礼のお返事が遅くなってしまい申し訳ありませんでした。
こちらの希望は
解１：重複したデータを許す場合
　　　5000等のいくつかのデータは複数回現れているデータは
　　　その回数分は使える。
でした。
参考URLは私にはどのように使えばよいのかわかりませんでした。
解１の答えを今回はつかわさせていただきました。

お礼日時：2009/08/25 11:54

No.3 回答者： imogasi 回答日時： 2009/08/16 22:19

これは原データがエクセルにあること（他にエクセルにはエクセル関数があること、VBAもあることを考えたかどうか）からエクセルのカテに質問したかもしれないが、（時どきこのコーナーには不適のこういう質問がでるが）、数理の（数学の）詳しい方が良く見る、カテゴリに質問出すべきでしょう。

エクセルのシートを使えば、即エクセルの問題じゃない。
ーー
普通の組み合わせを考え、プログラムでしらみつぶしに実行する方法では行き詰まるので、特別のアイデアが（もしあれば）必要です。
世の中には、取りえる場合の数が膨大で正攻法では行き詰まる問題が
在ります。将棋など対戦ゲームなども層です。この質問はナップサック問題、動的計画法などの問題意識が近い。
Googleで「ナップサック問題」「巡回セールスマンの問題」「組合せ最適化問題」で照会してみたら。

この回答へのお礼

早速の回答ありがとうございました。
また、お礼のお返事が遅くなってしまい申し訳ありませんでした。
エクセルで数値を入力、管理していましたのでこちらのカテゴリーに質問
してしまいました。
imogasiさんご提案どおりGoogleで検索してみたところ、なかなか厄介な質問であることに気がつきました。
もう少し検索して調べてみてから質問するようにいたします。
ただ、今回はもう少し質問してみたいところがありますので、こちらの場所をお借りします。

お礼日時：2009/08/25 11:48

No.2 回答者： _Kyle 回答日時： 2009/08/16 21:23

>その数字は一回しか使えません

とありますが、質問文の数字には、例えば5,000が５個あります。
この場合、5,000は5回までなら使ってよいということでしょうか？

VBAが選択肢に入るなら、やってやれないこともありませんが、
いずれにせよ、【数式では無理】ですし、VBAでやるにしても、
すべての組合せを書き出すとなると結構な時間がかかります。

「元データに複数ある数字でも、同じ数字は複数回使わない」
という条件で考えても、220,103キッカリになる組合せは
少なくとも数万通り以上あるようです。

ちなみに「同じ数字の重複を許さない」場合、
220,103キッカリになる組合せのうち、
使用する数字の個数の最小値は47個で、6,437通りあります。

例えば、
　3540,3559,3636,3706,3829,3835,3837,3876,3946,3993,4000,4020,
　4043,4085,4109,4118,4131,4198,4200,4220,4234,4258,4268,4274,
　4323,4327,4330,4331,4336,4417,4526,4627,4628,4707,4770,5000,
　5105,5141,5228,5617,5642,5953,6016,6143,6201,8820,10000
など。

また、同様の条件で、使用する数字の個数の最大値は70個、
このケースだけで少なくとも1万6千通り以上あります。
(1万6千というのはExcel2007の列数の制約です)

例えば、
　300,500,501,680,978,1000,1130,1597,1643,1890,1955,2000,
　2091,2100,2234,2268,2278,2284,2310,2421,2563,2706,2834,
　2843,2866,2944,2947,3000,3200,3203,3260,3265,3358,3425,
　3472,3500,3518,3540,3559,3636,3705,3706,3829,3835,3837,
　3876,3946,3993,4000,4020,4043,4085,4109,4118,4131,4160,
　4198,4200,4220,4234,4258,4268,4274,4323,4327,4331,4417,
　4526,4628,4707
など。

以上ご参考まで。

No.1 回答者： neKo_deux 回答日時： 2009/08/16 20:59

> できるだけ近くする数式はありますか？

一般的には解析的には解けない問題です。
「ナップザック問題」のキーワードで情報収集すると良いかも。

線形計画法とか、遺伝的アルゴリズムとかで、最適解を探索します。


質問の問題については、何らかの最適解が存在するのかも知れませんが。

--
A Genetic Knapsack Problem Solver
http://www.geocities.com/SoHo/Exhibit/8033/apple …

のサイトでGAを使用、1000世代くらい見てみると、

1890 0 2000 3000 3203 0 0 2834 5228 4336 0 0 0 5000 0 0 0 4000 0 1643 0 2947 500 3835 1955 0 2866 2843 0 0 0 0 300 6143 3876 2000 0 0 4220 0 0 3837 0 2000 2284 2563 4274 2000 0 5105 1000 4200 0 2000 2091 0 0 3265 4160 3636 0 0 0 0 3500 1000 0 5141 0 0 3000 0 4707 4330 0 3946 3993 680 0 4268 6201 5000 3200 0 4916 3472 0 5000 0 0 2278 4234 0 4198 0 0 0 4131 2000 0 4043 0 4331 4327 4258 978 0 0 1000 0 3829 0 0 4628 0 2310 4118

計220051とか。

0は該当する数字を使用しない事を表す模様。

この回答へのお礼

早速の解答ありがとうございました。
また、お礼のお返事が遅くなってしまい申し訳ありませんでした。
答えが出るのに時間がかかりますが、数値を入れるだけで簡単に回答、近似値が得られるのはとてもうれしいです。
ありがとうございました。

お礼日時：2009/08/25 11:47