You are Here: Home >< Maths

# Questions on D1 bin packing algorithms Watch

1. Does full bin packing and First fit decreasing algorithm always give the same amount of waste space?
And when you can not perform full bin packing on a set of data (no combinations can be found to make a full bin) do you always go for the First fit decreasing algorithm?
2. (Original post by b3rry)
Does full bin packing and First fit decreasing algorithm always give the same amount of waste space?
And when you can not perform full bin packing on a set of data (no combinations can be found to make a full bin) do you always go for the First fit decreasing algorithm?
Bin packing is *hard*. There is no known algorithm that always produces the best fit in a sensible amount of time (although in an exam, they'll give you nice cases which first-fit behaves well on).

I don't know what "full bin packing" means, I'm afraid - could you describe the algorithm? A quick Google didn't help me.

First-fit decreasing doesn't always optimise. Case in point: bins of size 5,4 are filled perfectly by boxes of size 2,3,4 in that order, but first-fit decreasing would sort into the order {4,3,2} and would fill the bins suboptimally by putting 4 into 5 (incorrectly), then 3 into 4, then running out of space.
3. (Original post by b3rry)
Does full bin packing and First fit decreasing algorithm always give the same amount of waste space?
And when you can not perform full bin packing on a set of data (no combinations can be found to make a full bin) do you always go for the First fit decreasing algorithm?
Full bin packing would just be making sure as many bins are optimally full as possible. So you can choose any number in the data set, input it into Bin1 and then if the next number can be added into Bin1 whilst not overflowing then you add that in aswell. You just keep adding into Bin1 until it reaches the maximum input value/overflows and then you move onto Bin2. You can always perform full bin packing even if it doesn't technically create a "full bin". You just add until it's the fullest combination you get.
4. (Original post by Magnesium)
Full bin packing would just be making sure as many bins are optimally full as possible. So you can choose any number in the data set, input it into Bin1 and then if the next number can be added into Bin1 whilst not overflowing then you add that in aswell. You just keep adding into Bin1 until it reaches the maximum input value/overflows and then you move onto Bin2. You can always perform full bin packing even if it doesn't technically create a "full bin". You just add until it's the fullest combination you get.
You've just described the First Fit algorithm, which is not optimal. (See my example above of why first-fit decreasing can be nonoptimal.)
5. (Original post by Smaug123)
You've just described the First Fit algorithm, which is not optimal. (See my example above of why first-fit decreasing can be nonoptimal.)
Sorry I didn't mean 'optimal solution' back there. But i think first fit is what the OP means instead of 'full bin'.
6. (Original post by Smaug123)
Bin packing is *hard*. There is no known algorithm that always produces the best fit in a sensible amount of time (although in an exam, they'll give you nice cases which first-fit behaves well on).

I don't know what "full bin packing" means, I'm afraid - could you describe the algorithm? A quick Google didn't help me.

First-fit decreasing doesn't always optimise. Case in point: bins of size 5,4 are filled perfectly by boxes of size 2,3,4 in that order, but first-fit decreasing would sort into the order {4,3,2} and would fill the bins suboptimally by putting 4 into 5 (incorrectly), then 3 into 4, then running out of space.
Full bin packing is just to find the perfect amount to fit the bin, and i think(not entirely sure) you use first fit decreasing algorithm to deal with the left over values.
7. (Original post by b3rry)
Full bin packing is just to find the perfect amount to fit the bin, and i think(not entirely sure) you use first fit decreasing algorithm to deal with the left over values.
Oh right - as I understand it, then, "full bin packing" isn't really an algorithm. It's an algorithm in the same sense as "solve the sudoku" is an algorithm for solving sudokus.
8. The best solution to have the least amount of waste space is probably the full bin method, having said that it is the most time consuming if there is a large amount of data to handle hence the use of algorithms. All in all its just a bit of a pain that's why they're removing D1 from the maths syllabus in a few years.
9. (Original post by Magnesium)
Full bin packing would just be making sure as many bins are optimally full as possible. So you can choose any number in the data set, input it into Bin1 and then if the next number can be added into Bin1 whilst not overflowing then you add that in aswell. You just keep adding into Bin1 until it reaches the maximum input value/overflows and then you move onto Bin2. You can always perform full bin packing even if it doesn't technically create a "full bin". You just add until it's the fullest combination you get.
ahhhh..so you can still perform full bin packing even there aren't any combinations to make a full bin?
it just seems like the normal first fit algorithm to me.
10. (Original post by Lien-Kit)
The best solution to have the least amount of waste space is probably the full bin method, having said that it is the most time consuming if there is a large amount of data to handle hence the use of algorithms. All in all its just a bit of a pain that's why they're removing D1 from the maths syllabus in a few years.
i have just did a question using all 3 bin packing algorithm(excluding lower bound) first fit decreasing algorithm and full bin packing gave me the exact same waste space, i wonder if that is just the odd of the question..
Removing D1? But is fun tho.
11. (Original post by b3rry)
i have just did a question using all 3 bin packing algorithm(excluding lower bound) first fit decreasing algorithm and full bin packing gave me the exact same waste space, i wonder if that is just the odd of the question..
Removing D1? But is fun tho.
Might be the question, try a few different ones.
I hated D1 out of all my maths modules, even FP1 beats it

TSR Support Team

We have a brilliant team of more than 60 Support Team members looking after discussions on The Student Room, helping to make it a fun, safe and useful place to hang out.

This forum is supported by:
Updated: January 18, 2015
Today on TSR

### 'Entry requirements are a form of elitism'

What do you think?

### I fancy Donald Trump...

Discussions on TSR

• Latest
• ## See more of what you like on The Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

• Poll
Useful resources

### Maths Forum posting guidelines

Not sure where to post? Read the updated guidelines here

### How to use LaTex

Writing equations the easy way

### Study habits of A* students

Top tips from students who have already aced their exams

## Groups associated with this forum:

View associated groups
Discussions on TSR

• Latest
• ## See more of what you like on The Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

• 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