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

  • 主题发起人 主题发起人 whaoye
  • 开始时间 开始时间
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

L
算法问题：在定长定宽的范围（矩形范围）内放置数目一定大小已知的矩形框 (100分)
回复
0
查看
131
luaijun
L
Y
如何在ComboBox中列出当前打印机所支持的纸张类型，并能选取不同的纸改变打印机的纸型？(200分)
回复
6
查看
317
Alex_HJ
A
Y
求一个 矩形最优化切割的 算法,200分(200分)
2
回复
21
查看
1K
LeeChange
L
G
有经验的人请进：请问保存图纸的方法，大约有10万张以上的图纸，请问用什么方法保存最好？图纸的大小最大3m，一般都是几百k，我用的是sql数据库！我试过用数据库保
2
回复
28
查看
171
yitanhg
Y
Z
使用QUICKREPORT 控件进行打印时，有关自定义纸张的最终解决方案(0分)
回复
11
查看
279
ldlcm
L
后退
顶部