n個の矩形で占有されている最小面積を求めるアルゴリズム

Question

私は長方形の数を持っています。小さな矩形をすべてカバーすることができる最小の長方形を見つけたいと思います。ローテーションは許可されません。

私は自分の答えを見つけたいと思います。私はjavaでそれをコードしようとしています。 私は自分のアイテムのすべての順列をチェックして、最小のエリアを見つけなければならないことは分かっています。そして、最初に簡単にするために、可能な最小限の領域を見つけようとしました。次に、各セルが占有されているかどうかを確認するためにブール値を持つ2次元配列を使用しました。しかし、私はそれを理解することができませんでした（コード）。

私のアイテムが私の限られたエリアに置くことができるかどうかチェックする方法？たとえば、最初のアイテムをx[0][0]からx[10][1]に配置し、この範囲内のすべてのセルをtrueにしますが、次のアイテムの他のセルをチェックするようにプログラムに指示する方法はわかりません。私のアルゴリズムが実装する必要のあるステップについて教えてください。

Answer 1

問題は2Dビンのパッキングのカテゴリに該当します。それはNP困難な問題であるため、それを解決するための効率的な多項式時間アルゴリズムは存在しません。 （P == NPでない限り）。

あなたはかなり最適な解決策を提供するブルートフォースアルゴリズムまたは巧妙なヒューリスティックを試すことができます。
1. How is 2D bin packing achieved programmatically?（異なるヒューリスティックを可視化するための）

---

あなたのブルートを
2. http://www.codeproject.com/Articles/210979/Fast-optimizing-rectangle-packing-algorithm-for-bu（実装の詳細については）
3. http://www.binpacking.4fan.cz/（様々なアルゴリズムを議論するために）：

は、以下のリンクを参照してください。強制アルゴリズムは非常に非効率的である。長方形を置くことができる順列は非常に巨大であり、見つけにくい。上記のアルゴリズムを試すことをお勧めします。このアルゴリズムは、すべての順列を見つけるよりも簡単に実装できます。