Sorting Into Groups Based On Arbitrary Size

This is a discussion on Sorting Into Groups Based On Arbitrary Size within the C++ Programming forums, part of the General Programming Boards category; OK, For the duration of this question i will use a simple example: You ship stuff in boxes, and you ...

  1. #1
    That Creepy Network Guy DeepBlackMagic's Avatar
    Join Date
    Feb 2003
    Posts
    265

    Sorting Into Groups Based On Arbitrary Size

    OK, For the duration of this question i will use a simple example: You ship stuff in boxes, and you can hold say 100 arbitrary units of space per box (just think in 2 dimensions) all of your units are flexable so we dont have to worry about conflicting shapes either, simple example. You want to sort these items of varying sizes into boxes such that the least amount of boxes are used to ship everything. How (Other than brute forcing each item combonation into each box and praying you find matches) can you accomplish this? Some algorithm? Also these items will eventually change in size over time, so i might have to re-sort the boxes on the fly. Im looking for a relatively fast way to do this all. Any input would be greatly appreciated.

  2. #2
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,497
    This is a classic example of a classic problem
    http://www.nist.gov/dads/HTML/knapsackProblem.html

    Or take a probability (or Monte Carlo) approach - that any "good" random solution will do and will take a lot less time to compute. If the random solution is on average within say 1% of the true answer, then 1% of the time, you'll ship one extra box.

    Or how about this.
    Say the sum of all your units is 432 (and you have 100 per box).
    No amount of rearranging will ever produce 4 boxes, you need a minimum of 5.
    So all you really need is "any" answer which produces a result packed into 5 boxes. There is no benefit in working out the best answer.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    That Creepy Network Guy DeepBlackMagic's Avatar
    Join Date
    Feb 2003
    Posts
    265
    Thanks alot for the quick reply, (btw you should update your avatar for Doom3 )

    Im interested in setting an ideal value for these boxes as well, such as saying they might be able to hold 120 but id like to keep it at 80 ideally, and force the program to fit it all into 2 boxes.

    I have been searching and have come up with the term "Bin Packing" as a possible name for this problem as well. Ideally id like to expand it from one dimension to 3 or more dims. Im not sure if the knapsack solution is expandable to make this work.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. window size VS. pixel size
    By dug in forum Windows Programming
    Replies: 2
    Last Post: 08-26-2003, 06:30 AM
  2. Replies: 11
    Last Post: 03-25-2003, 04:13 PM
  3. Changing a Structures Members array size
    By Xei in forum C++ Programming
    Replies: 1
    Last Post: 11-07-2002, 06:45 PM
  4. Tab Controls - API
    By -KEN- in forum Windows Programming
    Replies: 7
    Last Post: 06-02-2002, 09:44 AM
  5. File Size and File Size on Disk
    By DavidP in forum A Brief History of Cprogramming.com
    Replies: 4
    Last Post: 12-15-2001, 07:03 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21