Library tutorials & articles
Bin Packing
By Mitch Dusina, published on 31 Mar 2006
Displaying the Data
You may have started to wonder how I managed to generate
those nifty little graphs at the bottom of the last four pages.
Well, I'm going to tell you. I created a UserControl that
completely separates the algorithm logic, and the painting logic.
The painting logic is the same no matter what algorithm was used to
generate the Bins.
The code really is self explanatory and comes with comments. This demonstrates the proper way to display process intensive visual data. Notice that actual drawing is done only when needed. When a Paint event is fired, the control is merely refreshing itself with a cached Bitmap. This cuts way down on processing time and is really the correct way of doing things.
Complete code may be found as a Resource, downloadable at the top of any page.
The code really is self explanatory and comes with comments. This demonstrates the proper way to display process intensive visual data. Notice that actual drawing is done only when needed. When a Paint event is fired, the control is merely refreshing itself with a cached Bitmap. This cuts way down on processing time and is really the correct way of doing things.
Private Sub UpdateGraph()
InitDrawingSurface()
DrawBins(DrawDemarcations())
pbDrawingSurface.Refresh()
End Sub
Private Sub InitDrawingSurface()
If Me.Width = 0 Or Me.Height = 0 Then Exit Sub
bmpGraph = New Bitmap(Me.Width, Me.Height)
g = Graphics.FromImage(bmpGraph)
g.Clear(Me.BackColor)
pbDrawingSurface.Size = bmpGraph.Size
End Sub
'Returns how wide the text was on the left hand side of the graph as well as draws teh Demarcations
Private Function DrawDemarcations() As Integer
Dim TextHeight As Integer = CType(g.MeasureString(Me.BinHeight.ToString, DrawingFont).Height, _
Integer)
'100% of BinHeight
g.DrawString(Me.BinHeight.ToString, DrawingFont, DrawingTextBrush, BORDER, BORDER - 8)
'75% of BinHeight
g.DrawString((Me.BinHeight * 0.75).ToString, DrawingFont, DrawingTextBrush, BORDER, _
CType((Me.Height - BORDER * 2) * 0.25, Integer) + BORDER - TextHeight + 6)
'50% of BinHeight
g.DrawString((Me.BinHeight * 0.5).ToString, DrawingFont, DrawingTextBrush, BORDER, _
CType((Me.Height - BORDER * 2) * 0.5, Integer) + BORDER - TextHeight + 6)
'25% of BinHeight
g.DrawString((Me.BinHeight * 0.25).ToString, DrawingFont, DrawingTextBrush, BORDER, _
CType((Me.Height - BORDER * 2) * 0.75, Integer) + BORDER - TextHeight + 6)
'0% of BinHeight
g.DrawString("0", DrawingFont, DrawingTextBrush, BORDER, Me.Height - BORDER - TextHeight + 5)
'If there's decimals, Width2 will be longer, else, Width1 will be
Dim Width1 As Integer = CType(g.MeasureString(Me.BinHeight.ToString, DrawingFont).Width, Integer)
Dim Width2 As Integer = CType(g.MeasureString((Me.BinHeight * 0.75).ToString, _
DrawingFont).Width, Integer)
Return Math.Max(Width1, Width2) + 5 + BORDER
End Function
Private Sub DrawBins(ByVal StartX As Integer)
Dim BinPixelHeight As Integer = Me.Height - BORDER * 2
Dim X1, X2, Y1, Y2 As Integer
Dim i As Integer
Y1 = BORDER
Y2 = Me.Height - BORDER
If Bins Is Nothing Then Exit Sub
'Draws the vertical lines that make up the bins
For i = 0 To Bins.GetUpperBound(0) + 1
X1 = StartX + (BIN_WIDTH * i)
X2 = X1
g.DrawLine(DrawingPen, X1, Y1, X2, Y2)
Next
Dim j As Integer
Dim BinValue As Integer
Dim TotalBinHeight, TotalPixelBinHeight As Integer
For i = 0 To Bins.GetUpperBound(0) + 1
X1 = StartX + (BIN_WIDTH * i)
X2 = X1 + BIN_WIDTH
'Draws the Bins
If i < Bins.GetUpperBound(0) + 1 Then
'Draws the gradient
TotalBinHeight = 0
For j = 0 To Bins(i).GetUpperBound(0)
TotalBinHeight += Bins(i)(j)
Next
TotalPixelBinHeight = CType(TotalBinHeight / Me.BinHeight * BinPixelHeight, Integer)
If TotalPixelBinHeight > 0 Then
'Draws the Bin gradient
DrawingBinBrush = New LinearGradientBrush(New Rectangle(X1 + 1, Me.Height - _
BORDER - TotalPixelBinHeight, BIN_WIDTH - 1, TotalPixelBinHeight), _
Me.BinColor1, Me.BinColor2, LinearGradientMode.ForwardDiagonal)
DrawingBinBrush.WrapMode = WrapMode.TileFlipXY
g.FillRectangle(DrawingBinBrush, New Rectangle(X1 + 1, Me.Height - BORDER - _
TotalPixelBinHeight, BIN_WIDTH - 1, TotalPixelBinHeight))
Dim LastY As Integer
For j = 0 To Bins(i).GetUpperBound(0)
BinValue += Bins(i)(j)
Y1 = CType(BinValue / Me.BinHeight * BinPixelHeight, Integer)
Y1 = Me.Height - Y1 - BORDER
Y2 = Y1
If j = 0 Then LastY = Me.Height - BORDER
'Draws the horizontal lines
g.DrawLine(DrawingPen, X1, Y1, X2, Y2)
'Draws the Element value
Dim TextSize As SizeF = g.MeasureString(Bins(i)(j).ToString, DrawingFont)
g.DrawString(Bins(i)(j).ToString, DrawingFont, Me.DrawingBinTextBrush, _
CType(X1 + (BIN_WIDTH / 2) - (TextSize.Width / 2), Integer), _
CType(Y1 + ((LastY - Y1) / 2) - (TextSize.Height / 2), Integer))
LastY = Y1
Next
'Draws the Bin Number
g.DrawString((i + 1).ToString, DrawingFont, DrawingTextBrush, _
CType(X1 + (BIN_WIDTH / 2) - (g.MeasureString((i + 1).ToString, _
DrawingFont).Width / 2), Integer), Me.Height - BORDER)
'Draws the Bin Count
g.DrawString(TotalBinHeight.ToString, DrawingFont, DrawingBinTextBrush, _
CType(X1 + (BIN_WIDTH / 2) - (g.MeasureString(TotalBinHeight.ToString, _
DrawingFont).Width / 2), Integer), 5)
BinValue = 0
End If
End If
Next
'Bottom line
g.DrawLine(DrawingPen, StartX, Me.Height - BORDER, X1, Me.Height - BORDER)
End Sub
Complete code may be found as a Resource, downloadable at the top of any page.
Languages I know (from most comfortable with, to least comfortable with): VB.NET, C#, VB6, and C/C++
I'm 19 years old and pursuing a MS in Computer Science at the Colorado School of Mines. M...
Related articles
Related discussion
-
How to write the category attribut in a class dynamically
by converter2009 (1 replies)
-
VB.NET: Hide and show table using radio buttons
by converter2009 (1 replies)
-
VB.Net Button Problem
by pysdex (0 replies)
-
Unable to access AxInterop.AcoPdflib.dll on 64 bit OS
by Shaila14041981 (0 replies)
-
Very Urgent regarding deleting the images from a folder
by Nanosteps (6 replies)
Related podcasts
-
xpert to Expert: Inside Concurrent Basic (CB)
"Concurrent Basic extends Visual Basic with stylish asynchronous concurrency constructs derived from the join calculus. Our design advances earlier MSRC work on Polyphonic C#, Comega and the Joins Library. Unlike its C# based predecessors, CB adopts a simple event-like syntax familiar to VB progr...
keen to have a look the c++ code.
zxy901109@hotmail.com
cheers
Hi Nimpo
thank you for this fine sourcecode, it helps me in understanding the problem of bin packing a bit, a porblem i just want to solve in my access database
but i have a question and something i did not found in your programm.
you mentioned the possibility of bins with different heights, but i did not find this in the sourcecode or how to enter it
and anothe question, do you think that your solution will work in combination with an existing access database ?
thanks
Andreas
Hello,
I really want to thank you for for this great article. However, I am currently working on my last year project, which is about 2 dimensional sheet cutting optimizer. Unfortunalty, I did not find any article that explains how to implement it by code.
Please can any one help me, this is very important because I just have about 2 weeks to finish it.
If any one has some helpful resources please send it to my email mishoco@hotmail.com
Michel
Hi,
i urgently need the codes too before 19/09/07. pls help me. could you send me the C++ and java version of the codes. Tankyou. send to nuranastacia@yahoo.com
can u plz send me a 'C++' or 'C' program code for first fit algorithms....
i need it urgently.... i need to submit code as my project by saturday 09/15/07...
example output:
enter no. of process to be loaded: 4
Job # Job size Arrival time
1 40K 0 msec
2 15K 7 msec
3 10K 5 msec
4 45K 10 msec
press any key to continue...
note: Job size and Arrival time will be inputted by the user and as you press enter in the Job size, "K" will be automatically displayed as well as the "msec" in the arrival time.
I believe that the First Fit algorithm will always be better than or equivalent to the Next Fit algorithm.
I first learned of the Bin Packing problem from an Algebra 3 class in high school. I implemented all of the algorithms the textbook talked about. Doing some quick online research, the only other algorithm I found a mention of was the "Almost Worse Fit". It simply places the object in the second emptiest bin (which is slightly better than Worse Fit apparently).
I cannot myself convert my code into other languages (I do not have the time or the motivation). But the concepts used in my code are not very language specific. It shouldn't take much time to do the conversion. If you do not know the target language well then you will simply have to search online for the syntax for that particular structure (Arrays, sorting, and drawing is all there really is to it, and I would think that drawing isn't that important). Plus, that way you'd actually be learning the language you are supposed to learn =)
i am in the same situation can u plz send me a C or C++ code for best/first/worst fit algorithms....
i need it to complete my assignment
bion365@gmail.com
thanks
can u plz send me a 'C' program code for best/first/worst fit algorithms....
i need it urgently.... i need to submit code as assignment......PLZ HELP
rrookwood_jm@yahoo.com
hey... grt job buddy...
can u plz send me a 'C' program code for best/first/worst fit algorithms....
i need it urgently.... i need to submit code as assignment..... by sunday...
plz help....
ritusmart2001@yahoo.com
Hello,
I'm new here and maybe missing something. Everybody says 'Great article' - but where the article itself? Same for code - is there code example or algorithm available?
Thanks.
Have you provided all the algorithms that are available to solve Bin Packing ?
I would also like to see a solution for the 0-1 Knapsack problem where each article(File) have a weight(MB) as well as a value(priority). The sack capacity let's say 700MB.
Thank you.
Great article. Thanks.
Hi,
Excellent article. Would you know how or have a PHP version of this problem?
Regards, Michael
I have a quick question. Can there ever be more bins in a First Fit Algorithm than a Next Fit algorithm?
Well as for variable sized bins, all you would need to do is have an array of Integers that holds the size for each Bin. Then in my code, where ever there is a reference to BinHeight, you would simply reference BinHeightArray(ThisBinNumber) instead. You could incorporate all this code into its own Class as it should be an make the array a property so you can do bounds checking, check for valid values, and all that good stuff.
As for 2-dimensional Bin Packing... I'd have to get back to you on that one. I understand what you mean but I don't think these algorithms are easily translatable into another dimension... Try to formulate an algorithm that starts filling in the lower left to the lower right, and then starts moving up. I can't vouch for the efficiency of this idea but its my only lead...
Great article, I was looking for something exactly like this! How difficult would it be to modify the code to allow for varible size bin widths, and then pack each element either horizontal or vertial depending on height and width. If you can figure that out let me know. Thanks and keep up the good work.![Smiley Face [:)]](/emoticons/emotion-1a.gif)
This thread is for discussions of Bin Packing.