最小面积计算算法（仅在边缘放置瓷砖）

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难题，所以不存在简单而有效的算法。这并不意味着你可以使用没有很好的启发式方法，但是如果你有很多小的矩形，你不会找到最佳的解决方案。

为什么它是NP难的？假设所有矩形的高度为1，并且矩形的高度为2，那么寻找一个总高度为2的解决方案是有意义的（基本上，您尝试形成两条高度相同的水平线 - 长度相同的矩形）。为了找出这种解决方案是否存在，你必须形成你的小矩形的两个子集，两者的总宽度相同。这称为partition problem，它是NP完整的。即使可能存在差距并且不要求总宽度相同，但这仍然是一个NP难题。如上所述，通过将元素转换为高度为1的矩形，可以将分区问题缩小为矩形问题。

我会等待答复我发布在您的问题的意见，然后再考虑一下。