Bin Packing Algorithms – First Fit Algorithm

It's only fair to share...Share on FacebookTweet about this on TwitterPin on PinterestShare on Google+Share on RedditEmail this to someone

We are seeking to pack bins (of given size) with various items.

To find the lower bound, sum the numbers to be packed and divide this total by the size of the bin. The lower bound is the least integer greater than or equal to the result.

Example

Pack the following items in bins of size 20

8 7 14 9 6 9 5 15 6 7 8

The sum is 94

94 divided by 20 is 4.7

So the lower bound is 5 and we need at least 5 bins

FIRST-FIT ALGORITHM

Take the items in the order given and place each item in the first available bin that can take it, starting from Bin 1 each time.

Bin 1 8 7 5

Bin 2 14 6

Bin 3 9 9

Bin 4 15

Bin 5 6 7

Bin 6 8

Comments are closed.