[[20100114144216]]　『合計が一番近くなる組み合わせ』（めたぼ）　ページの最後に飛ぶ

『合計が一番近くなる組み合わせ』（めたぼ）
　いくつかの数値の中から、合計が決められた数に一番近く（またはその数値）となる組み合わせを見つけるにはどうすればいいですか?

 なかなか難しいですよ。
[[20091008131122]] 『データの振り分け』（みーこ）
　
(みやほりん)(-_∂)b

具体例を提示できませんか？

(warum)

みやほりんさんは過去の類似質問をとてもよくチェック
されてますね。
最近このサイトを見始めたのでその中の1件くらいしか
記憶にないです。
今回の質問内容を数値例を挙げて具体的に説明して欲しい
ですね。

(warum)

 一般的な最適解ってのは皆さん言うように難しい問題です。
そんなのを見っけたら世界に名が轟くかもしれません？
　
単純な数値のみの組合せであり且つ目標値に一番近くするってだけならば、
条件によっては自分がちょい前に以下の質問で
[[20091108213418]]『ランダムな数字をなるべく均等に並べ替えるには』（54-71）
一例として考えてみたコードを、その要件に適合するように改造すればいける「かも」しれません。
上記リンクにあるような感じで、出来るだけ具体的な例を提示してみてください。
条件がいい感じにいけそうで、かつ時間があったら考えてみます。
（ご近所PG）無理かもだけど

他の掲示板で同様な質問が出てます。
エクセルでの組み合わせ出力方法（計算含む）
http://oshiete1.goo.ne.jp/qa5593027.html

こちらの回答ではExcel Solverを使った解き方が示されてますが、
それが手軽で良いと思います。
数十個程度までならば最適解が得られると思います。
それより多い場合は能力オーバーになり解けないことがあります。
因みにこの種の問題はナップサック問題の特殊形で部分集合和問題と
呼ばれており、組合せ最適化問題の難問の１つで一般解法はまだ知られて
ないようですが現実に出てくる問題ならばいろいろ解法はあるようです。
それで大学の先生の間ではナップサック問題は解決済みということらしい。

(ご近所PG）さんの紹介例は最近のものですが知りませんでした。
こちらの質問の方がはるかに難しいですね。
Bin Packing問題(箱詰め)として考えれば解けますがその解法は結構面倒です。
ご近所PGさんともう1人の回答者の方はともに最適解をだしておられます。
この種の問題はいろんな業種の現場で現れる難しい問題ですが、これを研究
されている日本の大学の先生は極めて少ないですね。
だから解説してある本はほとんどないです。

(warum)

コメント返信：

[ 一覧(最新更新順) ]

[[20100114144216]] 『合計が一番近くなる組み合わせ』（めたぼ） ページの最後に飛ぶ

[[20100114144216]]　『合計が一番近くなる組み合わせ』（めたぼ）　ページの最後に飛ぶ