作者idoiwant (idont)
站内Prob_Solve
标题[问题] 类似背包问题
时间Wed Oct 22 13:59:43 2008
感觉很像背包问题...但靠一维的背包又解不出来
已知:一个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
1F：推 FRAXIS:如果面积是固定 长宽又必须要是整数 那能产生的长方形个数 10/22 17:25
2F：→ FRAXIS:就有限了 先把所有可能的长方形算出来 然後再用类似背包 10/22 17:26
3F：→ FRAXIS:问题的方法解.. 10/22 17:26
4F：→ idoiwant:呃....不太懂A... 10/22 18:34
5F：推 Eventis:Multi-Project Wafer? 10/24 02:54
6F：推 TroyLee:Floorplanning? 10/25 02:50