Rectangle "best fit" optimisation

[InertiaM]

I need suggestions

Imagine a cardboard box 1200 x 1000. You have to place smaller boxes (325 x 225) inside the larger one. The smaller boxes can only be rotated in multiples of 90 degrees. How many small boxes can be fitted into the large one?

The absolute "theoretical" maximum number of boxes would be (1200 x 1000) \ (325 x 225).

So how do I go about programming the remaining logic to ascertain the "best fit"

[jemidiah]

The complexity is in the rotation. Sometimes you might get a better fit by rotating one or several rows. I can't think of an easy way to characterize it, though, apart from some brute force if the actual problem size allows it. I'll think on it...

[InertiaM]

Brute force may be possible, because there will be a fairly limited number of combinations.

I've written the first step (simple row and column checking), but I'd still like suggestions.

    Private sMsg As String = ""

    Private Success As Boolean = False
    Private Success_Step As Integer = 0
    Private OuterBox As Size
    Private PieceToPlace As Size

    Private MaxTheoretical As Integer = 0

    Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles cmdCalculate.Click

        OuterBox = New Size(1200, 1000)
        PieceToPlace = New Size(396, 141)
        'PieceToPlace = New Size(ToInt32(nudWidth.Value), ToInt32(nudHeight.Value))

        Dim TimeTaken As New Stopwatch
        TimeTaken.Start()

        MaxTheoretical = (OuterBox.Width * OuterBox.Height) \ (PieceToPlace.Width * PieceToPlace.Height)

        Perform_Steps()

        TimeTaken.Stop()

        sMsg = ""
        sMsg &= String.Format("Assuming outer box size = {1} x {2}{0}{0}", Environment.NewLine, OuterBox.Width, OuterBox.Height)
        sMsg &= String.Format("Maximum theoretical pieces = {1}{0}{0}", Environment.NewLine, MaxTheoretical)

        If Success = True Then
            sMsg &= String.Format("**** SUCCESS !! ****{0}Step = {2}, time taken = {3}ms{0}{0}", Environment.NewLine, Success, Success_Step, TimeTaken.ElapsedMilliseconds)
        Else
            sMsg &= String.Format("Success = {1}, time taken = {3}ms{0}{0}", Environment.NewLine, Success, Success_Step, TimeTaken.ElapsedMilliseconds)
        End If

        sMsg &= String.Format("STEP 1{0}", Environment.NewLine)
        sMsg &= String.Format("{1} \ {2} = {3} @ {4:00.00}%{0}", Environment.NewLine, OuterBox.Width, PieceToPlace.Width, PieceWidthIntoWidth, ((PieceWidthIntoWidth * PieceToPlace.Width) / OuterBox.Width) * 100)
        sMsg &= String.Format("{1} \ {2} = {3} @ {4:00.00}%{0}", Environment.NewLine, OuterBox.Width, PieceToPlace.Height, PieceHeightIntoWidth, ((PieceHeightIntoWidth * PieceToPlace.Height) / OuterBox.Width) * 100)
        sMsg &= String.Format("{1} \ {2} = {3} @ {4:00.00}%{0}", Environment.NewLine, OuterBox.Height, PieceToPlace.Width, PieceWidthIntoHeight, ((PieceWidthIntoHeight * PieceToPlace.Width) / OuterBox.Height) * 100)
        sMsg &= String.Format("{1} \ {2} = {3} @ {4:00.00}%{0}", Environment.NewLine, OuterBox.Height, PieceToPlace.Height, PieceHeightIntoHeight, ((PieceHeightIntoHeight * PieceToPlace.Height) / OuterBox.Height) * 100)

        If Success_Step = 1 Then
            txtOutput.Text = sMsg
            Exit Sub
        End If

        
        'no result so far ...
        txtOutput.Text = sMsg
        Exit Sub

    End Sub

    Private Sub Perform_Steps()
        Success = False
        Success_Step = 0

        Step_1()
        If Success Then Exit Sub

    End Sub


#Region "_ Step 1 _"
    Private PieceWidthIntoWidth As Integer = 0
    Private PieceHeightIntoWidth As Integer = 0

    Private PieceWidthIntoHeight As Integer = 0
    Private PieceHeightIntoHeight As Integer = 0

    Private Sub Step_1()
        PieceWidthIntoWidth = OuterBox.Width \ PieceToPlace.Width
        PieceHeightIntoWidth = OuterBox.Width \ PieceToPlace.Height

        PieceWidthIntoHeight = OuterBox.Height \ PieceToPlace.Width
        PieceHeightIntoHeight = OuterBox.Height \ PieceToPlace.Height

        If (PieceWidthIntoWidth * PieceHeightIntoHeight) = MaxTheoretical OrElse (PieceHeightIntoWidth * PieceWidthIntoHeight) = MaxTheoretical Then
            Success = True
            Success_Step = 1
        End If
    End Sub
#End Region

[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

[NickThissen]

Isn't this basically the knapsack problem?
Maybe you can implement some kind of simple genetic algorithm, I think those are suited for problems like this (although I think they are better suited for less 'square' problems where you 1200*1000 grid is actually some arbitrary shape and your blocks are also arbitrarily shaped.

[InertiaM]

Here's my approach.

Thanks for that Seems like your pallets are smaller than ours

One point. If I take out my first step and just rely on yours, it wont find any solutions with only portrait or landscape rows. I suggest two lines are changed to :-

For i = 0 To nRowsPortMax
    For j = 0 To nRowsLandMax

Isn't this basically the knapsack problem?

Yes Nick, in a way it probably is I'll look at writing some form of algorithm - but krtxmrtz's solution is working quite well at the moment

[krtxmrtz]

...
One point. If I take out my first step and just rely on yours, it wont find any solutions with only portrait or landscape rows. I suggest two lines are changed to :-

For i = 0 To nRowsPortMax
    For j = 0 To nRowsLandMax

...

Good suggestion, as a matter of fact I didn't think much about possible improvements. Probably the method -and the code- can be further refined.

[opus]

I used this code in EXCEL

Public Sub CalculateMaxBrickNumer()
    Dim BoxWidth As Single
    Dim BoxHeight As Single
    Dim BrickHeight As Single
    Dim BrickWidth As Single
    Dim i As Integer
    Dim j As Integer
    Dim MaxNumber As Integer
    Dim Number As Integer
    MaxNumber = 0
    Dim NumberRowsHeightHeight As Integer
    Dim NumberRowsHeightWidth As Integer
    Dim NumberColumnsWidthWidth As Integer
    Dim NumberColumnsWidthHeight As Integer
    Dim MaxNumberRowsHeightHeight As Integer
    Dim MaxNumberRowsHeightWidth As Integer
    Dim MaxNumberColumnsWidthWidth As Integer
    Dim MaxNumberColumnsWidthHeight As Integer
    'The values are set on the activesheet in the named cells
    BoxWidth = ThisWorkbook.ActiveSheet.Range("BoxBreite").Value
    BoxHeight = ThisWorkbook.ActiveSheet.Range("BoxLänge").Value
    BrickWidth = ThisWorkbook.ActiveSheet.Range("BrickBreite").Value
    BrickHeight = ThisWorkbook.ActiveSheet.Range("BrickLänge").Value
    'The bricks will be placed for all possible numbers of columns in the direction BoxWidth to BrickWidth,
    'the rest of the useable Width will be used for placement of Bricks in the other direction.
    For i = 0 To Int(BoxWidth / BrickWidth)
        'i Columns of bricks are placed Width to Width
        NumberColumnsWidthWidth = i
        'calculate the possible number of Columns for Bricks in the other direction in the remaining Width
        NumberColumnsWidthHeight = Int((BoxWidth - i * BrickWidth) / BrickHeight)
        'how many Rows are possible direction BoxHeight to BrickHeight
        NumberRowsHeightHeight = Int(BoxHeight / BrickHeight)
        'how many Rows are possible direction BoxHeight to BrickWidth
        NumberRowsHeightWidth = Int(BoxHeight / BrickWidth)
        'Number of Bricks in Total
        Number = NumberColumnsWidthWidth * NumberRowsHeightHeight + NumberColumnsWidthHeight * NumberRowsHeightWidth
        If Number > MaxNumber Then
            MaxNumber = Number
            MaxNumberRowsHeightHeight = NumberRowsHeightHeight
            MaxNumberRowsHeightWidth = NumberRowsHeightWidth
            MaxNumberColumnsWidthWidth = NumberColumnsWidthWidth
            MaxNumberColumnsWidthHeight = NumberColumnsWidthHeight
        End If
        'Reset the Numbers
        NumberRowsHeightHeight = 0
        NumberRowsHeightWidth = 0
        NumberColumnsWidthWidth = 0
        NumberColumnsWidthHeight = 0
    Next i
    'Reverse the values and calculate again
    BoxHeight = ThisWorkbook.ActiveSheet.Range("BoxBreite").Value
    BoxWidth = ThisWorkbook.ActiveSheet.Range("BoxLänge").Value
    BrickHeight = ThisWorkbook.ActiveSheet.Range("BrickBreite").Value
    BrickWidth = ThisWorkbook.ActiveSheet.Range("BrickLänge").Value
    'The bricks will be placed for all possible numbers of columns in the direction BoxWidth to BrickWidth,
    'the rest of the useable Width will be used for placement of Bricks in the other direction.
    For i = 0 To Int(BoxWidth / BrickWidth)
        'i Columns of bricks are placed Width to Width
        NumberColumnsWidthWidth = i
        'calculate the possible number of Columns for Bricks in the other direction in the remaining Width
        NumberColumnsWidthHeight = Int((BoxWidth - i * BrickWidth) / BrickHeight)
        'how many Rows are possible direction BoxHeight to BrickHeight
        NumberRowsHeightHeight = Int(BoxHeight / BrickHeight)
        'how many Rows are possible direction BoxHeight to BrickWidth
        NumberRowsHeightWidth = Int(BoxHeight / BrickWidth)
        'Number of Bricks in Total
        Number = NumberColumnsWidthWidth * NumberRowsHeightHeight + NumberColumnsWidthHeight * NumberRowsHeightWidth
        If Number > MaxNumber Then
            MaxNumber = Number
            MaxNumberRowsHeightHeight = NumberRowsHeightHeight
            MaxNumberRowsHeightWidth = NumberRowsHeightWidth
            MaxNumberColumnsWidthWidth = NumberColumnsWidthWidth
            MaxNumberColumnsWidthHeight = NumberColumnsWidthHeight
        End If
        'Reset the Numbers
        NumberRowsHeightHeight = 0
        NumberRowsHeightWidth = 0
        NumberColumnsWidthWidth = 0
        NumberColumnsWidthHeight = 0
    Next i
    'Show the result on the Sheet
    ThisWorkbook.ActiveSheet.Cells(30, 1).Value = "MaxNumber: " & CStr(MaxNumber)
    ThisWorkbook.ActiveSheet.Cells(31, 1).Value = "RowsHeightHeight: " & CStr(MaxNumberRowsHeightHeight)
    ThisWorkbook.ActiveSheet.Cells(32, 1).Value = "RowsHeightWidth: " & CStr(MaxNumberRowsHeightWidth)
    ThisWorkbook.ActiveSheet.Cells(33, 1).Value = "ColumnsWidthWidth: " & CStr(MaxNumberColumnsWidthWidth)
    ThisWorkbook.ActiveSheet.Cells(34, 1).Value = "ColumnsWidthHeight: " & CStr(MaxNumberColumnsWidthHeight)
End Sub