• Revision:Packing Algorithms

TSR Wiki > Study Help > Subjects and Revision > Revision Notes > Mathematics > Packing Algorithms



Contents

First Fit

Work along the list, putting items in the first place where they fit. Remember you can go back and fill previous gaps if later pieces fit.

First Fit Decreasing

Start by sorting the items into decreasing order. Then proceed to work along the (newly ordered) list as with First Fit.

Example

Tapes last 45 minutes. The songs to be recorded on the tapes have the following durations, in minutes.

8 4 5 3 6 9 4 10 7 12 5 8 4 5

The total duration is exactly 90 minutes. Can the songs be fitted onto 2 tapes?

Using First Fit

3 tapes are needed.

Image:Packing example 1.jpg

Using First Fit decreasing

2 tapes are needed.

12 10 9 8 8 7 6 5 5 5 4 4 4 3

Image:Packing example 2.jpg

However neither method always gives the optimal solution.

Also See

See the other D1 notes:

  1. Algorithms
  2. Sorting algorithms
  3. Packing algorithms
  4. Graphs and networks
  5. Minimum connector problems
  6. The shortest path
  7. Route inspection
  8. The travelling salesman problem
  9. Linear programming
  10. The simplex algorithm

Comments

Try Learn together, TSR's study area

46,398
revision notes

54,713
mindmaps

57,764
crosswords

18,297
quizzes

create
a study planner

thousands
of discussions


The home of Results and Clearing

1,223

people online now

1,567,000

students helped last year
Poll
How are you feeling about GCSE results day?

The Student Room, Get Revising and Marked by Teachers are trading names of The Student Room Group Ltd.

Register Number: 04666380 (England and Wales), VAT No. 806 8067 22 Registered Office: International House, Queens Road, Brighton, BN1 3XE