2

假设我有一些项目，它们有一个定义的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
4

2 回答 2

1

只是吐口水（从我的头上掉下来，只是伪代码）。该算法循环遍历当前行的位置，并尝试找到放置在该位置的最佳项目，然后在该行完成时移动到下一行。当所有项目都被使用时，算法完成。

该算法性能的关键是创建一种有效的方法，在特定位置找到最长的项目。这可以通过创建一个字典（或哈希表）来完成：键=位置，值=在该位置的项目的排序列表（按长度降序排序）。然后在某个位置找到最长的项目就像从该哈希表中按位置查找项目列表并从该列表中弹出顶部项目一样简单。

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  |
于 2013-01-09T15:37:49.553 回答
-2

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

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

维基百科：背包问题

于 2013-01-09T13:57:45.013 回答