三维装箱算法问题请教

有160个弹簧,20个箱子,每个箱子可以装8个弹簧,每个箱子放两排。要将这160个弹簧放到箱子里。要求: 每个箱子第一排1—4号i弹簧高度差不超过1mm。第二排5—8高度差不超过1mm,1-8之间的高度差不超过2mm。怎么装法最合理?160个弹簧,如果有超出这个条件的,需要返修后,再放入,怎么能做到最少的返修呢?

2个回答

先排序在装吧,假设每个弹簧长度为一个随机数,将1到160排序,然后八个一组挨个装箱。

桶排序,先求最大值最小值,时间复杂度n;得到mix max (max-mix)/8得到8个桶的范围,(如果每个桶范围超过2怎么处理,在这里,由于肯定可以装箱完成,那就不会出现,桶的间隔太大的问题)
假设mix =2mm max=15mm 那第一个桶就是2-4,第一排2-3,第二排3-4,,最后一个桶13-15,13-14,14-15,可以推测出所有桶的范围,
如果出现断层,mix 2 max =20,(还是注意一点,前提条件是一定能装箱完成.那么断层也可以相同的处理,就不在赘述),时间复杂度为2n,

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问