Bin包装与扭曲？

我一直在寻找某种算法来照顾我所遇到的问题。我遇到的最接近的事情是一个bin包装算法，但我不认为它的安静，我正在寻找。Bin包装与扭曲？

这份文件是我的问题的图示和预期输出： http://www.scribd.com/doc/90871434/Rectangles

我的想法在哪里可以找到最低（高）的矩形，并创建满足剩余矩形的宽的长方形，并与一些递归找出其余的。

我基本上试图做的是找到最小数量的垂直堆叠的矩形，给定N个水平放置的矩形。

在Java中这样做我有一个HashMap与输入矩形。

任何想法，代码，链接？谢谢

来源

2012-04-23 user1352234

我认为你应该使用分而治之。

当你找到最低的矩形时，你也拆分你的数据集。下一个矩形不是排在左侧就是右侧。这是递归的。

来源

2012-04-24 00:22:28 bdecaf

找到最小的矩形。

创建你的第一个结果矩形。

确定剩余的矩形。

将算法应用于所有连续的其余矩形组。

来源

2012-04-23 20:54:06

啊是的，这是我的思路。问题是算法的一部分，就像遍历HashMap的代码一样，最终将矩形放在正确的位置。 – user1352234 2012-04-23 21:08:14

更为明显的表示形式是从左到右排列的矩形数组。用这种表示法，实现上述算法就容易得多。最坏的情况是'O（n * n）'，它的平均值是'O（n log（n））'。如果该算法速度不够快，我有一个更复杂的算法，即O（n log（n））最坏的情况。但复杂性可能不合理。 – btilly 2012-04-23 21:51:54

Bin包装与扭曲？

回答

相关问题