【Excel】エクセル 複数の数値データの中から合計すると任意の値になる組合せを抽出したい。

質問

たとえば、
　商品A 100 円
　商品B 200 円
　商品C 600 円
　　　・
　　　・
　　　・
以上のように全部で100品目以上ある商品の中からぴったり100,000円になる組み合わせを探し出したいのですが、可能ですか？

抽出される商品の数は問いません。

教えてください。

回答No.1

neKo_deux

> 100品目以上ある商品

15～16項目なら、Excelの扱える行数内で、選択(1)/非選択(0)の組み合わせ表を作って対応可能ですが…。

可能／不可能で言うと可能ですが、線形計画法とか遺伝的アルゴリズムとか、プログラムで問題解決する領域ですね。
「ナップザック問題」という名前で課題などとしてよく扱われる問題です。

取り合えず「Excel ナップザック」で情報収集すると、

ナップザック問題をExcelで解く
http://www.geocities.co.jp/SiliconValley-Oakland/8139/

のサイトに方法やVBAのプログラムが紹介されています。
簡潔ですが、実用的な内容になっていますね。

| １．手当たり次第法

は、データ数100件ですと厳しいですが、手順があまりにもシンプルに記載されていて、シンプルさが気持ちいいくらいです。

| ２．総当たり法
| ３．動的計画法

で解くのが現実的です。
総当り法はデータ数が30件程度と書かれていますが、最近のPCの性能なら100件でも対応可能かも？
データ数を10件、20件で速度を確認すると良いです。
ちなみに、マクロ実行で応答無しになった場合、Ctrl+BreakでVBAを中断します。

--
> 抽出される商品の数は問いません。

商品A 100円×1,000個で100,000円とかって事じゃ無いですよね？

参考URL：

http://www.geocities.co.jp/SiliconValley-Oakland/8139/

お礼

なるほど、何とかできました！
ＶＢＡはずぶの素人なので今のところやろうとすると人に聞くしか方法が無いんですよね。。。
マニュアルは専門用語が分からないし。。。

本当にどうもありがとうございました。
またよろしくお願いしますー。