Deadline: 2022-04-23 24:00

• In the bin packing task, we need to determine the minimum number of 1-capacity bins that can hold the weights \((s_i)_{i = 1}^n\), \((0 < s_i \le 1)\) given in the input. The problem is NP-complete, so an effective solution (according to our current knowledge) is not available, but several approximation algorithms have been created for it. In this task, the aim is to examine some approximate heuristics.
• In the file binPack.py we have provided a framework program that examines the lower limit and three approximation algorithms for the bin packing problem at a given input:
  1. The value of OPT is the ceiling of (the smallest integer greater than) the total weight of objects, that is \[\left\lceil\sum_{i=1}^n s_i\right\rceil,\] which is the lower limit for the required number of bins.
  2. The first fit (FF) algorithm tries to place the objects in the bins in the order they are given, so that the next object is always placed in the first bin it can fit into. If there is no room in any bins, a new one is created.
  3. The first fit decreasing (FFD) algorithm is similar to FF, but first it sorts the packs in descending order.
  4. The best-fit (BF) algorithm puts all objects in the bin where the least space is left. (This is already written in the program, study it!)
• Modify the binPack.py file and finish the program!
  1. Implement the FF algorithm in the first_fit function.
  2. Implement the FFD algorithm in the first_fit_d function. Be careful as Python passes the lists by reference so that if the list of weights is sorted, it directly modifies the original list. Instead, work with a copy of the list!
  3. Study the BF algorithm which is implemented in the best_fit function.
  4. In the program a list named packs is given. Replace it with a list of 1000 random numbers between 0 and 1 and call the packing functions on them.
  5. Run the program a few times! Compare the effects of the algorithms on the generated random inputs! Please write your experiences in a comment of the code.