# Questions on D1 bin packing algorithms

#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?
0
7 years ago
#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.
0
7 years ago
#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.
0
7 years ago
#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.)
0
7 years ago
#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'.
0
#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.
0
7 years ago
#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.
0
7 years ago
#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.
0
#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.
0
#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.
0
7 years ago
#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
0
X

new posts
Back
to top
Latest
My Feed

### Oops, nobody has postedin the last few hours.

Why not re-start the conversation?

see more

### See more of what you like onThe Student Room

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

### Poll

Join the discussion

#### How did your AQA A-level Psychology Paper 1 go?

Loved the paper - Feeling positive (80)
41.45%
The paper was reasonable (88)
45.6%
Not feeling great about that exam... (14)
7.25%
It was TERRIBLE (11)
5.7%