排版

aimisiyou

有23个矩形零件，尺寸分别如下
length     wide
400       230
400       160
340       130
246       100
350       100
170       110
220       120
420       280
330       220
290       170
230       200
210       170
260       150
180       160
200       180
245       160
210       200
220       140
250       170
300       300
350       320
320       280
165       150
现求一母板矩形，母板矩形既能裁出所有矩形零件（矩形零件互不重叠，矩形零件只能水平或垂直放置，可旋转90度）且母板矩形面积最小。

dlpg070

为帮助大家研究,我画了几张图
竖排
横排
元件相连的最稀疏排列
下面竖排的结果和图形

竖排列:总高度=4200
竖排列:最大宽度=420
竖排列:元件面积=1764000 母版与元件面积比=1.46908
图形文件名:排版_竖排_1.46908-20201006.png

dlpg070

难,好像不特别难
像游戏
继续提供图形,供参考:

竖排:总高度=4200 最大宽度=420总宽度/总高度=0.1
竖排:最优宽度=高度=1328
竖排:元件面积=1764000 母版与元件面积比=1.46908
竖排: 母版边框:
Line[{{0,0},{420,0},{420,4200},{0,4200},{0,0}}]
图形文件名:竖排_1.46908-20201006.png(前图形有瑕疵)
----------------------
横排列:总宽度=6306 最大高度=320 总宽度/总高度=19.7063
横排列:最优宽度=高度=1420
横排列:元件面积=2017920 母版与元件面积比=1.68055
横排列: 母版边框:
Line[{{0,0},{6306,0},{6306,320},{0,320},{0,0}}]
图形文件名:横排_1.68055-20201006.png
------------------------------
小结:
竖排: 420*4200  总宽度/总高度=0.1      k=1.46908
横排: 6303*320  总宽度/总高度=19.7063  k=1.68055
总宽度/总高度接近1时 母版最小
竖排忧郁横排,可在竖排基础上移动元件,使母版宽高尽可能接近相等
希望得到理论指引

aimisiyou

dlpg070 发表于 2020-10-10 15:29
难,好像不特别难
像游戏
继续提供图形,供参考:

可以排多行多列，只要面积利用率够大且矩形间无重叠就可以。

aimisiyou

dlpg070 发表于 2020-10-10 15:29
难,好像不特别难
像游戏
继续提供图形,供参考:

外框面积为980*1250=1225000，利用率98.0204%。

aimisiyou

按照O-tree表示法随机生成多个排版，再进行改进优化（如遗传算法），得到利用率较高的排版图形。

dlpg070

aimisiyou 发表于 2020-10-14 12:57
按照O-tree表示法随机生成多个排版，再进行改进优化（如遗传算法），得到利用率较高的排版图形。

哇!果然功力深厚
我对原来23个零件的数据稍作修改,生成2个问题
1 去掉21#,只有22个零件 ,如何排版
2 修改3# 340x130 => 380x180,仍23个零件,如何排版
有点得寸进尺,您自己做高兴地选择,我乐见你淋漓尽致的完美表现