algorithm - 将网格划分为矩形

Question

我有一个 0 和 # 的网格。我想将所有 0 重新组合成矩形。最少需要多少个矩形？

例子 ：

#00#00
#00#00
0000#0
000000

#11#34
#11#34
2222#4
222254

在这个例子中，我们使用了 5 个矩形。还有其他解决方案，但 5 个矩形是覆盖所有 0 的最小值。

Answer 1

该问题是NP-Hard问题，被称为经典装箱问题的 2D 变体，称为2D-装箱问题。
因此，该问题没有已知的多项式解。

这已被广泛研究，这里有一篇示例文章，介绍了近似解决此问题的方法。

您还可以尝试 Genthic 算法或其他启发式方法来解决问题。