Ninth lab: 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 vehicles and each vehicle will not have more than 100 bins.
• The file will be "items.txt" and will reside in the same folder as your code.
  • The first line is the number of vehicles
  • The second line is the number of bins per vehicles
  • 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 bin being able to store up to 1.00 worth of units
• You are to output the status of each bin in each vehicle along with an analysis (how many vehicles are empty and how many bins are being used but not filled for each vehicle)
• The program should be called BinPacker
• You need to have at least one method besides the main method.
• You must use at least one constant
• You must use arrays as your primary storage
• All normal exceptions should be handled (not thrown)
• 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:
Vehicle 1:	1.000  1.000  0.700  0.400  with 2 bins not full 
Vehicle 2:	0.000  0.000  0.000  0.000  and is empty
Vehicle 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.