瀏覽單個文章
sandstorm
*停權中*
 

加入日期: Mar 2010
文章: 541
我最喜歡暴力法了!

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)都有包到。
...
...

我保證這個演算法一定找得到最佳解,但要花多久時間就...
舊 2012-10-09, 08:26 PM #13
回應時引用此文章
sandstorm離線中