论坛徽章:: 0

电梯直达

1楼 [收藏(0)] [报告]

发表于 2006-04-27 17:17 |只看该作者 |倒序浏览

一个箱子长、宽、高：40.5×49×7 CM，一个房间的尺寸，长、宽、高：1190×210×210，
问：怎样放这些箱子才能在这个房间内放最多个箱子？(箱子不能放倒！)根据和思路？

文库|博客

ArXoR

稍有积蓄

论坛徽章:: 0

2楼 [报告]

发表于 2006-04-27 21:35 |只看该作者

3d packing问题是np-hard的吧...

实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？

converse

荣誉版主

论坛徽章:: 0

3楼 [报告]

发表于 2006-04-27 21:40 |只看该作者

如果不能倒着放的话,我觉得可以先考虑2D的情况,先考虑长和宽,就是40.5×49以及1190×210的关系
然后,算出各自的长宽比,较小的那个就是结果.

实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？

yzc2002

稍有积蓄

论坛徽章:: 0

4楼 [报告]

发表于 2006-04-27 21:57 |只看该作者

箱子不能倒放,高度就只能是210/7=30层了,所以高度信息就没用了
平面的东西可以当作一个二维数组A[m][n], (A[i][j], A[j][i])=(40.5,49), m=1190/40.5, n=210/49
限制条件:
S[i] = A[i][0] + ... +A[i][n-1] <=1190 表示横向的和
M[j] = A[0][j] + ... +A[m-1][j] <=210 表示纵向的和
然后...动态规划?