求在宽为w的纸上排列n个随机矩形的最节约纸张算法(200分)

W

whaoye

Unregistered / Unconfirmed
GUEST, unregistred user!
假定矩形的长和宽中必定有一个小于等于w
矩形可旋转。
最节约纸张即排好后，纸张在竖直方向上的长度最小。

提前感谢！
 
我也考虑很长时间，听很多说人这要用到自定义，递归函数。。。。。。。。。
 
感觉题目叙述的不是很清楚啊，如果只要求竖直方向最小，不要求横向的长度，
那么纸张需要满足的最小高度就是n个矩形中高度最大的那个，其他的全部横向排列
或着多个矩形垒起来排放，但要保证多个矩形垒起来的高度要小于纸张的最小高度
剩下不满足条件的矩形再依次横向排列！
 
我用递规做了的，后来发觉不好做，好像不是的规的模式。
 
hehe,递规又不是不可以.只是搜索空间太大.
说说看,最多有多少小矩形?
 
第一感觉，只能搜
 
1。图纸的宽限制为w(小矩形的长和宽中必有一个小于等于w)，
摆放好所有的小矩形后不能有矩形在图纸外.
2。假定现在规定矩形的数量为100个左右。
请给为大侠指点一下，大概的算法描述就可以了。
 
AI:
人家要100个,搜起来可有点吃力了,呵呵.
 
如果搜索都吃力，递归岂不是更吃力，呵呵
 
递归也是深度优先搜索的一种实现方式.
 
大家谈谈自己的看法！
 
我的第一印象也是--------搜.
但这么大的数据量(所有矩形的排列*(横放或竖放)*左上角位置的各种可能性),估计得好好斟酌数据结构
和约束函数.如果真的要用搜索,一定得找一个启发性相当高的估价函数.
btw:i have a book, the book have the problem and the solution.
 
LeeChange: can you mail the example to me ? thx!!!
whaoye@21cn.com
我看了一下贪婪法，回朔法，装箱算法，好象还是不好做。
我做了一个小的模型，但是始终不能得到最优解。
 
老大,我没有电子档,你不会叫我把整篇文章...
是中学时用的书,找找看吧.
 
实在是太感谢你了，
只要一个大致的思路就可以，好吧？
谢谢了！！！！
 
93NOI的试题你做过吗?最后一题跟你的问题极为类似.
 
93NOI是什么意思？
 
93年的似乎我还没看过题目，把题目贴出来瞧瞧
 
刚才我去瞧过题目了，看起来似乎有点像，但是又有很大的不同。因为如果你采用NOI93-6的算法，就不能保证每个矩形用且只被使用一次。虽然没找到解题报告，但估计对原方法很难进行改造。
 
假如各个矩形大小相同，那么只有两个自由度搜索；就比较好办。
否则极难获得得中大规模的最优解。
 
您必须登录或注册才可回复。

Similar threads

S
[转]ClientDataSet加上TDataSetProvider的数据保存问题
回复
0
查看
3K
SUNSTONE的Delphi笔记
S
S
[转]ClientDataSet加上TDataSetProvider的数据保存问题
回复
0
查看
2K
SUNSTONE的Delphi笔记
S
I
如何求出包围任意折线多边形的最小矩形
回复
0
查看
628
import
I
I
一个关于矩阵的算法
回复
0
查看
708
import
I
I
常用算法（2）分而治之算法
回复
0
查看
669
import
I
顶部