5

我有一个不同尺寸的矩形列表。

rects = [100x20, 30x10, 10x10, 70x20, 40x30, 50x10]

我正在尝试从这些矩形中呈现一个表格。如果我有固定数量的列，我可以简单地计算行数以及每行和每列的大小，如下所示：

numCols = 4;

for (i = 0; i < rects.size - 1, i++):
    rect = rects[i];
    col = i % numCols;
    row = floor(i / numCols);

    columns[col] = max(columns[col], rect.width);
    rows[row] = max(rows[row], rect.height);
end for;

现在我希望我的表格由最大行宽配置。列数取决于最佳行宽的运行时计算。

使用上面的列表和设置为 140 的最大行，我希望我的表是：

rects = [100x20, 30x10, 70x10, 10x20, 40x30, 10x10]

100x20, 30x10
70x10, 10x20
40x30, 10x10

cols = [100, 30]
rows = [20, 20, 30]

我处理这种情况的第一个想法是为每个可能的列数缓存最大列宽。然后最后一个总和 <= 最大行宽的条目获胜。

max[1] = [100]
max[2] = [100, 30] - wins
max[3] = [100, 40, 70] - 210 > 140
max[4] = [100, 30, 70, 10]
max[5] = [100, 30, 70, 10, 40]
max[6] = [100, 30, 70, 10, 40, 10]

不幸的是，我需要为每个可能的列号创建一个 max 条目。该列表可能会变得非常大。有人知道解决这个优化问题的算法吗？

4

2 回答 2

1

我只能看到对您的解决方案的优化：

假设：
MaxAllowedWidth- 所有列宽度的最大允许总和

  1. 在寻找可能的解决方案（您的最后一张表）时，当总列宽超过MaxAllowedWidth. 在您的示例中，您应该在第三步停止并且不要尝试 4、5、6 列，因为 3 列已经占用了您允许的更多空间。请注意，在此步骤中，我们仅考虑第一行项目。

  2. 以相反的顺序浏览在上一步中收到的可能的列号。第一个适用的解决方案将是最佳的，因为它将具有尽可能少的行数。

  3. 在第 2 步中，您应该检查此列数是否真正适合您的 MaxAllowedWidth. 在您的示例中，您将从总宽度 = 130 (100 + 30) 开始。然后浏览这些列，您应该检查是否应该扩大该特定列。如果列应该被放大，那么检查放大的列是否会占用比你剩下的更多的空间。如果它会尝试使用较少列的解决方案。此检查将允许您提前退出并跳过无用的迭代/操作。

问题描述不是很清楚，直到我阅读评论，我才知道你想要什么。max row width对我来说没有意义，total columns width听起来更好，IMO。

于 2011-03-03T14:51:26.207 回答
0

为了完成这个问题，这里是实际的表格布局。您可以设置最大宽度，列数是根据该线程中讨论的算法计算的：

http://sibirjak.com/osflash/projects/as3commons-ui/layouts/showcase/#a6-dyntable

Edit:

To modify the number of boxes, please open the boxes window from the task bar at the bottom of the example flash window.

于 2011-04-18T13:17:41.120 回答