将9×3矩形分成8个相同大小的正方形

Question

您将您最喜爱的布朗尼配方甩出并倒入新的9x3寸烤盘中。布朗尼烤。牙签出来干净。现在切割。

方形是布朗尼最美味的形状。你有八个人来服务。你怎样才能将你的新烤制作切成八块正方形？

Answer 1

所以这实质上是一个bin装箱问题（众所周知的是NP -hard！）的变化。

一种解决方案是使用2个3x3正方形，1 2x2平方和5个1x1正方形，如下：

的解决方案是很明显的非唯一的，因为不同的方块的位置可以是置换周围。

由于NP硬度，我想这将是一个有效的算法很难提出一个普通NxM矩形k正方形块。事实上，必须有整个系列的参数值才能解决问题（例如，如果您开始使用矩形，则不可能将其分成小于6的正方形）。