Further Maths - Bin-packing
Pearson Edexcel Further Mathematics 2022
Flashcards
The bin-packing problem
What is the bin-packing problem?
Minimising the amount of bins used to store things of a fixed sizes.
Full-bin combinations
What is the full-bin combinations algorithm for bin-packing?
Fill as many bins as possible using full-bin combinations and then pack the remaining items into the first available bin.
What is it called when you solve a problem by listing all possibilities?
Complete enumeration.
First-fit and first-fit decreasing
What is the first-fit algorithm for bin-packing?
Work through the list of items and place each item in the first bin with sufficient space.
What modification to the first-fit algorithm could you make to allow it to create better solutions?
Sort the items in descending order first.
What is the first-fit decreasing algorithm?
Rearrange the items to decreasing order and then use the first-fit algorithm.
Quality of the algorithms
Why is the full-bin combinations algorithm not very good?
It doesn’t scale up well and basically reduces to inspection.