算法寻找最小面积占用n个矩形
我有一些矩形，我想找到可以覆盖所有小矩形的最小矩形。 不允许旋转。
使用蛮力我想找到我的答案。 我试图用java编写它。 我知道我应该检查我的n个项目的所有排列，并找到最少的区域。 为了使它更容易，我试图找到最小的可能区域。 然后我用一个布尔值的2维数组来检查每个单元格是否被占用。 但我无法弄清楚（编码）。
如何检查我的物品是否可以放入我的有限区域？ 例如，我在x[0][0]到x[10][1]找到了我的第一个项目，并使该范围内的所有单元都为真，但我不知道如何告诉我的程序检查其他单元格是否有下一个项目。 你能告诉我关于我的算法需要实现的步骤吗？
您的问题属于2D-bin包装类别。 这是一个NP难题，所以没有一个有效的多项式时间算法来解决它。 （除非P == NP）。
你可以尝试暴力算法或聪明的启发式，这将给你相当优化的解决方案。
请参阅以下链接：
1.如何以编程方式实现二维装箱？ （用于讨论各种算法）
2. http://www.codeproject.com/Articles/210979/Fast-optimizing-rectangle-packing-algorithm-for-bu（关于实现细节）
3. http://www.binpacking.4fan.cz/（用于可视化不同的启发式）
你的蛮力算法效率很低。 矩形可以放置的排列非常巨大并且很难找到。 我建议你尝试上面提到的算法，比找到所有的排列更容易实现。
链接地址: http://www.djcxy.com/p/63241.html上一篇: algorithm for finding least area occupied with n rectangulars