Box Size - LxWxH ???
Results 1 to 6 of 6

Thread: Box Size - LxWxH ???

  1. #1
    Senior Member
    Join Date
    Apr 2004
    Location
    Mississauga,Ontario
    Posts
    129

    Question Box Size - LxWxH ???

    I've got a tricky lil problem.

    Here goes, I have three items.

    Item 1: 3"x3"x 3"
    Item 2: 27"x17"x7"
    Item 3: 6"x5"x10"


    I've also got three boxes:

    Box 1: 12"x12"x12"
    Box 2: 20"x16"x12"
    Box 3: 30"x30"x10"


    Now what I want to do is check to see if all the items will fit in either of the boxes, if they do then i'll proceed with to the selection of that box.
    If they don't then i'll try to fit as many items in one box as possible, then have the remaining items do the same. I want to do this until all items are in a box.

    Can this be done, I spent several hours going over this.

  2. #2
    PHP Witch laserlight's Avatar
    Join Date
    Apr 2003
    Location
    Singapore
    Posts
    13,538
    Now what I want to do is check to see if all the items will fit in either of the boxes, if they do then i'll proceed with to the selection of that box.
    If they don't then i'll try to fit as many items in one box as possible, then have the remaining items do the same. I want to do this until all items are in a box.

    Can this be done, I spent several hours going over this.
    I think you're have the elaborate on what you're trying to do.
    Basically, given a box of some size, and given n items of different sizes, you want to fit as many items as possible into the box?
    Or are you given n item types of different sizes, and the aim is to fit as many items of the largest item type, followed by as many items of the next largest item type, until no more items of the list of n item types may fit into the box?
    Or something else?

    If you're trying to solve the first scenario, then you would be dealing with a knapsack problem that is NP-complete.
    If you're trying to solve the second scenario, then the problem seems to be some sort of super-increasing knapsack problem, which is easy to solve.
    Use Bazaar for your version control system
    Read the PHP Spellbook
    Learn How To Ask Questions The Smart Way

  3. #3
    Senior Member
    Join Date
    Apr 2004
    Location
    Mississauga,Ontario
    Posts
    129
    It's a mix of both. I want to fit all the items in one box. If this is not possibly (based on dimention limitations), I would like to fit as many items in one box as possible and do this until all items are in a box.


    Scenario 1:
    =========

    Items:
    2 x DVD (7"x6"x1")
    1 x DVD Player (17"x14"x4")

    Available Boxes:
    Box 1: 12"x12"x12"
    Box 2: 20"x16"x12"


    Ideally I would like all items to fit in one box. In this particular scenario all items do fit in one box (Box 2).


    Scenario 2:
    =========

    Items:
    2 x DVD (7"x6"x1")
    2 x DVD Player (17"x14"x4")
    2 x 13" LCD T.V. (16"x6"x16")

    Available Boxes:
    Box 1: 12"x12"x12"
    Box 2: 20"x16"x12"


    In this scenario all items don't fit in one box. So I would place as many items in one box as possible. Until all items are in a box.

  4. #4
    PHP Witch laserlight's Avatar
    Join Date
    Apr 2003
    Location
    Singapore
    Posts
    13,538
    Basically, if all the items fit into a single box, choose that box to store the items.
    If not, then distribute the items among the given boxes such that as many items as possible are stored.
    For this, the solution need not be optimal, except in the case where only the optimal solution can store all the items.
    Items and boxes are of different sizes and quantities.

    How do you check if all the items fit into a single box, i.e. how is the calculation of such a check done?

    OT: my 4000th post...
    Use Bazaar for your version control system
    Read the PHP Spellbook
    Learn How To Ask Questions The Smart Way

  5. #5
    Senior Member
    Join Date
    Apr 2004
    Location
    Mississauga,Ontario
    Posts
    129
    How do you check if all the items fit into a single box, i.e. how is the calculation of such a check done?
    That's what i'm trying to find out. I need a way to perform such a check.


    BTW congrats on 4000th post.

  6. #6
    PHP Witch laserlight's Avatar
    Join Date
    Apr 2003
    Location
    Singapore
    Posts
    13,538
    That's what i'm trying to find out. I need a way to perform such a check.
    Okay....

    I shall admit that I have no real experience in solving the class of problems that you're proposing.
    You might want to try reading these 2 webpages from Steven Skiena's "The Algorithm Design Manual" and see if they are helpful in any way:

    Knapsack Problem
    Bin Packing

    BTW congrats on 4000th post.
    Thanks... 4096 should be coming shortly, methinks
    Use Bazaar for your version control system
    Read the PHP Spellbook
    Learn How To Ask Questions The Smart Way

Thread Information

Users Browsing this Thread

There are currently 1 users browsing this thread. (0 members and 1 guests)

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •