異なるサイズの四角形を使用して最適なタイル作成戦略を見つける

Question

私は8x8の四角形から構築された形をしています。サイズ8x8,16x16,32x32、および64x64の四角形の最小数を使用してそれらをタイルする必要があります。 4つの8×8の正方形に配置された正方形の単一の16×16の正方形に置き換えることができ、例えば：

何アルゴリズムは、これを達成するために使用することができますか？

Answer 1

これは動的プログラミングソリューションを必要とします。 (r, c)に1x1の正方形がある場合、真であるsquare[r][c]のブール配列があると仮定します（1x1,2x2,4x4、8x8の四角で処理するように単純化しましたが、 ）。一番上の行と左の列には、falsesentinel valuesの壁があります。

2d countアレイを定義します。ここで、count[r][c]は、上および左の領域の1x1四角形の数を示します。(r, c)。我々はすでに、二重にカウントされた領域を差し引いて、新しいセルに追加すること、の合計を知っている2つの領域を加算し

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] 

上記作品：私たちは、DPアルゴリズムを使用してそれらを追加することができます。 min_squares[r][c]が最小数を指す

// 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] 

我々は、次に、第二の2D min_squaresアレイを作成します。正方形領域が完全に一定時間内に1x1の正方形で覆われている場合countアレイを使用して、我々は、同様の方法を用いてテストすることができ元の1x1の正方形をカバーするのに必要な正方形。これらの値は、別の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) 

は、我々は(r, c)に配置された正方形のサイズを追跡するために使用する補助size_used[r][c]アレイを使用します。これから、再帰的にタイルを再構成することができます。

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

Optimal way for partitioning a cell based shape into a minimal amount of rectanglesを正しく見れば、これは同じ問題ですが、正方形ではなく長方形の場合です。