[解決済み】異なるサイズの長方形を、かなり最適な方法で可能な限り小さな長方形に詰め込むには、どのようなアルゴリズムが使用できるだろうか？

質問

Iveは、私は可能な限り最小のスペース（この空間の寸法は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の累乗で、各寸法の与えられた最大サイズ以内）を決定できるアルゴリズムがありますか？

どのように解決するのですか？

クイック＆ダーティなファーストパスソリューションは、何はなくとも比較対象として、常に素晴らしいものから始めることができます。

大から小への貪欲な配置

残っている最大の長方形をパックエリアに入れます。どこにも入らない場合は、パック領域をなるべく広げないように配置します。これを一番小さい長方形で終わるまで繰り返します。

完璧ではありませんが、簡単で良いベースラインです。この方法でも、元の例を完璧にパックすることができますし、2番目の例でも同等の答えが得られます。