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

发布于 2024-10-19 22:30:33 字数 979 浏览 10 评论 0原文

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

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

原文

I have a list of rectangles with different dimensions.

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

I am trying to render a table from these rectangles. If I would have a fix number of columns, I simply could calculate the number of rows and the size of each row and column like this:

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;

Now I want my table to be configured by a max row width. The number of columns depends on a runtime calculation of the optimal row width.

With the list above and a max row with set to 140 I expect my table to be:

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

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

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

My first idea to approach the situation is to cache the max column width for each possible number of colums. The last entry with a sum <= max row width then wins.

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]

Unfortunately, I need to create an entry in max for each possible column number. The list can get pretty big. Does someone know an algorithm to solve this optimization problem?

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

余生共白头 2024-10-26 22:30:33

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

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

在寻找可能的解决方案（您的最后一个表）时，当总列宽度超过MaxAllowedWidth时，停止尝试添加新列。在您的示例中，您应该在第三步停止，不要尝试 4、5、6 列，因为 3 列已经占用了您允许的更多空间。请注意，在此步骤中，我们仅考虑第一行项目。
以相反的顺序遍历上一步中收到的可能的列号。第一个适用的解决方案将是最佳的，因为它将具有尽可能少的行数。
在第 2 步中，您应该检查此列数是否确实适合您的 MaxAllowedWidth。在您的示例中，您将从总宽度 = 130 (100 + 30) 开始。然后浏览各列，您应该检查是否应放大该特定列。如果应扩大列，请检查扩大的列是否会占用比剩余空间更多的空间。如果它会尝试使用更少的列的解决方案。此检查将允许您提前退出并跳过无用的迭代/操作。

问题描述不太清楚，看了评论才明白你想要什么。 最大行宽度对我来说毫无意义，总列宽度听起来更好，IMO。