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

This program is to try to fill shipping containers for cargo ships. The idea is to place boxes in 20 equipment unit (TEU) shipping containers. And them place the containers on a cargo ship. You are just to identify where each box goes. At the end you should report the status of each container on each cargo ship and some summary information. Assume the limiting factor for placing a box in a container is its weight. Each container can only hold sa set weight (which is the same for all containers).

This is a standard problem referred to as "bin packing" 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

• Use constants for: the maximum weight of a container, the number of containers in a ship, and the number of ships. These might be changed if the company buys more ships and/or bigger ships (or containers).
• The file will be "items.txt" and will reside in the same folder as your code. It contains integers. Each integer represents the weight of one box.
• You are to output the status of each container on each ship along with an analysis
  • The status of each container on each ship
  • How many containers for each ship are not full
  • An overall sum of how much additional weight the fleet of ships can carry vs. the total capacity.
• The program should be called BinPacker
• One method should receive your 2D array (representing how much room is left for for each container on each ship) and an item to store. It should find the first container that has enough room in it and store it there. If there is no room to store it, it should fail. No item can be split to be put in more than one container.
• 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 arrays as your primary storage
• It is suggested that you use the "first fit" method. It is the easiest

Sample dialogue

For a fleet of 3 ships that can each hold 4 containers (of 100 units each): Input file

50
60
20
30
70
30
10
40

Output

Here is your report:
Ship 0
   Container 0:   100  
   Container 0:   100  
   Container 0:    70  
   Container 0:    40  
      2 containers are not full
Ship 1
   Container 1:     0  
   Container 1:     0  
   Container 1:     0  
   Container 1:     0  
      4 containers are not full
Ship 2
   Container 2:     0  
   Container 2:     0  
   Container 2:     0  
   Container 2:     0  
      4 containers are not full
890 more weight can be carried.
This represents 74.167 percentage wasted.

Submission

1. Create your SDR.
   • In Lessons Learned, include a discussion comparing your previous program to this one. How did using arrays impact the result.
   • Your testing should:
     • include at least 2 different types of errors
     • different sizes of containers, number of containers, and number of ships
     • ensure that every line of code is executed at least once
     • a very large set of data. (For this you don't need to include in the report the status of each container, just the ships. Also don't include the input but add that file to the zip folder and just refer to in in the SDR)
     • for the smaller files, add copies of your files that you used (with appropriate links back to the test cases) at the end of the report. Try to put them in columns to save space. You might want to have different sets of files for some of the different tests.
   • If you used any hints, be sure to indicate that in the Outside Resources Used section
   • For Future Improvements include a discussion about ideas how to not waste as much space.
2. Convert your SDR into a pdf document
3. Create an empty zip folder
4. Place your java file and pdf document in it.
5. Submit the zip folder on canvas

Hints

1. Algorithm hint to place one item

Optional improvements

Optional improvements should ONLY be worked on once the program is completing working. In addition, the work is to be done on your own with little if any help for lab assistants or the instructor.

• Throw an exception when an item is encountered and there is no container that can hold it. Program should give an error and exit.
• 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.
• Discuss (in future improvements) what changes would need to be made to your code to allow each ship to have a different number of containers. For even more extra credit, implement it