algorithm - コンテナを満たす長方形の最大サイズを見つける

Question

特定の幅と高さのコンテナがあります。コンテナーに収まる必要があるブロックがたくさんありますが、これらのブロックが収まる最大サイズを計算する必要があります。

例えば：

に：

この質問に似ていると思いますが、彼のコードはjqueryであり、テキストに適用されます。これを行う方法の疑似コードまたは何らかの形式のアルゴリズムが欲しいだけです。

Answer 1

図のように、すべてのブロックの高さと方向が同じであると仮定すると、Aブロックの長さで配列を作成できます。

ブロックを特定の境界四角形に最適にパックすることが目標である場合は、サブセット合計問題を解いて、サイズを大きくせずに最大長に最も近いブロックのセットを見つけます。最初の行のブロックを削除し、残りのブロックでこのプロセスを繰り返します。

目標が最小の (面積による) 境界矩形を見つけることである場合は、このペーパーを参照する必要があります: Fast Optimizing Rectangle Packing Algorithm for Building CSS Sprites。また、ブロックの高さが異なる場合もカバーします。

ブロックの向きが異なる可能性がある場合、問題ははるかに困難なパッキングの問題です。