@Jindotgae, @Mid-Night_Sun, @CRYPT, @thewalrus, @inDUSTry
Does anyone knows an algorithm for the Best Fit algorithm in the Bin Packing Problem (BPP)?
Bin Packing Problem is part of combinatory optimization and belongs to the NP-hard problems. BPP is basically about packing bins with certain items of different sizes with objectives like
- packing in most time efficient way,
- pack the items so the items are distributed evenly
- pack the items into the bin so you use as least bins as possible
- ....
There are different ways to achieve that, each have their own advantages and disadvantages. These are the algorithms that exist:
- Next fit /Next fit decreasing
- Worst fit/Worst fit decreasing
- First fit/ First fit decreasing
- Worst fit/ Worst fit decreasing
- Full fit/Best fit
I'm interested in the Full fit/Best fit algorithm. This algorithm sorts the items so the bins are packed to the fullest, in order to use as least bins as possible. Does anyone know an (efficient) algorithm to that? I want to write a software that takes a number of items with their sizes and sorts them into as least bins as possible.
For further explanation and for those who are interested here a video.