異なるサイズの長方形をできるだけ小さい長方形にかなり最適な方法で詰め込むには、どのようなアルゴリズムが使えるか？
私は、可能な限り小さなスペースに詰め込む必要のある長方形のオブジェクトの束を持っています（このスペースの寸法は2の累乗である必要があります）。
しかし、この場合、私はその空間がどの程度の大きさであるべきかを計算するアルゴリズムが必要です。
例えば、次のような長方形があるとします。
- 128*32
- 128*64
- 64*32
- 64*32
128*128のスペースに詰め込むことができる
_________________ |128*32 | |________________| |128*64 | | | | | |________________| |64*32 |64*32 | |_______|________|ただし、160*32と64*64がある場合は256*128のスペースが必要です。
________________________________ |128*32 |64*64 |64*32 | |________________| |_______| |128*64 | |64*32 | | |_______|_______||____| | |160*32 | | |____|____|
長方形の束をパックして、コンテナに必要なサイズ（2の累乗で、各寸法の与えられた最大サイズ以内）を決定することができるアルゴリズムにはどのようなものがあるでしょうか？
269
3
梱包の問題]1を見てください。あなたのは '2D bin packing.' に該当すると思いますが、その解決策や他のパッキング問題から多くを学ぶことができるはずです。
こちらもご覧ください。長方形の画像データを正方形のテクスチャに詰め込む。
これはNP困難問題(http://en.wikipedia.org/wiki/NP-hard)であることは間違いないので、最適解を得るためには、可能な限りの組み合わせを試すバックトラック・アルゴリズムを実装しなければなりません。
ただ、2次元の長方形を限られた2次元空間に詰め込む必要があるため、早い段階で多くの可能性を切り捨てることができ、それほど悪い結果にはならないかもしれませんね。
一般的な解決策はノントリビアル（数学で言うところの完全な○○○○不可能）である。 一般的には遺伝的アルゴリズムを使って可能な組み合わせを試しますが、最初に一番大きい形を入れ、次に大きい形を入れる場所を変えてみるなどすれば、それなりにうまくいくはずです。