To solve this problem you need a formal definition of what is "the first box that can contain it". "first ... that" assumes a certain order.
You have n items. How many boxes there's, an infinite amount? Then, it's O(n) because you do certain operation to insert one item, then repeat n times. Limited amount? Then things are getting really complex because your "first-hit" algorithm
can run out of boxes. Then what?
Wow that is a great question! Shame it was moved from the micro section, I would love to know how a 30f, could be used to achieve this. At first I thought i saw the answer, but as you look at it more, the harder it seems!
Are all item's items of a fixed maximum size? and are any of a fixed minimum size?
no i mean during the sorting process, to decide an item to move up or down you use MIN criteria. such that..
Code:
if MIN(a(i).x, a(i).y, a(i).z) < MIN(a(i-1).x, a(i-1).y, a(i-1).z) then
tmp = a(i-1)
a(i-1)=a(i)
a(i)=tmp
end if
int MIN(x,y,z) {
return the smallest among x,y,z.
end sub
though i dont think this simple code may fullfill your need, you need to look closer into the criteria to decide if an item fit in the given box and then you can modify MIN function to suit your need. properly sorted boxes based on your criteria will enable you to binary search appropriate box in log(n) process. you know your problem clearly we dont. YMMV.
there are situation when MIN criteria will not fullfill exactly just as your example above 2x2x2 box wont fit 1x9x8 item, so maybe you can use MAX criteria? you study that
So, all the boxes are of the same size and you can put multiple items into the same box, right?
That is a very complex task. And the "first hit" algorithm will not give you the minimum number of boxes. "Frist hit" would rather minimize the speed and to do that you simple take a new box for every item - you cannot do it faster than this. This will run in O(n).
You can save some boxes, if you take two items at a time and if they fit in the same box you put them there and if not, you put one in the box and pull another item from the queue and so on. This will run in O(n).
To evolve this idea further, you can maintain a pool of items ready to be put into the boxes, then as soon as you find a set of items which fills a good portion of the box, you fill in the box and pull some new items into your pool to replace the used items. Any sort of such algorithm will run approximately in O(n) too.
Getting the absolute minimum of the boxes for the given set of items is a very complex task and I don't think an easy algorithm exists. Brute force will run way worse than O(n^2).
You could also look into sorting according to the longest diagonal, which is sqrt(a^2+b^2+c^2), but i'd like to know more about the elements of this problem first.
When you say you have 'sizes' 5x9x8 does that mean that is the max size and there are boxes with integer sizes up to that size?
Could you post the original description of the problem. I think you are complicating this more than originally intended (the solution suggestion talks about item weight and box capacity, you are talking about dimensions).
I'd like to see that data too as some of the posts in this thread dont make that much sense as you noticed too.
I'd also like to see what size the objects can be as well as a few example 'pickings' like this for example:
First pick: item=2x5x3, box=3x6x4
Second pick: item=3x2x6, box=5x3x8
and if the dimensions are always integer values or can they be fractional such as:
2.345 x 1.643 x 7.111
You have fixed-size mail shipping boxes.
You can ship anything you want that fits in the box.
You have n items to ship and have a large supply of 5 x 9 x 8 boxes.
You want to minimize the number of boxes you use.
The first-fit algorithm is a greedy algorithm for this problem - it processes the items in the sequence in which they are first given and places them in the first box in which they fit, scanning through the boxes in increasing order.
First fit is not optimum but it never takes more than twice as many boxes as the minimum possible.