段ボール箱に、箱をなるべく隙間なく敷き詰めるには

質問

数年来ずっと疑問で、いつかは解き方を知りたいと思っている文系の者です。

決まった大きさの段ボール箱(直方体)が数種類あります(例/大・中・小)。

そして箱に入れる商品(直方体。長いのとか平べったいのとか)が数個～数十個あります。

箱に入れる商品を、できるだけ隙間なく段ボールに敷き詰めた時、それら全部が入る一番小さい段ボールが知りたいです。

つまり、複数の商品を購入したとき、荷物が小さくなるよう、できるだけ小さい段ボール箱を選びたいんです。

近似値で、ある程度あいまいでもいいんです。
(または総当たりや統計的な方法であっても、プログラムが一瞬で答えを出せる程度の計算ならOKです)

お願いします!

どなたか教えてくださると嬉しいです。

回答No.2

Tacosan

イメージ的には「三次元パッキング」という問題でしょう. いくつかの発見的手法が提案されています.

補足

ありがとうございます!

「三次元パッキング」というキーワード、検索してみたら、具体的な手法があるようで、なんか目標に近付けたような気がします。
もし書籍を見つけても読み解くのは大変そうですが、探してみたいと思います。
もし他にキーワードをご存知でしたらお教えください。

回答No.1

DIooggooID

この辺りが参考になのと思います。

http://www.geocities.jp/ikuro_kotaro/koramu/790_lm.htm

しかし、実務上は効率的な解法がないので、Amazon等で採用されているように、
箱のサイズを最小限に抑えて、梱包／発送する方が、はるかに低予算で実現できる
と想像できます。

http://blogs.itmedia.co.jp/yohei/2010/04/amazon-8578.html

参考URL：

http://www.geocities.jp/ikuro_kotaro/koramu/790_lm.htm

補足

ありがとうございます!

「リュカの問題の拡張」という部分でしょうか。
立方体と書かれている部分がありますが容器が直方体でも可能でしょうか？

読んでも私の浅学では理解できませんでしたが、この問題は「解決されている」問題でしょうか。この式を理解して組めば解けると考えてよろしいでしょうか？

それとも「実務上は効率的な解法がない」という部分で、やっぱり役に立つ式は存在しない、ということなのでしょうか。