Arrays (2D): Bin Packing

Learning Objective(s)

1. Learn to use two dimensional arrays
2. Be introduced to an NP Complete problem

Overview of the program

Bin packing is a standard problem that can be very computational expensive to solve. A description of the problem can be found on Wikipedia. Read it to understand the overall problem. You will be programming a very simple (and typically non-optimal) solution to it.

Details

• You will not have more than 100 tubs and each tub will not have more than 100 boxes.
• The file will be "items.txt" and will reside in the same folder as your code.
  • The first line is the number of tubs
  • The second line is the number of boxes per tub
  • The remaining lines (undetermined number of lines) is the size of each item (as a double)
• Your items will be "normalized' (i.e. between 0 and 1) with each box being able to store up to 1.00 worth of units
• You are to output the status of each box in each tub along with an analysis (how many tubs are empty and how many boxes are being used but not filled for each tub)
• The program should be called BinPacker
• One method should receive your 2D array (representing how much room is left for a given box in a given tub) and an item to store. It should find the first box that has enough room in it and store it there. If there is no room big enough it should fail.
• You should have one method that does all the output.
• You should have a third method that reads in all values and calls the first one for each number.
• You must use at least two constants (one for the max number of tubs and one for the max number of boxes per tub). There is a third constant that would be good to have.
• You must use arrays as your primary storage
• It is suggested that you use the "first fit" method. It is the easiest

Sample file

3
4
.5
.6
.2
.3
.7
.3
.1
.4

Output

Here is your report:
tub 1:	1.000  1.000  0.700  0.400  with 2 boxes not full 
tub 2:	0.000  0.000  0.000  0.000  and is empty
tub 3:	0.000  0.000  0.000  0.000  and is empty

Submission

1. Create an empty zip folder.
2. Place your program (.java file) in it
3. Place your software development report in it.
4. Submit the zip folder on canvas

Optional improvements

• Also implement best fit and compare it to first fit in terms of being closer to optimal in the lessons learned. Discuss when each is better than the other.
• Also implement worst file (along with best fit) and compare best fit to worst fit in terms of being closer to optimal in the lessons learned. Discuss when each is better than the other.