Finding the optimal solution to this problem is NP complete. That is the optimal solution can only be found by exhaustively trying every possible combination of assignments of packages to bins. Fortunately there are a lot of heuristics for solving the problem which do a pretty good job. In this lab you will will compare several different "greedy" heuristics.
For a given set of packages, and a given bin capacity, it is easy to compute the theoretical lower bound on the number of required bins. The following algorithm will do it:
Given: P a set of packages. Each package, pi has a weight of Pi.weight C the capacity of the bins Let: TW = sum of all package weights B = TW / C if B==floor(B) minimum number of containers is B else minimum number of containers is floor(B)+1
Algorithm: NextFit Given: W: an array of weights of packages. C: the capacity of a bin Let wc=0 // weight of the current package tw=0 // the amount of weight in the current bin bc=1 // the number of bins used Repeat if there are no more packages break wc = weight of next package if tw+wc > C increment bc set tw = wc else set tw = tw + wc return bc
Algorithm: BestFit Given: W: an array of weights of packages. C: the capacity of a bin B: an array of bins, all initially empty Let wc=0 // weight of the current package bc=0 // the number of bins with packages Repeat if there are no more packages break wc = weight of next package bb = -1 // the best bin to put the package in bSpace = C // the amount of space remaining in the best bin bi = 0 // the index of the bin being considered while bi < bc Let t = B[bi]+wc if t < C if (C-t) < bSpace set bb = bi set bSpace = C-t increment bi if bb>=0 B[bb] = B[bb]+wc else B[bc] = wc increment bc return bc
Algorithm: WorstFit Given: W: an array of weights of packages. C: the capacity of a bin B: an array of bins, all initially empty Let wc=0 // weight of the current package bc=0 // the number of bins with packages Repeat if there are no more packages break wc = weight of next package bb = -1 // the best bin to put the package in bSpace = 0 // the amount of space remaining in the best bin bi = 0 // the index of the bin being considered while bi < bc Let t = B[bi]+wc if t < C if (C-t) > bSpace set bb = bi set bSpace = C-t increment bi if bb>=0 B[bb] = B[bb]+wc else B[bc] = wc increment bc return bc
Once sorted, the next fit, best fit and worst fit algorithms can be applied without further modification.
Once implemented you will test each on your algorithms on two criteria:
143 53 57 32 56 43 40 45 58 58 55For this data, the output of the 9 algorithms is:
Algorithm Bins Speed(microseconds) NextFit 4 1 BestFit 4 4 WorstFit 4 4 desc SortedNextFit 5 3 desc SortedBestFit 4 6 desc SortedWorstFit 4 7 asc SortedNextFit 5 3 asc SortedBestFit 5 7 asc SortedWorstFit 5 6As the number of items to be put into bins grows, you can expect that the differences between the algorithms will be larger as well. In the data above, the numbers of bins is correct for the given data. The times numbers are completely made up. (for 10 items the time would be too short to measure accurately, so I did not even try.)
The data files are available on UNIX as
/home/gtowell/Public/337/Lab13/sample.txt /home/gtowell/Public/337/Lab13/d100.txt /home/gtowell/Public/337/Lab13/d1000.txt /home/gtowell/Public/337/Lab13/d10000.txt /home/gtowell/Public/337/Lab13/d100000.txt /home/gtowell/Public/337/Lab13/d1000000.txt /home/gtowell/Public/337/Lab13/d10000000.txtThe biggest file has 10,000,000 packages (think FedEx on a busy night). sample.txt is identical to the data just above.
Data Set | Number of packages | Bin Capacity | Theoretical Min Bins | On line | Off line, ASC | Off line, DESC | ||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
Next Fit | Best Fit | Worst Fit | Next Fit | Best Fit | Worst Fit | Next Fit | Best Fit | Worst Fit |
Topic | Points |
---|---|
Intro / Contributions | 10 |
Algorithms | 10 |
Theoretical Analysis (Big-O) | 10 |
Data and analysis | 50 |
Appendix | 20 |
For you secret identity: 2 TV shows