Given: n objects to be placed in bins of capacity L each.
Object i requires units of bin capacity.
Objective: determine the minimum number of bins needed to
accommodate all n objects.
eg. Let L = 10,
Bin packing problem is NP complete when formulated as a decision problem.
As an optimization problem bin packing is NP-hard
Approximation Algorithm for Bin Packing:
1. First Fit (FF)
- Label bins as 1, 2, 3, . . .
- Objects are considered for packing in the order 1, 2, 3, . . .
- Pack object i in bin j where j is the least index such that
bin j can contain object i.
2. Best Fit (BF)
Same as FF, except that when object i is to be packed, find out
that bin which after accommodating object i will have the least
amount of space left.
3. First Fit Decreasing (FFD)
reorder objects so that
then use FF.
4. Best Fit Decreasing (BFD)
reorder objects as above and then use BF.
Th. Packing generated by either FF or BF uses no more than bins.
That by either FFD or BFD uses no more than