Ustalanie optymalnej strategii układania płytek przy użyciu kwadratów o różnych rozmiarach

Question

Mam kształty zbudowane z kwadratów 8x8. Muszę je ułożyć przy użyciu najmniejszej liczby kwadratów o rozmiarach 8x8, 16x16, 32x32 i 64x64. Cztery 8x8 kwadratów ułożonych w kwadrat może być zastąpione jednym kwadracie 16x16, np .:

Co algorytm może być wykorzystane do osiągnięcia tego celu?

Answer 1

To wymaga dynamicznego rozwiązania programistycznego. Zakładam, że mamy tablicę boolowską square[r][c], która jest prawdziwa, jeśli (r, c) ma kwadrat 1x1 (Uprościliśmy rozwiązanie do pracy z kwadratami 1x1, 2x2, 4x4 i 8x8, aby ułatwić śledzenie, ale łatwo jest dostosować). Podeprzyj go ścianą falsesentinel values w górnym rzędzie i lewej kolumnie.

Określ tablicę 2d count, gdzie count[r][c] odnosi się do liczby kwadratów 1x1 w regionie powyżej i na lewo od (r, c). Możemy dodać je za pomocą algorytmu DP:

count[0..n][0..m] = 0 
for i in 1..n: 
    for j in 1..m: 
    count[i][j] = count[i-1][j] + count[i][j-1] - 
     count[i-1][j-1] + square[i][j] 

Powyższe prace poprzez dodanie dwóch regionach już wiemy sumę, odejmując podwójnie liczone obszaru i dodanie w nowej komórce. Za pomocą tablicy count, można sprawdzić, czy obszar kwadratowy jest całkowicie pokryta kwadratów 1x1 w stałym czasie stosując podobną metodę:

// p1 is the top-left coordinate, p2 the bottom-right 
function region_count(p1, p2): 
    return count[p1.r][p1.c] - count[p1.r][p2.c-1] - 
     count[p2.r-1][p1.c] + 2*count[p2.r-1][p2.c-1] 

Następnie utworzenia drugiego 2D min_squares tablicę, w której min_squares[r][c] odnosi się do minimalnej liczby kwadraty wymagane do pokrycia oryginalnych kwadratów 1x1. Te wartości mogą być wyliczona z wykorzystaniem innego DP:

min_squares = count 
for i in 1..n: 
    for j in 1..m: 
    for size in [2, 4, 8]: 
     if i >= size and j >= size and 
      region_count((i-size, j-size), (i, j)) == size*size: 
     min_squares[i][j] = min(min_squares[i][j], 
      min_squares[i-size-1][j] + 
      min_squares[i][j-size-1] - 
      min_squares[i-size-1][j-size-1] + 
      1) 

W celu odtworzenia posadzka potrzebne, aby uzyskać obliczony najmniej używamy pomocniczy size_used[r][c] tablicę które wykorzystać do śledzenie wielkości kwadratu umieszczonego w (r, c). Z tego możemy rekursywnie zrekonstruować płytki:

function reconstruct(i, j): 
    if i < 0 or j < 0: 
    return 
    place square of size size_used[i][j] at (i-size_used[i][j]+1, j-size_used[i][j]+1) 
    reconstruct(i-size_used[i][j], j) 
    reconstruct(i, j-size_used[i][j]) 

Answer 2

Być może zechcesz spojrzeć na Optimal way for partitioning a cell based shape into a minimal amount of rectangles - jeśli dobrze zrozumiałem, jest to ten sam problem, ale w przypadku prostokątów zamiast kwadratów.