我需要一种算法来计算长度为 X 的正方形的最大可能数量，这些正方形可以在网格可用性限制的情况下适合 M x N 矩形。
例如 当X = 2且M = N = 8时(不能使用灰色网格)
我们最多可以在这个矩形内容纳 10 个正方形。 像下面的解决方案一样，可能有多个解决方案空间用于最大计数。
- 哪种算法可以帮我做到这一点？
- 是否有不同于多项式的 DP 解？
- 这种特定算法有名称吗？
[注意:我认为贪婪在这里不起作用，如果我错了请纠正我]
请描述您所知道的最佳方法。
最佳答案
根据要求，对于X = 2，您可以使用带位掩码的 DP。您可以按列或行进行操作，因此通常选择较小的那一个。我们假设最小数量是列数。
您可以执行 DP，其中状态是当前行、当前列和一个位掩码，告诉哪些列在当前行中被阻止。
让我用你的例子来解释一下。
原始状态:row = 0, column = 0, bitmask = 00000000 .
检查您是否可以在当前位置放置一个方 block ，在这种情况下可以。所以结果将是max(1 + placing the square, not placing the square) 。如果不能，那么您只有一个选择:不放置它。
如果你不放置方 block ，你的下一个状态是 row = 0, column = 1, bitmask = 00000000 。请注意，现在第一位正在讲述下一行，而不是当前行，因为我们已经通过了该列。
如果你放置了方 block ，你的下一个状态是 row = 0, column = 2 (因为正方形，我们跳了两个)和 bitmask = 11000000 。该位掩码告诉您第二行的前两个位置已经被阻止。
现在让我们考虑一个不同的状态，row = 2, column = 4, bitmask = 11110000 。这对应于您的解决方案位于第三行第五列时的情况。位掩码告诉我们下一行的前四个单元已经被阻塞，并且当前行的后四个单元是空闲的。
再次检查是否可以放置正方形。单元格未被阻挡，但网格包含标记的单元格，所以您不能。下一个状态是 row = 2, column = 5, bitmask = 11110000 。在这个例子中，我希望您注意到位掩码不会告诉您有关被原始网格阻挡的单元格的任何信息，而只是被您之前的方 block 所阻挡。
所以每个状态都会在常数时间内检查，因此算法的复杂度就是状态的数量，即 O(NM * 2^(min(N, M))) ，抱歉，我在评论中忘记了一个额外的因素。
关于最大化带约束的矩形拟合所需的算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/33707611/