找到填充容器的矩形的最大尺寸

Question

我有一個容器，具有一定的寬度和高度。我有一堆我需要適合容器的塊，但我需要計算這些塊可以適合的最大尺寸。

例如：

到：

我猜它類似於此question，但他的代碼是jQuery和適用於文本。我只是想僞代碼或某種形式的如何做到這一點的算法。

Answer 1

假設，如圖所示，所有塊具有相同的高度和方向，您可以創建一個具有塊長度的數組A。

如果目標是在給定的邊界矩形中將塊優化打包，那麼求解subset sum problem以找到最大長度最接近但沒有更大的塊集。刪除第一行的那些塊，並用剩餘的塊重複該過程。

如果目標是找到最小的（按面積）邊界矩形，那麼您應該看看這篇論文：Fast Optimizing Rectangle Packing Algorithm for Building CSS Sprites。它還涵蓋了塊的高度可能變化的情況。

如果塊可以有不同的方向，那麼問題就更難packing problem。