我有一堆长方形的物体，我需要把它们塞到尽可能小的空间里(这个空间的维数应该是2的幂)。
我知道各种包装算法，将包装项目以及尽可能到一个给定的空间，但在这种情况下，我需要算法来计算出该空间应该有多大。
假设我有下面这些矩形
128 * 32
128 * 64
64 * 32
64 * 32
它们可以装在128*128的空间里
_________________
|128*32 |
|________________|
|128*64 |
| |
| |
|________________|
|64*32 |64*32 |
|_______|________|
然而，如果还有160*32和64*64，则需要256*128的空间
________________________________
|128*32 |64*64 |64*32 |
|________________| |_______|
|128*64 | |64*32 |
| |_______|_______|
| | |
|________________|___ |
|160*32 | |
|____________________|___________|
有什么算法能够打包一堆矩形并确定容器所需的大小(以2为幂，并且在每个维度的给定最大尺寸范围内)?
关于这个问题有大量的文献。一种好的贪婪启发式方法是将矩形从大到小放置在容器底部和左侧的第一个可用位置上。想象重力把所有的东西都拉到左下角。对于这个谷歌“沙雷左下角包装”的描述。
为了获得最佳解决方案，最先进的技术可以在几秒钟内完成20多个矩形。Huang有一种算法，可以将寻找最小的外围包围框的问题与确定一组矩形是否适合特定大小的包围框的问题分开。你给他的程序一组矩形，它会告诉你打包这些矩形所需要的最小的包围框。
对于您的情况，外部循环应该从最小的边界框向上迭代(宽度和高度依次以2的幂增加)。对于每个包围框，测试一下是否可以为矩形找到一个填充。你会得到一堆“不”的答案，直到第一个“是”的答案，这将保证是最优解。
对于算法的内部循环——对特定大小的边界框回答“是”或“否”的循环，我将查找Huang参考并实现他的算法。他在基本算法的基础上进行了大量优化，但你只需要最基本的部分。由于您希望处理旋转，因此在搜索过程中的每个分支点上，只要同时尝试两个旋转并在两个旋转都没有得到解决方案时回溯即可。
关于这个问题有大量的文献。一种好的贪婪启发式方法是将矩形从大到小放置在容器底部和左侧的第一个可用位置上。想象重力把所有的东西都拉到左下角。对于这个谷歌“沙雷左下角包装”的描述。
为了获得最佳解决方案，最先进的技术可以在几秒钟内完成20多个矩形。Huang有一种算法，可以将寻找最小的外围包围框的问题与确定一组矩形是否适合特定大小的包围框的问题分开。你给他的程序一组矩形，它会告诉你打包这些矩形所需要的最小的包围框。
对于您的情况，外部循环应该从最小的边界框向上迭代(宽度和高度依次以2的幂增加)。对于每个包围框，测试一下是否可以为矩形找到一个填充。你会得到一堆“不”的答案，直到第一个“是”的答案，这将保证是最优解。
对于算法的内部循环——对特定大小的边界框回答“是”或“否”的循环，我将查找Huang参考并实现他的算法。他在基本算法的基础上进行了大量优化，但你只需要最基本的部分。由于您希望处理旋转，因此在搜索过程中的每个分支点上，只要同时尝试两个旋转并在两个旋转都没有得到解决方案时回溯即可。
