Library tutorials & articles

Bin Packing

By Mitch Dusina, published on 31 Mar 2006
Mitch Dusina 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. My...
Page 1 of 7
  1. Bin Packing, What is It?
  2. Next Fit Algorithm
  3. First Fit Algorithm
  4. Worst Fit Algorithm
  5. Best Fit Algorithm
  6. Decreasing Algorithms
  7. Displaying the Data

Bin Packing, What is It?

   Bin Packing is a mathematical way to deal with efficiently fitting Elements into Bins.  Now, a Bin is something that can hold inside itself a certain amount (it's Bin Height).  Every Element is of a certain, non-zero, and positive value ( Element Height).  The goal of every Bin Packing algorithm is to use the least amount of Bins to hold the required number of Elements.

Bin:  A fixed-size container that can hold Elements.
Bin Height:  The specified amount that each Bin can hold.
Element:  An item that is to be placed in a Bin having a certain Element Height.
Element Height:  The amount of Bin space the Element will take up if placed in that Bin.

   Now, why is this useful?  Several real-world problems can be optimized and made to run more efficient by employing this solution.  Image for a moment that you have a package of blank CDs that can hold 80 minutes of music each.  You have 100 songs of varying lengths.  You want to use the least amount of blank CDs to fit all of your songs on.  This is a Bin Packing problem.

Bin: The blank CDs.
Bin Height:  80 (minutes) or 4,800 (seconds).
Element:  One song.
Element Height:  The length of each song in minutes or seconds.

   Other examples include:  Using the least amount of boards to cut out small pieces for a construction project, fitting large files onto small capacity hard drives, etc.

   There is one hitch with a Bin Packing problem, that is a Bin Packing problem is classified as NP-Complete.  This basically means that their is no way of  being guaranteed the best solution without checking every possible solution.  This is not to say that a solution reached by one of the following algorithms is not optimal, it may be.  The classic NP-Complete problem is the Traveling Salesman Problem.  The algorithms presented here do give reasonable, practical solutions however.

Related tags

vb.net

Comments

  1. huang chang hsueh
    yesterday

    I am learning os system now.Teacher assign me a pratice to implement firfit . can u plz send me a c++ or c code for best fit algorithm. Please help me

    a7300323@gmail.com

  2. sc609 ch
    14 Nov 2008 at 21:44

    my email id is mysc609@gmail.com.....

  3. sc609 ch
    14 Nov 2008 at 21:42

    Could someone please mail me the C or C++ or java code of bin packing algorithm if u have it.

    Thanks

  4. wendy nielsen
    22 Jun 2008 at 01:09

    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  

     

  5. alul
    17 Apr 2008 at 09:12

    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

  6. MisSya
    16 Sep 2007 at 06:26

    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

  7. ian kirby fisalbon
    12 Sep 2007 at 10:29

    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.


  8. Mitch Dusina
    11 Sep 2007 at 05:13

    I have just returned from an extended absence from this forum so I realize this is rather late.


    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 =)








  9. Bion Bion
    25 Jun 2007 at 05:19

    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

  10. ROOKIE ROYAL
    16 Jun 2007 at 23:48

    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

  11. Ritesh G
    28 Apr 2007 at 03:09

    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

  12. Slava M
    07 Mar 2007 at 16:24

    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.

  13. HackieChan
    03 Jan 2007 at 19:22

    Excellent article. I was looking for something exactly like this. I think it will help me backing up files to the CDs.
    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.


  14. cyberagui
    12 Dec 2006 at 18:02

    Great article. Thanks.

     

  15. Michael LeComte
    28 Oct 2006 at 19:48

    Hi,

    Excellent article.  Would you know how or have a PHP version of this problem?

    Regards, Michael

  16. Leisa Smith
    17 Oct 2006 at 22:13

    I have a quick question.  Can there ever be more bins in a First Fit Algorithm than a Next Fit algorithm?

  17. Mitch Dusina
    10 Jul 2006 at 22:27

    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...





  18. Don Slack
    24 Jun 2006 at 14:37

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

  19. Developer Fusion Bot
    01 Jan 1999 at 00:00

    This thread is for discussions of Bin Packing.

Leave a comment

Sign in or Join us (it's free).

AddThis

Related articles

Ask a question

Related discussion

Related jobs

Events coming up

  • Dec 6

    Developing AJAX Web Applications with Castle Monorail

    London, United Kingdom

    Monorail is the model-view-controller engine of the Castle Project, bringing many of the best ideas of Ruby on Rails to the .NET world. In this talk, David De Florinier and Gojko Adzic show how Monorail makes it easy to develop .NET based AJAX applications, and how to use the Castle Project to build Web 2.0 applications effectively. Come to this session if you are a .NET web developer. Everyone is welcome!

Languages

Web Development

Frameworks & Architecture

Other major sections