Bin Packing Algorithms (AS)

Bin Packing Algorithms (AS)

Bin Packing Algorithms

First Fit (FF) Algorithm

• Definition: The First Fit algorithm places each item in the first bin where it will fit as items are processed in the order they occur.
• Advantage: Easy to implement and execute, computationally less complex.
• Disadvantage: It can result in an inefficient packing with more bins than necessary.

First Fit Decreasing (FFD) Algorithm

• Definition: The First Fit Decreasing algorithm sorts the list of items in decreasing order before applying the first fit algorithm.
• Advantage: More efficient than First Fit in terms of the number of bins often needed.
• Disadvantage: Increased computational complexity as the list needs to be sorted first.

Full Bin (FB) Algorithm

• Definition: The Full Bin algorithm attempts to fill each bin with exactly the bin capacity, if it is not possible, then the bin is closed.
• Advantage: It can be efficient for items of similar size.
• Disadvantage: It often results in wasted space in bins and additional bins when item sizes vary.

Remember these algorithms are heuristic in nature, meaning that they provide an approximate solution and do not guarantee the optimal solution. Familiarise with how to apply these algorithms using various datasets and be comfortable discussing their advantages and disadvantages.