请教大家一个算法，脑子烧糊了。。。

[suspended]

题目：

已知一个矩形容器[(0,0), (W,H)]，其中已经容纳（摆放）了 m 个小矩形，
这些矩形均满足以下条件：
1. 当然都比容器小，且摆放位置未超出容器范围；
2. 所有小矩形的边均与容器的某一边平行或者重叠；
3. 所有小矩形不重叠；
4. 所有小矩形至少有两条相邻边与容器或者其他小矩形的边重叠（其实就是指
小矩形向某角落挤紧，在保持不重叠的情况下只有 0 个或 1 一个自由度可滑动）

问题算法：
取另一个小矩形 (w,h)摆放到容器中，使其满足所有上述 1~4 的条件，
求所有可能的摆法。


想了很久没有思路。请教诸位了。

[binux]

@suspended 你需求只有添加 1 个，不能再多个矩形吗？如果不是，你怎么保证局部最优就是全局最优？

[suspended]

@binux 添一个能搞定之后，添多个不就是一个一个添喽。:D

局部最优当然不保证全局最优。全局最优根本不可能实现，因为是个 N-P 问题啦。全局较优是外围算法来负责的，我这个问题里的算法只是全局算法里的一个步骤而已。因为论文里面这个步骤的算法没有交代，自己琢磨了几个小时也只有穷举的办法，所以才拿上来请教一下诸位同仁。

[suspended]

@SCaffrey 哎呀，漏掉了这位仁兄，不好意思。 m 最大在 1000 这个量级，谢谢。

[yangyaofei]

这个……是为了更省料的切割方法？

[suspended]

@yangyaofei 是滴是滴，除了省料，还要好切

[SCaffrey]

既然 1000 那么枚举放的位置不就是很妙了吗 XD
如果每次查询的小矩形规格是定值的话似乎可以预处理一波吧

[suspended]

@SCaffrey 规格肯定有若干，每个规格的矩形有若干。所以不想穷举的说。。。