商品を混在させて箱に詰めていった場合の、梱包数

エクセルにて箱の大きさは問わずに、商品それぞれの重量単位で箱に詰めていった場合、箱が何箱必要か計算したいのですが。２週間たっても今だ解決しなくて困っています。どうかよろしくお願いします。

条件1：　ひと箱あたり最大20Kgまで入ります。（箱の大きさは問わない）
条件2：　一つの商品を切り分けて別の箱に移すことができない
条件3：　商品を効率よく混在させて箱に詰めていった場合の、梱包箱数を求めたい

No.2 ベストアンサー 回答者： cozycube1 回答日時： 2012/10/06 11:31

　詳しい方法は調べるか、数学系のカテで再質問して頂きたいのですが、一例としては、おおむね以下の手順が考えられます。

商品は全て20kg以下でいいですね？

　商品を、いきなり箱に詰めて行かず、以下のシミュレーションを行います。

０）箱の数を適当に決める（たとえば、総重量÷20）。箱には1から順に番号付けしておく。
１）最も重い物から、重い物順に商品を列挙する。
２）重い物順序に箱を変えながら入れて行く。
３）空箱が無くなったら、1番目の箱に戻って続ける。
４）１）～３）を繰り返し、商品が無くなるまで続ける。
５）20kgを超えた箱から、軽い物順序に商品を取り出し、全てを20kg以下にする。
６）５）で取り除いた商品だけで、０）～５）を行う。
７）さらに入りきらない商品が出れば、６）を繰り返す。

　必ずしも真の最適解は得られません。せいぜい局所的な最適解に留まります。

　エクセルで行うのに、手順としてシンプルで間違いが出にくい方法を考えてみました。もし試されるなら、VBAを含めて、エクセルへの実装はお任せします。

　もっと最適化したい場合は、私の手には負えないように思います。すみません。

この回答への補足

皆さん素晴らしいです！スペシャリスト集団ですね！展開の仕方が見えてきました。今シックハックしながら式を入れ始めたところです。しばらくかかりそうですが何とか完成させたいと思います。有難うございます。

補足日時：2012/10/07 20:57

No.5 回答者： f272 回答日時： 2012/10/06 14:52

私ならこんなアルゴリズムを使う。

0）箱の数を((総重量-1)/20)+1にする。箱には1から順に番号付けしておく。
1）最も重い物から順に、商品を入れる順番を決める。
2）すべての箱の空き容量を20kgにセットする。
3）空き容量が最も大きな箱（空き容量が同じなら番号の最も若い箱）を選ぶ。
4) 選んだ箱の空き容量が次に入れる物と同じか大きければ，物を入れて，空き容量をその分だけ減らす。
選んだ箱の空き容量が次に入れる物より小さければ，箱の数を1つ増やして最初からやり直す。
5) 3)-4)を繰り返して入れる物がなくなればおしまい。

この回答への補足

箱の数を((総重量-1)/20)+1ですね！なるほど！アルゴリズムはちょっとやってみたのですがうまく設定できませんでした。もう少し考えてみたいと思います。有難うございます。

補足日時：2012/10/07 21:16

No.4 回答者： ki073 回答日時： 2012/10/06 14:30

基本的にはNo2, No.3の回答で良いとは思いますが、

総重量/20kgで余りがある場合には１個増やすで最低箱数がでます。適当に分配した場合に最低箱数を越えてしまった場合には、
整数計画ソルバー（線形計画ソルバー）を使えば何箱必要かと詰め方が求められます。
おおざっぱには、
それぞれの商品を１単位ずつ分けた表を作る
箱の重量を20kg以下に制限（制限条件）
箱数が最小になる方法を見つける
の条件でやります。

以前回答したものをリンクしておきます。
こちらはかなり複雑でしたので、glpkを使っていますが、この場合にはEXCELのソルバーで十分できると思います。
http://oshiete1.nifty.com/qa7734670.html

この回答への補足

なるほど！最低箱数を越えてしまった時点でソルバーを使うわけですね。まだそこまでの数式がくめてないので完成したらソルバーにも挑戦したいと思います。ありがとうございます。

補足日時：2012/10/07 21:09

No.3 回答者： MarcoRossiItaly 回答日時： 2012/10/06 12:24

No.2さんのお考えを支持します。

箱数の想定を変化させて、一つひとつの場合を試していくといことですね。ベストアンサーは辞退します。

若干の補足をするなら、３）については、次のような方法に差し替えることも考えられるかもしれません。

３）空箱が無くなったら、1番目の箱に戻って続ける。
↓
３）空箱が無くなったら、最後の箱から1番目の箱の方向に、逆順で続ける。

こうすると、若い数字の箱ばかりに重たい商品が集まることを避けて、各箱の1商品当たりの重量が平均化されそうな気がします。箱の中に残った小さな隙間にもできるだけ商品を詰めたいという事情を考えても、都合が良さそうです。

いずれにしてもご質問の内容は、Excelより先に、数学の問題。その上、どこのセルにどんなデータがあるかという情報もないということで、質問者さんが取り組んでいる問題にピッタリの回答が寄せられることは、このままでは難しいかもしれません。

この回答への補足

cozycube1さんの展開方法の精度が更にアップしますね！有難うございます。

補足日時：2012/10/07 21:03

No.1 回答者： aokii 回答日時： 2012/10/06 11:04

ひと箱あたり最大20kgでしたら、F2セルに、

=ROUNDUP(E2/20,0)

F2セルを選んで、セルの右下隅をダブルクリック。

この回答への補足

ROUNDUP使わせていただきます。有難うございます。

補足日時：2012/10/07 21:20