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