Question: This is Java, you can write either code or psuedocode. In the bin packing problem, objects of different volumes must be packed into a finite
This is Java, you can write either code or psuedocode.
In the bin packing problem, objects of different volumes must be packed into a finite number of bins or containers, each of capacity C, in a way that minimizes the number of bins used. A well-known heuristic for this problem, known as "Worst fit" proceeds as follows. Consider the items in the order they are given. Put each item into the emptiest bin among those with something in them. Start a new bin if the item does not fit into any bin that has already been started. For example, if the sizes are: {3,4,2,3} and the capacity of the bin is C=6, then the worst fit algorithm proceeds as follows: Item 1: 3 is placed in bin 1: {3}. Item 2: 4 does not fit in bin 1. A new bin is started for it: {3}{4}. Item 3: 2 is placed in bin 1 because it has most available capacity: {3,2}{4}. Item 4: 3 does not fit in bins 1 and 2. A new bin is started for it: {3,2}{4}{3}. The algorithm returns 3, because it uses 3 bins. Write the above algorithm using priority queues and analyze its running time. int worstFit(int[] size, int C) // C is capacity of each bin. Return number of bins used.
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
