寻找能够放置在网格中最大物品数量的算法

Question

寻找能够放置在网格中最大物品数量的算法

algorithm

3

在二维空间中有一个N*M点的网格。可以将物品放置在点(x,y)上，但是点(x+2,y-2)、(x-2,y-2)、(x-2,y+2)或(x+2,y+2)不能有其他物品。此外，格子中还有几个点被卡住了，即这些点无法放置物品。

那么如何找到可以放置在网格中的最大物品数量？

- Shashwat Kumar

不，这不是作业。只是一次练习。 - Shashwat Kumar

如果(12,8)和(8,8)是空闲的，但(8,12)和(12,12)已被占用，您能否将一个项目放在(10,10)处？ - Rusty Rob

不考虑n和m超过1000的情况。 - Shashwat Kumar

为避免混淆，我已经修改了问题。 - Shashwat Kumar

3个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- riri · Answer 1

如果没有这些阻塞点，最佳的打包方式是放在列上。

(a + 0), (a + 3), (a + 6), ..., (a + 3*n)

无论在这些列的哪个位置存在一个块，都不能进行改进。如果一个块在 (x, y) 的某一列上，那么你可以在点 (x+2, y-2) 和 (x-2, y-2) 上放置它。因此，请遍历所有的列，并尝试将它们放置在最少数量的块上。（注意，之前是说最大化。我昨晚只睡了3个小时）

检查这个过程需要 n*m 步骤。

- IVlad · Answer 2

考虑简单的一维问题：给定一个长度为n的带有阻塞单元的数组，有多少种方法可以用1填充它，使得如果在x处有1，则在x-2和x+2处没有1。

注意这是一个冗余条件：如果我们在x处有一个1，则x-2处没有1就足够了（如果在x+2处有1，那么它将打破这个简化条件）。

令dp[i，j]表示以点填充1到i的方式数量，使得最后一个元素是j。

我们有：

dp[i, 0] = dp[i - 1, 0] + dp[i - 1, 1] <- no 1 at i
dp[i, 1] = 2 * dp[i - 2, 0] <- we MUST have 0 at i - 2, but i - 1 can have whatever
=> if i is blocked dp[i, _] = dp[i - 1, _]

例子：

n = 3
brute force solutions:
000
010
100
001
110
011
=> 6
dp[0, 0] = 1 dp[0, 1] = 0
dp[1, 0] = 1 dp[1, 1] = 1
dp[2, 0] = 2 dp[2, 1] = 2
dp[3, 0] = 4 dp[3, 1] = 2
=> dp[3, 0] + dp[3, 1] = 6

同样的方法也可以用于你的问题。只需注意条件可以简化为“如果(x-2,y-2)和(x+2,y-2)上没有点，则可以在(x,y)处放置一个点”。然后只需迭代并在O(lines*columns)的时间复杂度内填充您的dp矩阵即可。

- Adam · Answer 3

我认为将网格视为一个环面是很形象的，即边缘会“环绕”（上下->左右），这样你就可以忽略边缘情况。当N和M很大时，这是一个很好的近似。

在环面上，每个点必然会阻挡另外两个点的存在，但你可以重叠排除区域，即一个点的(x+2, y-2)也可以是另一个点的(x+2, y-2)。因此，你可以实现的最大填充率是1/2。这可以通过交替的列条纹来实现：2个完整的列，2个空列，2个完整的列等。

我会留下角落情况（M不是4的倍数）。

在非环面的网格上，你有两个考虑因素。首先，你可以直接从网格边缘开始填满整个列。其次，你可以完全填充底部两行（“底部”是y最小的位置）。因此，你可以实现略高于1/2的填充率，但是随着尺寸趋近于无穷大，你仍然得到1/2。