使用不同大小的正方形找到最佳平铺策略

Question

我的形状由8x8方块构成.我需要使用最小数量的8x8,16x16,32x32和64x64的正方形来平铺它们.布置在正方形中的四个8x8正方形可以替换为单个16x16正方形,例如:

可以使用什么算法来实现这一目标？

Answer 1

这就需要动态规划解决方案。我假设我们有一个square[r][c]布尔数组，如果(r, c)有一个 1x1 正方形，则为 true（我简化了解决方案以使用 1x1、2x2、4x4 和 8x8 正方形，以使其更容易遵循，但很容易适应）。用哨兵值墙填充它false 在顶行和左列上

定义一个二维count数组，其中count[r][c]指 的上方和左侧区域中 1x1 方格的数量(r, c)。我们可以使用 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]

上面的工作原理是将我们已经知道总和的两个区域相加，减去重复计数的区域并添加新的单元格。使用该count数组，我们可以使用类似的方法测试一个正方形区域是否在恒定时间内被 1x1 正方形完全覆盖：

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

然后我们创建第二个二维min_squares数组，其中min_squares[r][c]指的是覆盖原始 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)

为了重建获得计算最小值所需的平铺，我们使用一个辅助size_used[r][c]数组来跟踪位于 处的正方形的大小(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])