一个复杂的木板切割的算数题,我问了很多人,看有没有人能解.

AntGhazi 2008-12-28 02:33:41
题目:
本题作用为木板切割,有大板若干,需小板若干,目标是在最节约的情况下将小板从大板中切割出来,每块板有长,宽,纹理三种属
性。纹理有三种:长方向纹理记为1,宽方向纹理记为2,无纹理方向为3 ,1与2属于3

已知有不同尺寸的大板材B,共有N种,表示为 Bn{B1,B2,~,Bn},每种大板材的宽为X{X1,X2,~,Xn},高为{Y1,Y2,~,Yn},每种大
板材的纹理方向为A{A1,A2 ,~An},共表示为:B{(X1,Y1,X1) , (X2,Y2,X2) ,~ , (An,An,An)}

又已知需要不同尺寸的小板n种,表示为b{b1,b2,b3,~,bn},每种小板的宽为x{x1,x2,~,xn},高为y{y1,y2,~,yn},每种小板的纹理方
向为a{a1,a2,~,an},每一种小板的数量分别为c{c1,c2,c3,~,cn},共表示为b{(x1,y1,a1,c1), (x2,y2,a2,c2), ~ ,
(xn,yn,an,cn)};

求:从N种B板中切割出n种数量分别为c,纹理为a的 b 板.
1. 分别需要多少块大板C{C1,C2,~,Cn},才能最节约B板.
2. 分别如何切割,才能用料最少,余料最少,求切割方程式,求余料方程式.
3. 如果每刀切割时,必须切断,求切割方程式.
...全文
484 9 打赏 收藏 转发到动态 举报
写回复
用AI写文章
9 条回复
切换为时间正序
请发表友善的回复…
发表回复
lovedogdog 2009-04-25
  • 打赏
  • 举报
回复
我现在也在做一个切割板材的,功能都可以实现,但速度不怎么样,算法也一般,谈不上最优
  • 打赏
  • 举报
回复
这是个NP完全问题,lz可以去搜索“二维装箱”,有很多关于这方面的资料,当然都只能得到一些近似解。
关于切割和余料的方程式恐怕很难直接给出。

如果每次走刀都必须走到底,那这个问题会稍微简单一些。
起码对于单独一块大木板来说,(如果数据量不大)可以动态规划得到怎样切割对这块木板来说可利用面积最大。
每次贪心下来,最后能得到一个方案,当然这个方案在整体上并不能保证是最优的。
navi_dx 2008-12-29
  • 打赏
  • 举报
回复
关注,学习,以前也想解决这个问题,没搞定
vectorfx 2008-12-29
  • 打赏
  • 举报
回复
试试
AntGhazi 2008-12-29
  • 打赏
  • 举报
回复
多谢dlyme,我去查查
  • 打赏
  • 举报
回复
类似的题目网上倒是不少.
northwolves 2008-12-28
  • 打赏
  • 举报
回复
推荐 Lingo.
suilj 2008-12-28
  • 打赏
  • 举报
回复
你搜一下 排布
FancyMouse 2008-12-28
  • 打赏
  • 举报
回复
有样例么

33,009

社区成员

发帖
与我相关
我的任务
社区描述
数据结构与算法相关内容讨论专区
社区管理员
  • 数据结构与算法社区
加入社区
  • 近7日
  • 近30日
  • 至今
社区公告
暂无公告

试试用AI创作助手写篇文章吧