Calculating the optimal number of columns for a table layout - Only given the table width and a list of rectangles

Question

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?

Answer 1

I can see only optimizations to your solution:

Assumptions:
MaxAllowedWidth - maximum allowed sum of all columns width

1. When looking for possible solutions (your last table) stop trying to add new columns when total column width will exceed MaxAllowedWidth. In your sample you should stop on third step and do not try 4, 5, 6 columns because 3 columns already will take more space that you're allowed to. Please note that on this step we're taking into account only first row of items.

2. Go through possible columns number received in previous step in reverse order. First applicable solution will be optimal since it will have minimum possible number of rows.

3. On step 2 you should check that this number of columns will really fit into your MaxAllowedWidth. In your sample you will start with total width = 130 (100 + 30). Then going through the columns you should check whether this specific column should be enlarged. If column should be enlarged then check whether enlarged column will take more space than you have left. If it will then try solution with less columns. This checks will allow you to exit earlier and skip useless iterations/operations.

The question description is not that clear, I didn't got what do you want till I read comments. max row width makes no sense to me, total columns width sounds better, IMO.