Let us look at an example. Suppose there are 3 bins with capacities 10,20,15. Suppose there are 5 objects with sizes 6,8,9,2,8. One way of packing the objects is to assign 2nd object to the first bin, 1st and 5th objects to the second bin, and 3rd and 4th objects to the third bin. Of course, there are other ways of doing this packing as well. In fact given an instance of this problem, it might happen that it is not possible to pack the objects into bins.
We will not worry about finding a good algorithm for bin packing. In fact, we will work with the well known Best Fit Algorithm for bin backing. The best fit algorithm for bin packing can be described as follows. When we need to add an object to one of the bins, we will pick the bin which has the largest remaining capacity . Let us go back to the example above. We will add the objects in the order 6,8,9,2,8. When we need to add the first object, the remaining capacities of the bins are 10,20,15 respectively. So it goes to the second bin. The remaining capacities are now 10,14,15. So the 2nd object goes to the third bin. The remaining capacities are now 10,14,7. The 3rd object goes to the 2nd bin. The remaining capacities are 10,5,7. The last 2 objects now go the the first bin.
In this assignment, you will develop an implementation of the best fit algorithm. For sake of implementation, assume that each bin has a unique id, which can be any integer. Similarly, each object has a unique id, which can be any integer. Of course, two bins can have the same capacity or two objects can have the same size.
The program should implement the following operations:
// Requirement : Use Java 8 class BestFit{ public BestFit(){ // Fill this } public void add_bin(int bin_id, int capacity){ // Fill this } public int add_object(int obj_id, int size){ // Fill this // return the bin id to which this object is added } public int delete_object(int obj_id){ // Remove the object with id "id" from the bin it is placed in. // Fill this // Return the bin_id from which this object was removed } public List> contents(int bin_id){ // Return the list of current objects in the bin with id "bin_id" : list of pairs for each object in the bin. } }