Back
to top
Questions on D1 bin packing algorithms
Watch this threadPage 1 of 1
Go to first unread
Skip to page:
b3rry
Badges:
0
Rep:
?
You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#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?
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
reply
Smaug123
Badges:
15
Rep:
?
You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#2
Report
#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?
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?
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:
?
You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#3
Report
#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?
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
reply
Smaug123
Badges:
15
Rep:
?
You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#4
Report
#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.
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
Magnesium
Badges:
17
Rep:
?
You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#5
Report
#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.)
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
b3rry
Badges:
0
Rep:
?
You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#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.
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
Smaug123
Badges:
15
Rep:
?
You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#7
Report
#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.
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
Lien-Kit
Badges:
0
Rep:
?
You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#8
Report
#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:
?
You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#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.
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.
it just seems like the normal first fit algorithm to me.
0
reply
b3rry
Badges:
0
Rep:
?
You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#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.
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.
Removing D1? But is fun tho.
0
reply
Lien-Kit
Badges:
0
Rep:
?
You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#11
Report
#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.
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.
I hated D1 out of all my maths modules, even FP1 beats it
0
reply
X
Page 1 of 1
Go to first unread
Skip to page:
Quick Reply
