Further Maths - Bin-packing
Flashcards
What is the bin-packing problem?
Minimising the amount of bins used to store things of a fixed sizes.
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.
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.
Why is the full-bin combinations algorithm not very good?
It doesn’t scale up well and basically reduces to inspection.
Are first-fit and first-fit decreasing optimal or heuristics?
Heuristics.