Rectangle "best fit" optimisation

[krtxmrtz]

Here's my approach.
I've called W and H the width and height of the rectangular area and a the widht and b the height of a small rectangle ("brick") that's to be packed inside.

Let:

N_P = number of rows with the bricks in portrait orientation
N_L = number of rows with the bricks in landscape orientation

(see figures)

n_P = INT(W/a) is the number of bricks per row (portrait)
n_L = INT(W/b) is the number of bricks per row (landscape)

Then the total number of bricks is, at least:

Total = N_P*n_P + N_L*n_L

where these restrictions apply:

N_P <= INT(H/a)
N_L <= INT(H/b)
b*N_P + a*N_L <= H

Now, in some cases, after packing the last rows in landscape mode there could be some space left at one side (left or right) to place a few moore bricks in portrait orientation (see figure). This is the case if both these 2 conditions are met:

W - b*n_L >= a
H - b*N_P >= b

If you call:
k1 = W - b * n_L
k2 = H - b * N_P

then k1*k2 is the number of extra bricks.

'Rectangle width and height
Const W As Single = 1200
Const H As Single = 800
'Brick width (a) and height (b)
Const a As Single = 37
Const b As Single = 83
Private Sub main()
    Dim nRowsPort As Integer, nRowsLand As Integer
    Dim nBricksPerRowPort As Integer, nBricksPerRowLand As Integer
    Dim nRowsPortMax As Integer, nRowsLandMax As Integer
    'Height of all the rows (portrait plus landscape)
    Dim TotalH As Integer
    'Total number of bricks
    Dim TotalN As Integer
    'Total bricks with possible extras
    Dim GrandTotalN As Integer
    Dim tmp As Integer, i As Integer, j As Integer
    Dim dummy1 As Single, dummy2 As Single
    
    nBricksPerRowPort = Int(W / a)
    nBricksPerRowLand = Int(W / b)
    
    'Maximum values for nRowsPort and nRowsLand:
    nRowsPortMax = Int(H / b)
    nRowsLandMax = Int(H / a)
    'Try all integer combinations of nRowsPort and nRowsLand
    'with the restrictions:
    'nRowsPort <= nRowsPortMax
    'nRowsLand <= nRowsLandMax
    'b*nRowsPort + a*nRowsLand <= H
    TotalN = 0
    For i = 1 To nRowsPortMax
        For j = 1 To nRowsLandMax
            TotalH = b * i + a * j
            If TotalH <= H Then
                tmp = i * nBricksPerRowPort + j * nBricksPerRowLand
                If tmp > TotalN Then
                    TotalN = tmp
                    nRowsPort = i
                    nRowsLand = j
                End If
            End If
        Next
    Next
    'Check if some space is left to fit in a few more
    dummy1 = W - b * nBricksPerRowLand
    dummy2 = H - b * nRowsPort
    If dummy1 >= a And dummy2 >= b Then
        'Number of extra rows of bricks
        i = Int(dummy2 / b)
        'Number of extra bricks per row
        j = Int(dummy1 / a)
        'Number of extra bricks
        i = i * j
    Else
        i = 0
    End If
    
    'Grand total
    GrandTotalN = TotalN + i
    
    Debug.Print "Total bricks: " & CStr(TotalN)
    Debug.Print "Extra bricks: " & CStr(i)
    Debug.Print "Grand total bricks: " & CStr(GrandTotalN)
    Debug.Print "Rows (portrait): " & CStr(nRowsPort)
    Debug.Print "Rows (landscape): " & CStr(nRowsLand)
End Sub