作者奶油銓

你這個問題，約10年前我有寫過一個程式處理這種問題，當時是用f77 寫的不過當時我是用圓去包，但你現在是正方形。分享一下我的想法 (我的作法不能保證一定是最少)，但你上面的例子我一定是3個就框住了。

我的想法如下:

(1) 先把圖形切成非常細的小方格 (越細就會找的越準)

(2) 有被小長方形包住的地方就定為1，沒包到的就定為0

(3) 找尋合適的中心位置，把你要框的130x130正方形放上去，計算範圍內的1的數目，累加數字越大的那個位置就蓋上去。

這個合適的中心位置，可以
(i) 自己寫程式判斷，哪邊長方形比較密集，就從那邊開始放正方形
(ii) 無腦的就scan每個格點。(以這個例子來說最多僅需要scan 140625個位置)

(4) 蓋上去後把被蓋住的數值寫成0，然後重複(3) 直到全部都變成0。

我自己原來是用 (3)-(i)， 一開始想說從質心附近開始找，但遇到資料極端分散的情形，就失敗。...

作者sandstorm

500*500的2D空間，用130*130的框框，如果是整數座標，那就會有(500-130+1)*(500-130+1)=137641個框框(w0, w1,..., w137640)。

然後每個框框都檢查會框住哪幾些個矩形(r0, r1,...rN)，記錄起來。

那我們就有了類似下面的資料：
w0(r1, r4, r15,...)
w1(r0, r3, r4,...)
...
...
w137640(r13, r19,...)

我們希望用最少的框框就包到所有的矩形，
所以我們先只取一個框框，這樣有137641種狀況，檢查哪個滿足(r0, r1,...rN)都有包到。
若取一個找不到，就取二個框框，這樣有C(137641, 2)種狀況，檢查哪個組合滿足(r0, r1,...rN)都有包到。
若取二個找不到，就取三個框框，這樣有C(137641, 3)種狀況，檢查哪個組合滿足(r0, r1,...rN)都有包到。
...
...

我保證這個演算法一定找得到最佳解，但要花多久時間就...