最小面積計算算法（僅在邊緣放置瓷磚）

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的矩形，可以將分區問題縮小爲矩形問題。

我會等待答覆我發佈在您的問題的意見，然後再考慮一下。