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

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。