240 OTHER ALGORITHMIC TECHNIQUES
only when an object will not fit in any of the current bins. Write an algo-
rithm for best fit. Show how best fit would have handled the two unsorted
examples in the text.- Another technique for bin packing is next fit, where we keep putting items
into a bin as long as they will fit. The first object that doesn’t fit in a bin
causes the algorithm to start a new bin. The algorithm never backs up to a
previous bin. Write an algorithm for next fit. Show how next fit would have
handled the two unsorted examples in the text. - Another technique for bin packing is worst fit, where each item is placed in
the bin so that the most amount of space is left. New bins are started only
when an object will not fit in any of the current bins. Write an algorithm
for worst fit. Show how worst fit would have handled the two unsorted
examples in the text. - What will be the best worth found by the backpack approximation algo-
rithm with a limit of 55 and the items ([5, 20], [10, 25], [15, 30], [20, 70],
[25, 75], [30, 15], [35, 35], [40, 60])? Is the result found optimal? - What will be the best result found by the subset sum approximation algo-
rithm if it was run for pass values of 0, 1, and 2 and for the set of values {29,
21, 16, 11, 3} with a limit of 52? Is this result optimal?
9.2 Probabilistic Algorithms
Probabilistic algorithms take a radically different approach from the determin-
istic algorithms that were explored in Chapters 1 through 7. In some applica-
tions, these probabilistic algorithms provide results that cannot be achieved
through deterministic means. The examples and applications presented here are
not meant to be exhaustive. They are intended to illustrate the range of possi-
bilities.■ 9.2.1 Numerical Probabilistic Algorithms
Numerical probabilistic algorithms calculate an approximate result for some
mathematical problem. The longer these algorithms are given to generate a
result, the greater precision that result will have.