Questions on D1 bin packing algorithms

Watch
b3rry
Badges: 0
Rep:
?
#1
Report Thread starter 5 years ago
#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?
:confused:
0
reply
Smaug123
  • Study Helper
Badges: 15
Rep:
?
#2
Report 5 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?
:confused:
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
reply
Magnesium
Badges: 17
Rep:
?
#3
Report 5 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?
:confused:
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
reply
Smaug123
  • Study Helper
Badges: 15
Rep:
?
#4
Report 5 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
reply
Magnesium
Badges: 17
Rep:
?
#5
Report 5 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
reply
b3rry
Badges: 0
Rep:
?
#6
Report Thread starter 5 years ago
#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
reply
Smaug123
  • Study Helper
Badges: 15
Rep:
?
#7
Report 5 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
reply
Lien-Kit
Badges: 0
Rep:
?
#8
Report 5 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
reply
b3rry
Badges: 0
Rep:
?
#9
Report Thread starter 5 years ago
#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
reply
b3rry
Badges: 0
Rep:
?
#10
Report Thread starter 5 years ago
#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
reply
Lien-Kit
Badges: 0
Rep:
?
#11
Report 5 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
reply
X

Quick Reply

Attached files
Write a reply...
Reply
new posts
Back
to top
Latest
My Feed

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.

Personalise

Current uni students - are you thinking of dropping out of university?

Yes, I'm seriously considering dropping out (129)
14.61%
I'm not sure (40)
4.53%
No, I'm going to stick it out for now (265)
30.01%
I have already dropped out (22)
2.49%
I'm not a current university student (427)
48.36%

Watched Threads

View All
Latest
My Feed

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.

Personalise