特定比率の直方体の中に複数の直方体を自動的に隙間なく入れる方法

質問

たとえば段ボール箱(直方体)があるとします。
段ボール箱の縦横高の長さは特定の比率の縦横比ですが、大きさは決まっていません。
その段ボール箱の中に、できるだけ隙間なく、購入した商品を梱包するには、商品をいろんな方向に回転して梱包しなければなりません。
そうして商品すべてをできるだけ小さい段ボール箱に入れて、その段ボール箱の大きさとなるものを一つだけ知りたいのです。
プログラムは、パズルゲーム「ミキソミノ」の解法プログラムなどを参考にできるかと思いましたがわかりませんでした・・。

結果的に梱包した段ボールの大きさの数値だけわかればいいのですが・・。
よろしくお願いします。
言語はcoldfusionなので、アイデアだけでも教えていただければ幸いです。

回答No.2

don_go

＞でも今回は複数商品の同時梱包時の送料を出せばいいだけなんですけどね。
＞送料計算がサイズの場合で賢く送料を出す方法はどこか(のサイト)で
＞使われているのでしょうか？
ネットショップで一般的なのは、送料定額で一定以上の金額分を
購入した場合には送料無料(店舗負担)が多いので、あまり厳密な
送料計算はしていない様に思います。
＃大型商品の場合は個別に別途送料を設定。

実際の商品発送では破損を防ぐための緩衝材を入れる事も多いので
単なる数学的な最適解というのは役に立たないと思われますが？

お礼

>＃大型商品の場合は個別に別途送料を設定。
想定していなかったです。参考になりました。
送料計算については、サイズで送料を計算できるシステムがどこにもないから作りたい、って感じです・・。
緩衝材等については、緩衝材の大きさの割合の平均(20～30％くらい？)か、大きさが大きくなるにつれて緩衝材の割合を減らして計算ということでいいかなと思います。
厳密にやれば重さが重くなったら緩衝材を増やす、という感じでしょうね。

回答No.1

seta_takahiro

中に入れる直方体について、何か制限はあるのでしょうか、
同じ大きさの直方体だけなのか、
箱と同じ縦横比のものだけだとか、
辺の長さが整数値限定だとか、
何も制限はなくて、任意の大きさの直方体だとか。

どのような問題に対しても
最適解を求めるアルゴリズムを作るのはものすごく難しそうだな、
という気がするだけで、何もアイデアはありませんが、
質問だけさせてください。

# パズルはNP完全な物が多いですが、
# この問題も何も制限なしだと、NP完全問題である
# PARTITIONが表現出来てしまうな、と思いました。

補足

実はショッピングカートで、複数梱包時の正確な送料を知るために縦横高さが知りたいだけなんですが、他にも応用できるかもと思ったもので・・。
制限は、外側の箱が立方体でも構わないくらいでしょうか。(あまり変わらないですね)
あとは、大雑把でも構わないことです。
積み方によって変わってきますしね。
大雑把でもいいので高速にしないとだめです。
総当たりで行くと時間が足りません。

形を考慮せず中にすべてをぎっしり詰められた時は、段ボール箱の大きさは、すべての直方体の体積の合計の立方根から求められますし、
単純に最大になる大きさなども出ますが・・。

あるいは中に入れる直方体について、どれだけ個々の大きさや形がばらついているかというような確率から、都合よく「このくらいになる」という、公式や統計のようなもの、はないですよねぇ・・。

でも今回は複数商品の同時梱包時の送料を出せばいいだけなんですけどね。
送料計算がサイズの場合で賢く送料を出す方法はどこか(のサイト)で使われているのでしょうか？(商品サイズのランクをSとかMとかLにして決めていくしかないでしょうか。)