计算表格布局的最佳列数-仅给出表格宽度和矩形列表

Question

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

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中创建一个条目。该列表可能会变得很大。有人知道解决此优化问题的算法吗？

Answer 1

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

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

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

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

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

问题描述不太清楚，看了评论才明白你想要什么。max row width对我来说毫无意义，total columns width听起来更好，IMO。