algorithm - 最小面积计算算法(仅在边缘放置瓷砖)

Question

我有不同尺寸的小矩形(1cm x 2xm、2cmx3cm、4cm*6cm 等)。不同类型矩形的数量可能因情况而异。每种类型的不同矩形可能具有不同数量的计数。

我需要用所有这些小矩形创建一个大矩形，这些小矩形只能放置在边缘。 无轮换。理想情况下，最终的外部矩形应该类似于正方形。 X~Y。并不是所有的边都需要被填满。较小的矩形之间可以有间隙。图片示例:
http://i.stack.imgur.com/GqI5z.png

我正在尝试编写一个代码，找出可以形成的最小可能区域。

我有一个算法可以遍历所有可能的布局，找出可能的最小区域。但是随着不同类型矩形的数量和矩形数量的增加，这需要很长时间。即 2 种矩形，每种都有 100 多个矩形。 8个for循环。这将是 ~100^8 次迭代

关于计算最小可能面积的更好更快算法的任何想法？代码在 python 中，但任何算法概念都可以。

    for rectange_1_top_count in (range(0,all_rectangles[1]["count"]+1)):
      for rectange_1_bottom_count in range(0,all_rectangles[1]["count"]-rectange_1_top_count+1):
        for rectange_1_left_count in (range(0,all_rectangles[1]["count"]-rectange_1_top_count-rectange_1_bottom_count+1)):
          for rectange_1_right_count in ([all_rectangles[1]["count"]-rectange_1_top_count-rectange_1_bottom_count-rectange_1_left_count]):
            for rectange_2_top_count in (range(0,all_rectangles[2]["count"]+1)):
              for rectange_2_bottom_count in (range(0,all_rectangles[2]["count"]-rectange_2_top_count+1)):
                for rectange_2_left_count in (range(0,all_rectangles[2]["count"]-rectange_2_bottom_count-rectange_2_top_count+1)):
                  for rectange_2_right_count in [(all_rectangles[2]["count"]-rectange_2_bottom_count-rectange_2_left_count-rectange_2_top_count)]:
                      area=calculate_minimum_area()
                      if area< minimum_area:
                        minimum_area=area

Answer 1

这看起来像是一个 NP-hard 问题，因此不存在简单高效的算法。这并不意味着您没有可以使用的好的启发式方法，但是如果您有很多小矩形，您将无法快速找到最佳解决方案。

为什么它是 NP 难的？让我们假设你所有的矩形都有高度 1 而你有一个高度为 2 的矩形，那么寻找总高度为 2 的解决方案是有意义的(基本上，你尝试形成两条具有相同长度的高度为 1 的矩形水平线).要弄清楚是否存在这样的解决方案，您必须形成小矩形的两个子集，两者加起来的总宽度相同。这称为 partition problem并且它是 NP 完全的。即使可能存在间隙并且不需要总宽度相同，这仍然是一个 NP-hard 问题。如上所述，您可以通过将要分区的元素转换为高度为 1 的矩形来将分区问题简化为矩形问题。

我会等到我在你的问题的评论中发布的问题的答案，然后再考虑。