最小面积计算算法(仅在边缘放置切片)

Question

我有不同尺寸的小矩形(1cm x 2xm,2cmx3cm,4cm*6cm等).不同类型矩形的数量可根据情况而变化.每种类型的不同矩形可以具有不同数量的计数.

我需要创建一个包含所有这些小矩形的大矩形,这些小矩形只能放在边缘上.没有轮换.理想情况下,最终的外部矩形应该是方形的.X~Y.并非所有边缘都需要填满.较小的矩形之间可能存在间隙.图片示例:http:
//i.stack.imgur.com/GqI5z.png

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

我有一个算法循环所有可能的位置,以找出可能的最小区域.但是,随着不同类型矩形的数量和矩形数量的增加,这需要很长的运行时间.即2种类型的矩形,每种都有100 +矩形.8循环.那将是~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 难题，因此不存在简单有效的算法。这并不意味着没有可以使用的好的启发式方法，但是如果您有许多小矩形，您将无法快速找到最佳解决方案。

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

我会等待我在您问题的评论中发布的问题的答案，然后再考虑一下。