垂直包装(固定长度和水平位置)

本文关键字：水平 位置 包装 垂直 | 更新日期: 2023-09-27 17:51:10

假设我有一些项目，它们有一个定义的length和horizontal position(都是常量):

1 : A      
2 :     B
3 :  CC
4 :  DDD   (item 4 start at position 1, length = 3)
5 :    EE  
6 : F

我想把它们垂直地打包，这样就形成了一个高度尽可能小的矩形。

到目前为止，我有一些非常简单的算法，循环遍历项目，并逐行检查是否可以将它们放在该行(这意味着不会与其他内容发生冲突)。有时，它完美地(偶然地)工作，但有时，它导致非最优解。

下面是上面的例子给出的结果(一步一步):

 A      |  A   B  |  ACC B  |  ACC B  |  ACC B  |  ACC B  | 
                                DDD   |   DDD   |  FDDD   |
                                            EE  |     EE  |

而最优解是:

ADDDB 
FCCEE

注意:我发现在应用算法之前，先按它们的length(降序)排序项目，给出更好的结果(但它仍然不完美)。

是否存在一种算法可以在合理的时间内给出最优解?(尝试所有可能性是不可行的)

编辑:这里是一个使用排序技巧不起作用的例子，并且使用TylerOhlsen建议(除非我不理解他的答案)不会起作用:

1 : AA
2 :    BBB
3 :   CCC 
4 :  DD

将给出:

AA BBB
  CCC 
 DD

最优解:

 DDBBB
AACCC

垂直包装(固定长度和水平位置)

只是随口说说(我脑子里的想法，只是伪代码)。该算法循环遍历当前行的位置，并尝试找到放置在该位置的最佳项，然后在该行完成后继续移动到下一行。当所有项都被使用时，算法完成。

该算法性能的关键是创建一个有效的方法来找到在特定位置的最长项。这可以通过创建一个字典(或哈希表)来实现:key=positions, value=该位置的排序列表(按长度降序排序)。然后，在某个位置找到最长的项就像在哈希表中按位置查找项目列表并从列表中弹出最上面的项一样简单。

int cursorRow = 0;
int cursorPosition = 0;
int maxRowLength = 5;
List<Item> items = //fill with item list
Item[][] result = new Item[][];
while (items.Count() > 0)
(
    Item item = FindLongestItemAtPosition(cursorPosition);
    if (item != null)
    {
        result[cursorRow][cursorPosition] = item;
        items.Remove(item);
        cursorPosition += item.Length;
    }
    else //No items remain with this position
    {
        cursorPosition++;
    }
    if (cursorPosition == maxRowLength)
    {
        cursorPosition = 0;
        cursorRow++;
    }
}

这将导致示例1(在每个循环的开始)的以下步骤…

 Row=0  |  Row=0  |  Row=0  |  Row=1  |  Row=1  |  Row=1  |  Row=2  |
 Pos=0  |  Pos=1  |  Pos=4  |  Pos=0  |  Pos=1  |  Pos=3  |  Pos=0  |
        |  A      |  ADDD   |  ADDDB  |  ADDDB  |  ADDDB  |  ADDDB  | 
                                         F      |  FCC    |  FCCEE  |

这将导致例2中的以下步骤(在每个循环的开始)…

 Row=0  |  Row=0   |  Row=0   |  Row=1   |  Row=1   |  Row=1   |  Row=2   |
 Pos=0  |  Pos=2   |  Pos=4   |  Pos=0   |  Pos=1   |  Pos=3   |  Pos=0   |
        |  AA      |  AACCC   |  AACCC   |  AACCC   |  AACCC   |  AACCC   |
                                                         DD    |   DDBBB  |

这是一个经典的背包问题。正如@amit所说，它是np完备的。最有效的解决方案是利用动态规划来求解。

维基百科页面是一个很好的开始。我从来没有实现过任何算法来解决这个问题，但我研究了它与扫雷游戏的关系，这也是NP-Complete。

Wikipedia: backpack Problem

相关文章：