http://www.hatena.ne.jp/1114739498#
人力検索はてな - 【Microsoft Excel】エクセルで作成した価格表を利用して、10万円ぴったりの買い物をする場合の組み合わせを全て考えたいのです。価格表には1,000商品程掲載されております..
Excelで全ての商品の組み合わせ2^1000≒1.07×10^301を計算するのは無理です。
「計算時間の爆発」が起きます。ニューロ・コンピュータなど「学習能力をもつコンピュータを使うしかありません」
エクセルには『ソルバー』という機能があります。『ゴールシーク』の複雑版といった感じでしょうか?
通常のエクセルにはこの機能はメニューを探してものっていません。アドイン機能の登録作業をして初めて使用できます。
上記2番目のURLを参考にアドイン登録をされて使用してみてください。
単純に全ての組合せで調べようとすると、1000種類の商品は多すぎて計算できませんね。何らかの戦略が必要になります。
1000商品の価格帯を教えていただければ新たな展開が得られるかと思います。
例えば、1000商品のうちのかなりのものがが5万円を超えているのであれば、組合せの数を激減させることが可能(5万円を越えるもの同士の組合せを最初から排除)、等。
http://www.is.titech.ac.jp/~watanabe/myhome/NP.html
NP Problems and its complexity
今のコンピュータではどんなアルゴリズムを使ったとしても、答えがたまたますぐに出る場合もあるし一つめの答えが見つからないまま事実上永遠に時が過ぎていく場合もあるということです。印刷して自分で考えるのが敢えて言えば最善だと思います。
http://www.neurosci.aist.go.jp/~kurita/thesis/thesis/node34.html
$B%@%$%J%_%C%/%W%m%0%i%_%s%0(B
全ての組合せを求めるならダイナミックプログラミングで解くことができます。これだと、連休中には無理だと思いますので簡単な方法です。
単純に2個で10万になる組合せを求めるなら、Vlookup関数を用いることで単価が
10万円から自身の単価を引いた単価の商品が
あるかを検索すれば可能です。3個でならマクロを組んであげて2000×2000の組み合わせに対して同様の事をすれば可能ですね。
Yahoo! JAPAN
商品が1000点程度あるということですが、価格でソートして同じ価格のものはまとめてしまうことができませんか?
それだけでも組み合わせの数は激減すると思います。
また、それぞれの価格によっては組み合わせが限られます。
5番目の回答者の方の考え方と同じですが、10万円を超える組み合わせを排除するとか…
例えば、最高の値段のものから選択していって、次は残額の中での最高額のもの、さらに残額から…というのを1番目の組み合わせとして、
次は上記の組み合わせの一部を別のものに置き換えて見つけていけば、
という方法で考える組み合わせは減らせそうです。
(例)
6万、5万、4万、3万、2万、1万の商品が1点ずつあるとすると
1番目の組み合わせを考えるときは
6万円を選び、残り4万なので4万円を選ぶ
2番目は
6万円を選び、残りの4万を別の選び方をして3万と1万を選ぶ
3番目は、
最初に6万の組み合わせはないので5万を選び、残りの5万を4万と1万を選ぶ
と続けると
組み合わせは
{6,4}{6,3,1}{5,4,1}{5,3,2}{4,3,2,1}
となります。2^6-1=63通りも考えなくていいはずです。
こういう方法を応用できないでしょうか?
では全てではなくとも、いくつかでもかんがえられないですかね・・・・・。