Rectangle "best fit" optimisation

[InertiaM]

I need suggestions :blush:

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" :confused:

[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:

NP = number of rows with the bricks in portrait orientation
NL = number of rows with the bricks in landscape orientation

(see figures)

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

Then the total number of bricks is, at least:

Total = NP*nP + NL*nL

where these restrictions apply:

NP <= INT(H/a)
NL <= INT(H/b)
b*NP + a*NL <= 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*nL >= a
H - b*NP >= b

If you call:
k1 = W - b * nL
k2 = H - b * NP

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 (http://en.wikipedia.org/wiki/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 :thumb: 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 :D

[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