Minimalne prostokąty wymagane do pokrycia danego prostokątnego obszaru

Question

Mam prostokątny obszar wymiaru: n*m. Mam również mniejszy prostokąt o wymiarach: x*y. Jaka będzie minimalna liczba mniejszych prostokątów wymaganych do pokrycia całego obszaru większego prostokąta?

Nie ma potrzeby, aby paczka mniejsze prostokąty. Mogą one nakładać się na siebie, w razie potrzeby przekraczać granice większego prostokąta. Jedynym wymaganiem jest to, że musimy użyć najmniejszej liczby prostokątów o rozmiarze x*y.

Inną rzeczą jest to, że możemy obrócić mniejsze prostokąty w razie potrzeby (90 stopni obrotu), aby zminimalizować liczbę.

n, m, x i y: wszystkie są liczbami naturalnymi. x, y nie muszą być czynnikami n, m.

Nie mogłem go rozwiązać w wyznaczonym czasie, nie mogłem też ustalić podejścia. Zapoczątkowałem różne przypadki, w których n, m jest podzielna przez x, y lub nie.

zmiana

przykładowych przypadkach testy:

• n * m = 3 * 3 x * y = 2 * 2. Wynik powinien być 4
• n * m = 5 * 6, x * y = 3 * 2. Wynik powinien być 5
• n * m = 68 * 68, x * y = 9 * 8. Wynik powinien być 65

Answer 1

(UPDATE:. Zobacz nowszą wersję poniżej)

myślę (ale nie mam żadnego dowodu w tej chwili), że nieregularne tilings można wyrzucić, a znalezienie optymalnych sposobów rozwiązania znalezienie punktu, w którym należy zmienić kierunek płytek.

Zaczynasz z podstawowym siatki tak:

i optymalnym rozwiązaniem będzie miała jeden z tych dwóch form:

więc dla każdego z nich punkty, obliczasz liczbę wymaganych płytek dla obu opcji:

---

Jest to bardzo proste wdrożenie. Wartości "poziome" i "pionowe" w wynikach to liczba płytek w nieobrotowej strefie (oznaczona na zdjęciu kolorem różowym).

Algorytm prawdopodobnie sprawdza niektóre rzeczy dwa razy i może użyć jakiejś pamięci do przyspieszenia.

(Testy wykazały, że trzeba uruchomić algorytm po raz drugi przy włączonym parametrze x i y, a sprawdzenie obu typów rozwiązań jest rzeczywiście konieczne.)

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)));

to przeciwciśnienie przykład Evgeny Kluev pod warunkiem: (68, 68, 9, 8), która zwraca 68, gdy jest rozwiązanie za pomocą zaledwie 65 prostokątów, jak pokazano na ten obraz:

---

Upd ate: poprawiony algorytm

Kontrprzykład pokazuje drogę do uogólnienia algorytmu: pracuj z 4 zakrętów, wypróbuj wszystkie unikalne kombinacje orientacji i każdą pozycję granic a, b, cid między regiony; jeśli prostokąt zostaje odkryte w środku, spróbuj obie orientacje na pokrycie go:

Poniżej znajduje się prosty, nieoptymalizowane realizacja tego pomysłu; prawdopodobnie kilka razy sprawdza niektóre konfiguracje i trwa to 6,5 sekundy dla testu 1000, ale znajduje prawidłowe rozwiązanie dla kontrprzykładu i innych testów z poprzedniej wersji, więc logika wydaje się być dobra.

to pięć obrotów i numeracja regionów używanych w kodzie. Jeśli duży prostokąt jest kwadratem, sprawdzane są tylko pierwsze 3 obroty; jeśli małe prostokąty są kwadratami, sprawdzany jest tylko pierwszy obrót. X [i] i Y [i] są wielkością prostokątów w obszarze i, a w [i] i h [i] są szerokością i wysokością regionu i wyrażoną w liczbie prostokątów.

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>");