回転できる長方形の数が与えられた場合、最小面積の包囲矩形を見つけてください

Question

したがって、私は入力としていくつかの矩形をとり、それらを最小面積の矩形にパックしようとするアルゴリズムを実装しようとしています。長方形はすべて90度回転できます。

これはビンのパッキングの問題と似ていますが、ローテーションの原因となる良いアルゴリズムを見つけることができません。私は長さhereでこれについて議論している論文を見つけました。記事自体を理解しているうちに、もっと簡単なものを見つけたいと思っていました。

提案がありますか？

-edit-

私は以前に問題を誤解したと思います。我々は、それぞれが90度回転できるようにいくつかの矩形が与えられています。囲む長方形の面積を最小限に抑えながら、2つの矩形が重なり合わないように、指定されたすべての矩形に適合する矩形を見つける必要があります。

ここで私が直面している問題は、囲み矩形が与えられていて、指定された矩形がその種類のものかどうかを確認するのではなく、最小値を見つけるよう求められているということです。

Answer 1

が、私はこのアルゴリズムを使用して良い結果を持っていた：

http://www.intechopen.com/articles/show/title/a_greedy_algorithm_with_forward-looking_strategy

編集：

私はあなたを与えるだろう供給リンクに記載されたアルゴリズム「はい」または「いいえ」指定された矩形のセットが特定の囲み矩形にパックできるかどうかについての答え。外接する四角形を見つけるには、アルゴリズムを繰り返し実行します。基本的には、囲み矩形の下限と上限を計算し、バイナリ検索を実行してその範囲内の最小解を求めます。私は囲み矩形が1次元で固定サイズである（すなわち、幅が一定で、最小長さを探している、またはその逆である）と仮定しています。囲み矩形の幅と長さの両方を変えることができれば、それはより困難になり、これはうまくいかないかもしれません。

次のようになり、下限と上限を計算する簡単な（しかしナイーブ）アプローチ：

下界 - 最良のケースは、すべての矩形を隙間無く完全にパックすることができるということです。したがって、すべての入力矩形の面積を合計し、その領域に必要な外接矩形の長さを計算します。

上限 - 各矩形は別の「行」にパックする必要があるため、入力矩形ごとにmin(width, height)を計算して合計します（つまり、入力矩形が最小幅または入力の他の次元が囲む矩形の幅を超えないように、各入力の高さ）を計算します。

少しでも頑張ったら、下限と上限を大幅に改善して検索スペースを減らすことができますが、これにより出発点が得られます。