將9×3矩形分成8個相同大小的正方形

Question

您將您最喜愛的布朗尼配方甩出並倒入新的9x3寸烤盤中。布朗尼烤。牙籤出來乾淨。現在切割。

方形是布朗尼最美味的形狀。你有八個人來服務。你怎樣才能將你的新烤製作切成八塊正方形？

Answer 1

所以這實質上是一個bin裝箱問題（衆所周知的是NP -hard！）的變化。

一種解決方案是使用2個3x3正方形，1 2x2平方和5個1x1正方形，如下：

的解決方案是很明顯的非唯一的，因爲不同的方塊的位置可以是置換周圍。

由於NP硬度，我想這將是一個有效的算法很難提出一個普通NxM矩形k正方形塊。事實上，必須有整個系列的參數值才能解決問題（例如，如果您開始使用矩形，則不可能將其分成小於6的正方形）。