[問題] 類似背包問題

[idoiwant (idont)]

感覺很像背包問題...但靠一維的背包又解不出來

已知:一個m*n(m,n都為整數)的長方形,給定k個小長方形,

     面積為r1,r2,...,rk,(r1,r2...全都小於m*n)

     r1,r2,...,rk皆為整數,此k個長方形長寬可變,

     但也要為整數,ex:if r1=20,此長方形就可為2*10的長方形或4*5的長方形或....

     現在把k個小長方形放入m*n的長方形(但不一定放的下)

問題:求max sum(放入的面積) <---- 看的懂嗎...就是盡量填滿m*n這個長方形的意思...

有這個演算法嗎!?

我找不到.....

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 220.136.180.86
推 FRAXIS:如果面積是固定 長寬又必須要是整數 那能產生的長方形個數
→ FRAXIS:就有限了  先把所有可能的長方形算出來 然後再用類似背包
→ FRAXIS:問題的方法解..
→ idoiwant:呃....不太懂A...
推 Eventis:Multi-Project Wafer?
推 TroyLee:Floorplanning?