把一些矩形拼成一个大矩形，要求留空最少
把一些矩形拼成一个大矩形，矩形可以旋转，要求拼后的矩形面积最小，也就是留的空白最少。拼后的矩形没有尺寸限制，如果有多解，最好是长宽接近。
感觉上和下料问题有些区别，因为是尺寸不受限的，不知道这样是会增加复杂度，还是降低复杂度。
如果是限制一维的长或者宽呢,就是长或宽定长，令一维可以增长。
[解决办法]
(1)用回溯法解决“这些矩形能否放在一个m*n的大矩形里”的问题。
(2)用枚举法和(1)解决“这些矩形能否放在一个面积为S的大矩形里”的问题。
(3)用二分法和(2)解决“能容下这些矩形的大矩形面积最小为多少”的问题。
好复杂啊~
[解决办法]
贪婪算法的策略很多,近似程度也不同,想到一个简单的:
1.对所有的矩形进行排序(按长度W),从大到小:A[N]
这样得到一个很粗糙的大矩形,面积为:A[1].W*(A[1].Height+...+A[N].Height)
2.用非常简单的方式来优化这个大矩形:
从最小的矩形开始(即A[N]),按循序填充到大矩形的空白位置(从A[2]开始)
举例来说:
a:W=20,H=10;b:W=10,H=9;c:W=5,H=4;d:W=4,H=4;
1.上面的矩形排好序,得到的矩形面积为:20*(10+9+4+4)=540
2.将d填充到b中(当然,如果添不下,就试试c,一直向下),由于b有10的空位,所以可以填充,填充之后的矩形面积为:20*(10+9+4)=460;
将c填充到b中,同样可以填充:这时的面积为:20*(10+9)=380;
这种算法比较粗糙,应该优化一下,LZ可以自己想想其他的
