Question
•First-Fit: Put each item as you come to it into the first (earliest opened) bin into which it fits. If there is no available bin then open a new bin.
•First-Fit-Decreasing: First sort the items in decreasing order by size, then use First-Fit on the resulting list.
•Best Fit: Place the items in the order in which they arrive. Place the next item into the bin which will leave the least room left over after the item is placed in the bin. If it does not fit in any bin, start a new bin.
a) Give pseudo code and the running time for each of the approximation algorithms.
b) Implement the algorithms in Python, C++ or C. Your program named binpack should accept multiple test cases and output to the terminal the number of bins each algorithm calculated for each test case.
c) Randomly generate at least 20 bin packing instances. Summarize the results for each algorithm. Which algorithm performs better? How often? Note: Submit a description of how the inputs were generated not the code used to produce the random inputs.
Solution Preview
This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.
Problema).
First Fit:
• Initialize the no. of bins with 0
• allocate an array to can keep track of the remaining space from a bin after inserting an item into it
• for i=1 to no. of items do
for j=1 to no. of bins do
put item into the 1st bin that can accommodate the weight of the item
update remaining bin space
endfor
endfor
if there is no bin to accommodate the current item then no. of bins+=1 & allocate a new bin //increment
endif
return no. of bins
Best Fit:
• Initialize the no. of bins with 0
• allocate an array to can keep track of the remaining space from a bin after inserting an item into it
• for i=1 to no. of items do
for j=1 to no. of bins do
put item into the bin that leaves the tightest empty space among all candidates
update the minimum remaining space
endfor
endfor
if there is no bin that can accommodate the current item then create new bin & increase no. of bins by 1...