I hate to make this more complicated than it needs to be...but...

Must you also consider the weights of multiple cartons? Usually if they're all similar in weight, the total shipping charges are less than if one is very heavy.

For shipments that will require multiple cartons, spread the largest boxes out amongst the cartons and fill with the smaller boxes. If a box doesn't fit, change the distribution of the boxes that you've used so far and don't proceed until all boxes fit. (I guess that one's obvious)

My last thought is that this really becomes an excercise in working with the least common denominator(LCD). Are the box sizes random? (is this was already answered sorry). If they are, then use an inch or cm as the LCD. If they are standard, find the LCD, (ie, 6 inches, 10 cm, etc.).

Use a table which has 6 columns....CARTONID[C(10)], BOXID[C(10)], ORIENTATION[N(1)], X[N(2)], Y[N(2)], Z[N(2)]. The Orientation is a code you use to determine which plane faces up, and which plane faces forward (this would be used by the graphical portion later) The X,Y,Z would be the size of the box in units of LCD. The first box gets placed at 0,0,0. The program then calculates three locations for the next box to be placed [X(1),0,0; 0,Y(1),0; 0,0,Z(1)]. For each new box added, the program removes one location (b/c it just got used) and calculates 3 more. The location used should maximize the remaining space in usuable volume (perhaps 2 to 4 LCD units, depending on the range of sizes of the boxes). Each time a box is moved, or removed, the program wipes out the last three locations and restores the one that was erased (location of the box that was removed).

This procedure allows the program to 'think' in three dimentions.

Let me know if this helps.

Matt