Thread: Sorting Into Groups Based On Arbitrary Size

1. 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. 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.

3. 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