研发组老李 发表于 2009-7-20 23:15

算问题：将N个大小不等的矩形不重叠地拼在一个指定宽度不定长度的大矩形里……

将N个大小不等的矩形(长或宽不大于大矩形的指定宽度)不重叠地拼在一个指定宽度不定长度的大矩形里，求使占用大矩形区域最小的拼法。
我的思路是先把N的N!种可全排列获取出来然后再去拼接算出总面积用快速排序法获取最小面积.但问题是N!的可能性太多了.当N>10时等待的时间就没办法忍受了.
大家都来出个主意拼个快速的算法.

曾轶可 发表于 2009-7-22 00:10

可以斜着放么？

字数补丁.exe

李宇春 发表于 2009-7-22 15:12

不管怎么放占得位置都是一样的，楼主多虑了。

2843223 发表于 2009-11-6 08:39

唱歌的也学习编程了 难得难得！！

2843223 发表于 2009-11-6 14:28

找一个数学老师做一个数学模型就可以了。

xzowen 发表于 2009-11-9 15:02

1# 研发组老李


先放最大的。然后围着最大的放……
唉，不知道可不可以，没试过，慢慢试吧~

huangyu830 发表于 2009-11-9 15:24

将全部矩形按边长从大到小排序，然后将最长边矩形放到“指定宽度不定长度的大矩形”。然后取相临近的矩形比较，是否到达指定宽度，不是换一下，是的话就将此矩形放到此处，在放下一个符合条件，定位，不符合条件，在换下一个放......最优，可能算法要更细些考虑更全些吧。
还好是二维的 要是三维的 就更难办了~！
页: [1]
查看完整版本: 算问题：将N个大小不等的矩形不重叠地拼在一个指定宽度不定长度的大矩形里……