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

[suspended]

题目：

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

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


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

[sherlocktheplant]

你这是要压缩贴图吗？

[suspended]

@sherlocktheplant 不是，工业需求。

[Kilerd]

这算是动态规划的题目把。

[sherlocktheplant]

你可以看看 uv 压缩相关的算法 虽然是图形学的东西 但是实际是一样的

[9hills]

4 并不能得出 向某角落挤紧

举个例子，小矩形绕内壁一周。

[SCaffrey]

数据范围大该怎样呢

[suspended]

@sherlocktheplant 那个方面的算法不太符合要求，因为不会考虑是否方便切割之类的工业要求。

[suspended]

@9hills 虽然我括号里的这个解释其实有点多余。。。不过你说的小矩形绕内壁一周没问题啊，只有在往四个角落挤紧是符合条件 4 的，因为要求至少两条相邻边重叠。

[9hills]

@suspended 某角落指的四个角落中任意一个么。。

就算你这么解释也不对，比如容器 10X10 的，然后放入一个 5X10 的在中间，四个角落都不沾

另外题目里也没有说矩形是不是有最小单位，如果没有的话，那解肯定是无穷多个

[9hills]

@suspended 没看到相邻边，有这个约束也没关系，在 5X10 靠边放一个 1X1 的就好了，还是四个角落都不沾

[suspended]

@9hills
"比如容器 10X10 的，然后放入一个 5X10 的在中间，四个角落都不沾 "

所以这种情况不符合要求 4 ，因为没有任何边与其他矩形重合。
“某角落”是指任意角落，我表达得有些含糊了。

另外，矩形肯定最小 1x1 ， 0x0 不能称为矩形吧？

[suspended]

@9hills
"在 5X10 靠边放一个 1X1 的就好了，还是四个角落都不沾"

这个不矛盾啊，我是指往某一个角落挤紧，不是说位于某个角落。当然，其实不看括号里的解释就好了，如果觉得解释反而更不好理解的话。

[9hills]

@suspended 看我补充，你找两个 1x1 的方块，靠紧。放到任意一个边上，依然满足你的 1-4 的全部要求
0.5x0.5 就不是矩形了？

[suspended]

@9hills 啊，对头，看来括号里的说明似乎比条件 4 更严密些，我得想想如何修改。

矩形尺寸肯定是整数，我补充一下题干好了。

[9hills]

@suspended 你把矩形改成从第一个小矩形开始，必须一个一个添加就行了。

看起来想是做切割。。。

[suspended]

@9hills 是做切割。我找了好些论文，比较了各种算法，挑出来一个最符合需求的来实现。论文嘛，限于篇幅，都语焉不详的，实现的时候发现其中的一个子算法（就是我的问题所述）论文里并没有交代，所以放上来请教一下大家。

"你把矩形改成从第一个小矩形开始，必须一个一个添加就行了。"，的确就是这么一个过程，不过会有本质区别吗？

[9hills]

其实我看了下，用轮询的方法，时间复杂度也不高。 M 和 N 不大的话轮询就好了。。。

[suspended]

@9hills 我目前想破脑袋想出来的也只有轮询了。 3x 。

[binux]

工业算法和竞赛算法是不同的，很多时候，竞赛算法就是在「求所有可能的摆法」以及「最佳」中纠结。
但是在工业中，贪婪次优都是是可行的。

一边给出「求所有可能的摆法」，一边又要「考虑是否方便切割」，先搞清楚到底要什么比较好。

[suspended]

@binux 是从所有可能摆法中选优。题目的这个算法，即便穷举的话，时间复杂度大约是 O(n^2)？(不好意思，不懂算法啦）所以「求所有可能的摆法」完全可行吧，「考虑是否方便切割」就是如何选优（选优还有其他要求）的问题，这个条件以目前的计算能力是达不到最优的，只能在可接受的时间内找到个较优的算法。

现在就是「求所有可能的摆法」这个步骤希望找到比穷举更好的办法喽。