相关疑难解决方法(0)

我有一堆矩形物体,我需要将它们装入尽可能小的空间(这个空间的尺寸应该是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,并且每个维度的给定最大大小)？

我有一个程序,将计算通过拟合矩形所采取的最小区域.

输入:不同高度和宽度的矩形.
输出:一个包含所有这些矩形的矩形.
规则:不能转动或滚动矩形,它们不能重叠.

我知道这是相关的,或者可能被定义为垃圾箱包装问题(NP-hard).然而,我找到的那些算法通常会对例如宽度设置限制.我没有这样的限制,唯一的目标是让得到的区域尽可能小.

关于什么算法适合获得合适解决方案的任何指针？