Tôi có kích thước khác nhau của hình chữ nhật nhỏ (1cm x 2xm, 2cmx3cm, 4cm * 6cm, v.v ...). Số lượng hình chữ nhật loại khác nhau có thể thay đổi tùy theo từng trường hợp. Mỗi loại hình chữ nhật khác nhau có thể có số lượng đếm khác nhau.Thuật toán tính toán diện tích tối thiểu (Chỉ đặt các ô trên cạnh)
Tôi cần tạo hình chữ nhật lớn với tất cả các hình chữ nhật nhỏ này, những hình chữ nhật nhỏ này chỉ có thể được đặt trên các cạnh . không có phép quay. Hình chữ nhật bên ngoài cuối cùng lý tưởng nên được làm quen với một hình vuông. X ~ Y. Không phải tất cả các cạnh cần phải được lấp đầy. Có thể có những khoảng trống giữa các hình chữ nhật nhỏ hơn. Ví dụ:
http://i.stack.imgur.com/GqI5z.png
Tôi đang cố gắng viết mã tìm ra khu vực tối thiểu có thể được tạo thành.
Tôi có một thuật toán lặp qua tất cả các vị trí có thể để tìm ra khu vực tối thiểu có thể. Nhưng phải mất một thời gian dài vì số lượng hình chữ nhật loại khác nhau và số lượng hình chữ nhật tăng lên. tức là 2 loại hình chữ nhật, mỗi hình chữ nhật có 100 hình chữ nhật. 8 cho vòng lặp. Đó sẽ là ~ 100^8 lần lặp
Bất kỳ ý tưởng nào về thuật toán tốt hơn và nhanh hơn để tính toán khu vực tối thiểu có thể? mã là python, nhưng mọi khái niệm thuật toán đều ổn.
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
Vì vậy, kích thước của hình chữ nhật bên ngoài được đưa ra và bạn muốn giảm thiểu vùng màu trắng ở giữa? –
Điều kiện làm cho nó khó khăn là hình chữ nhật chỉ có thể được đặt trên các cạnh/cạnh. Chúng không thể được xếp chồng lên nhau –
Kích thước của hình chữ nhật ngoài không được đưa ra. Chỉ có hình chữ nhật nhỏ diemsions được đưa ra. Kích thước của hình chữ nhật bên ngoài sẽ thay đổi dưới dạng thay đổi vị trí. Nhưng tôi muốn vị trí hình chữ nhật nhỏ tối ưu trên cạnh sẽ cung cấp cho khu vực hình chữ nhật nhỏ nhất bên ngoài. –