6

我的问题与 2D Knapsack 问题或切割库存非常相似，但有一个例外......适合容器的矩形可以调整大小和裁剪。但不允许旋转。

挑战在于尽可能少地生产作物并填满整个容器（没有任何间隙）。

有没有人遇到过可以做类似事情的算法。任何链接，伪代码非常感谢。

保持问题通用，但我想将其应用于在固定大小的页面上组织照片。

非常感谢

4

3 回答 3

5

首先从确定性最佳拟合递减算法开始：

  • 根据大小将矩形从大到小排序

  • 取出第一个矩形并将其放入容器中（如果合适）

  • 取下一个矩形并将其放在容器中剩余的最佳位置，不要裁剪（如果它适合它）。如果有多个选项，请选择留下的剩余区域最少的选项。重复此步骤，直到容器已满或已使用所有矩形。

  • 如果容器还没有装满，请以相同的顺序遍历未使用的矩形，但这次尝试裁剪。

现在，这不会是完美的。您可能会遇到类似于此图像中左侧 2 个解决方案的情况，即使不需要，您也可以裁剪“无空间”项目：

在此处输入图像描述

所以，其次，对第一个的结果抛出一个元启发式算法，例如禁忌搜索或模拟退火。如果你正在寻找一个开源库来为你做这件事，看看这个。

于 2011-02-26T11:20:53.320 回答
3

在我写这篇文章的时候，我们试图优化的确切标准还没有确定。但无论最终决定的标准是什么，以下启发式（即通常不是最佳的）方法可能是有用的：

仅考虑将少量矩形组合成单个较大矩形的少量“布局”。 然后递归地查看将这些新矩形组合成更大矩形的方法，使用相同的几个布局，直到只剩下一个矩形。

这并不能保证最佳解决方案，因为某些照片子集被限制在最终解决方案中形成子矩形。但它似乎很可能会提供质量合理的解决方案。

例如，对于 3 个矩形 A、B 和 C，考虑以下 4 种布局：

A
B
C

ABC

AB   (i.e. A appears on the left)
AC

AA   (i.e. A appears on the top)
BC

裁剪只会发生在第一轮，当我们组合 3 张照片组时。对于此步骤，应在上述 4 个布局中的每一个下考虑 3 张照片的每个子集，并为每个布局确定最佳缩放和裁剪，记住生成的矩形可以通过后续步骤放大或缩小。（最佳性标准的一个好的选择应该具有以下特性：在特定布局下，A、B 和 C 中的每一个的理想缩放和裁剪量不受结果矩形缩放多少的影响，所以这不应该是问题。）

随后的组合轮次将表现类似，但不考虑任何裁剪。对于完整的解决方案，第 2 轮将涉及尝试将第 1 轮生成的所有 3 个矩形组合在一起，其中所有 9 张照片都是不同的，但是遵循这种方法将导致指数级爆炸。为每个照片子集保留最好的少数安排就足够了。请注意，每张照片至少出现在每轮生成的矩形中的一个中，这一点很重要。

于 2011-02-25T20:13:54.953 回答
0

我不会声称这是最佳的，但这里有一些想法可能会让你尝试。

我将根据评论重新定义问题。我们得到了一个 v x t 大小的矩形 X 和 N 个不同大小的矩形。我们想用 N 个矩形完全覆盖矩形 X。我们可以根据原始尺寸调整图像的大小。我们希望最小化 N 个矩形所覆盖的面积，这些矩形也不覆盖矩形 X 的面积。

这是一个想法：

  • 如果我们能找到一个与原始尺寸成比例的包装，我们可以简单地放大或缩小它并适合矩形，我们就完成了
  • 给定一些 bin 打包算法，执行二进制搜索以找到 X 的最小缩放常数，以便我们可以打包 bin 中的所有矩形。
  • 展开并裁剪单个矩形，直到空间被填满

不知道它会怎么样，但可以尝试一下。

于 2011-02-25T18:30:55.483 回答