Hey there! Sign in to join this conversationNew here? Join for free
    • Thread Starter
    Offline

    0
    ReputationRep:
    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:
    • PS Helper
    • Study Helper
    Offline

    13
    ReputationRep:
    PS Helper
    Study Helper
    (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.
    Offline

    3
    ReputationRep:
    (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.
    • PS Helper
    • Study Helper
    Offline

    13
    ReputationRep:
    PS Helper
    Study Helper
    (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.)
    Offline

    3
    ReputationRep:
    (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'.
    • Thread Starter
    Offline

    0
    ReputationRep:
    (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.
    • PS Helper
    • Study Helper
    Offline

    13
    ReputationRep:
    PS Helper
    Study Helper
    (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.
    Offline

    0
    ReputationRep:
    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.
    • Thread Starter
    Offline

    0
    ReputationRep:
    (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.
    • Thread Starter
    Offline

    0
    ReputationRep:
    (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.
    Offline

    0
    ReputationRep:
    (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
 
 
 
  • 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
    Brexit voters: Do you stand by your vote?
    Useful resources

    Make your revision easier

    Maths

    Maths Forum posting guidelines

    Not sure where to post? Read the updated guidelines here

    Equations

    How to use LaTex

    Writing equations the easy way

    Student revising

    Study habits of A* students

    Top tips from students who have already aced their exams

    Study Planner

    Create your own Study Planner

    Never miss a deadline again

    Polling station sign

    Thinking about a maths degree?

    Chat with other maths applicants

    Can you help? Study help unanswered threads

    Groups associated with this forum:

    View associated groups
  • 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

    Write a reply...
    Reply
    Hide
    Reputation gems: You get these gems as you gain rep from other members for making good contributions and giving helpful advice.