Hình chữ nhật tối thiểu cần thiết để bao phủ một khu vực hình chữ nhật đã cho

Question

Tôi có một khu vực hình chữ nhật có kích thước: n*m. Tôi cũng có một hình chữ nhật nhỏ hơn kích thước: x*y. Số lượng hình chữ nhật nhỏ hơn tối thiểu cần thiết để bao quát toàn bộ diện tích hình chữ nhật lớn hơn là bao nhiêu?

Không cần thiết phải gói hình chữ nhật nhỏ hơn. Chúng được phép chồng lên nhau, băng qua đường viền của hình chữ nhật lớn hơn nếu cần. Yêu cầu duy nhất là chúng tôi phải sử dụng số ít nhất là hình chữ nhật x*y.

Một điều nữa là chúng ta có thể xoay hình chữ nhật nhỏ hơn nếu cần (xoay 90 độ), để giảm thiểu số.

n, m, x và y: tất cả đều là số tự nhiên. x, y không cần phải là các thừa số của n, m.

Tôi không thể giải quyết nó trong thời gian nhất định, tôi cũng không thể tìm ra cách tiếp cận. Tôi bắt đầu bằng cách lấy các trường hợp khác nhau của n, m có thể chia hết cho x, y hay không.

cập nhật

mẫu trường hợp thử nghiệm:

• n * m = 3 * 3, x * y = 2 * 2. Kết quả phải là 4
• n * m = 5 * 6, x * y = 3 * 2. Kết quả phải là 5
• n * m = 68 * 68, x * y = 9 * 8. Kết quả nên 65

Answer 1

(UPDATE:. Xem phiên bản mới hơn dưới đây)

Tôi nghĩ (nhưng tôi không có giấy tờ chứng minh vào thời điểm này) mà tilings bất thường có thể được loại bỏ, và việc tìm kiếm các phương tiện giải pháp tối ưu tìm điểm để chuyển hướng gạch.

Bạn bắt đầu với một mạng lưới cơ bản như thế này:

và giải pháp tối ưu sẽ mất một trong hai hình thức sau đây:

Vì vậy, cho mỗi người trong các điểm, bạn tính số lượng ô yêu cầu cho cả hai tùy chọn:

---

Đây là triển khai rất cơ bản. Giá trị "ngang" và "dọc" trong kết quả là số lượng ô trong vùng không xoay (được chỉ ra bằng màu hồng trong hình ảnh).

Thuật toán có thể kiểm tra một số thứ hai lần và có thể sử dụng một số ghi nhớ để tăng tốc độ.

(Thử nghiệm đã cho thấy rằng bạn cần chạy thuật toán lần thứ hai với thông số x và y được chuyển đổi và kiểm tra cả hai loại giải pháp là cần thiết.)

function rectangleCover(n, m, x, y, rotated) { 
 
    var width = Math.ceil(n/x), height = Math.ceil(m/y); 
 
    var cover = {num: width * height, rot: !!rotated, h: width, v: height, type: 1}; 
 
    for (var i = 0; i <= width; i++) { 
 
     for (var j = 0; j <= height; j++) { 
 
      var rect = i * j; 
 

 
      var top = simpleCover(n, m - y * j, y, x); 
 
      var side = simpleCover(n - x * i, y * j, y, x); 
 
      var total = rect + side + top; 
 
      if (total < cover.num) { 
 
       cover = {num: total, rot: !!rotated, h: i, v: j, type: 1}; 
 
      } 
 
      var top = simpleCover(x * i, m - y * j, y, x); 
 
      var side = simpleCover(n - x * i, m, y, x); 
 
      var total = rect + side + top; 
 
      if (total < cover.num) { 
 
       cover = {num: total, rot: !!rotated, h: i, v: j, type: 2}; 
 
      } 
 
     } 
 
    } 
 
    if (!rotated && n != m && x != y) { 
 
     var c = rectangleCover(n, m, y, x, true); 
 
     if (c.num < cover.num) cover = c; 
 
    } 
 
    return cover; 
 

 
    function simpleCover(n, m, x, y) { 
 
     return (n > 0 && m > 0) ? Math.ceil(n/x) * Math.ceil(m/y) : 0; 
 
    } 
 
} 
 
document.write(JSON.stringify(rectangleCover(3, 3, 2, 2)) + "<br>"); 
 
document.write(JSON.stringify(rectangleCover(5, 6, 3, 2)) + "<br>"); 
 
document.write(JSON.stringify(rectangleCover(22, 18, 5, 3)) + "<br>"); 
 
document.write(JSON.stringify(rectangleCover(1000, 1000, 11, 17)));

Đây là phản ví dụ Evgeny Kluev cung cấp: (68, 68, 9, 8) trả về 68 trong khi có một giải pháp sử dụng chỉ 65 hình chữ nhật, như thể hiện trong hình ảnh này:

---

UPD ate: thuật toán được cải tiến

Ví dụ về số lượt truy cập cho biết cách tổng quát thuật toán: làm việc từ 4 góc, thử tất cả các kết hợp định hướng độc đáo và mọi vị trí của đường viền a, b, c và d giữa các vùng; nếu một hình chữ nhật còn lại phát hiện ra ở giữa, thử cả hai phương hướng để trang trải nó:

Dưới đây là một đơn giản, thực hiện unoptimised của ý tưởng này; nó có thể kiểm tra một số cấu hình nhiều lần, và mất 6,5 giây cho bài kiểm tra 11 × 17/1000 × 1000, nhưng nó tìm ra giải pháp đúng cho ví dụ ngược và các kiểm tra khác từ phiên bản trước, do đó, logic có vẻ như âm thanh.

Những là năm quay và cách đánh số trong những khu vực được sử dụng trong các mã. Nếu hình chữ nhật lớn là hình vuông, chỉ có 3 vòng quay đầu tiên được chọn; nếu hình chữ nhật nhỏ là hình vuông, chỉ có vòng xoay đầu tiên được chọn. X [i] và Y [i] là kích thước của các hình chữ nhật trong vùng i, và w [i] và h [i] là chiều rộng và chiều cao của vùng tôi thể hiện bằng số hình chữ nhật.

function rectangleCover(n, m, x, y) { 
 
    var X = [[x,x,x,y],[x,x,y,y],[x,y,x,y],[x,y,y,x],[x,y,y,y]]; 
 
    var Y = [[y,y,y,x],[y,y,x,x],[y,x,y,x],[y,x,x,y],[y,x,x,x]]; 
 
    var rotations = x == y ? 1 : n == m ? 3 : 5; 
 
    var minimum = Math.ceil((n * m)/(x * y)); 
 
    var cover = simpleCover(n, m, x, y); 
 

 
    for (var r = 0; r < rotations; r++) { 
 
     for (var w0 = 0; w0 <= Math.ceil(n/X[r][0]); w0++) { 
 
      var w1 = Math.ceil((n - w0 * X[r][0])/X[r][1]); 
 
      if (w1 < 0) w1 = 0; 
 
      for (var h0 = 0; h0 <= Math.ceil(m/Y[r][0]); h0++) { 
 
       var h3 = Math.ceil((m - h0 * Y[r][0])/Y[r][3]); 
 
       if (h3 < 0) h3 = 0; 
 
       for (var w2 = 0; w2 <= Math.ceil(n/X[r][2]); w2++) { 
 
        var w3 = Math.ceil((n - w2 * X[r][2])/X[r][3]); 
 
        if (w3 < 0) w3 = 0; 
 
        for (var h2 = 0; h2 <= Math.ceil(m/Y[r][2]); h2++) { 
 
         var h1 = Math.ceil((m - h2 * Y[r][2])/Y[r][1]); 
 
         if (h1 < 0) h1 = 0; 
 
         var total = w0 * h0 + w1 * h1 + w2 * h2 + w3 * h3; 
 
         var X4 = w3 * X[r][3] - w0 * X[r][0]; 
 
         var Y4 = h0 * Y[r][0] - h1 * Y[r][1]; 
 
         if (X4 * Y4 > 0) { 
 
          total += simpleCover(Math.abs(X4), Math.abs(Y4), x, y); 
 
         } 
 
         if (total == minimum) return minimum; 
 
         if (total < cover) cover = total; 
 
        } 
 
       } 
 
      } 
 
     } 
 
    } 
 
    return cover; 
 

 
    function simpleCover(n, m, x, y) { 
 
     return Math.min(Math.ceil(n/x) * Math.ceil(m/y), 
 
         Math.ceil(n/y) * Math.ceil(m/x)); 
 
    } 
 
} 
 

 
document.write("(3, 3, 2, 2) &rarr; " + rectangleCover(3, 3, 2, 2) + "<br>"); 
 
document.write("(5, 6, 3, 2) &rarr; " + rectangleCover(5, 6, 3, 2) + "<br>"); 
 
document.write("(22, 18, 5, 3) &rarr; " + rectangleCover(22, 18, 5, 3) + "<br>"); 
 
document.write("(68, 68, 8, 9) &rarr; " + rectangleCover(68, 68, 8, 9) + "<br>");