algorithm - 在另一个矩形内均匀分布矩形所需的算法

Question

我正在寻找一种算法，可以帮助在更大的矩形内分布不同大小的矩形，同时最大限度地减少重叠。

我已经研究过装箱算法，但它们似乎最大限度地减少了矩形之间的空间量（在我的情况下，所有被打包的物品都是正方形）。

我想我想最大化所有正方形和外部矩形边界之间的距离。

这是我正在尝试做的一个例子：

Answer 1

如果您使用类似于此处描述的算法将它们尽可能紧密地打包，然后均匀扩展以匹配目标封闭矩形怎么办？

例如，假设您可以将上面的 3 个矩形打包成一个3x2盒子，而您的外盒是7x5. 然后从盒子的中心到每个矩形的中心取向量，x 分量乘以(7/3)，y 分量乘以(5/2)，得到新的中心。

Answer 2

这似乎是背包问题的概括。

动态规划将在接近多项式时间内解决它。